Combinatorial Nullstellensatz

With Applications to Graph Colouring

Xuding Zhu, R. Balakrishnan

• Publisher: Chapman and Hall/CRC
• Year: 2021
• ISBN:
  9781000426694
• Edition: 1
• Topic: Mathematik
• Subtopic: Algebra

Combinatorial Nullstellensatz is a novel theorem in algebra introduced by Noga Alon to tackle combinatorial problems in diverse areas of mathematics. This book focuses on the applications of this theorem to graph colouring. A key step in the applications of Combinatorial Nullstellensatz is to show that the coefficient of a certain monomial in the expansion of a polynomial is nonzero. The major part of the book concentrates on three methods for calculating the coefficients:

• Alon-Tarsi orientation: The task is to show that a graph has an orientation with given maximum out-degree and for which the number of even Eulerian sub-digraphs is different from the number of odd Eulerian sub-digraphs. In particular, this method is used to show that a graph whose edge set decomposes into a Hamilton cycle and vertex-disjoint triangles is 3-choosable, and that every planar graph has a matching whose deletion results in a 4-choosable graph.

• Interpolation formula for the coefficient: This method is in particular used to show that toroidal grids of even order are 3-choosable, r-edge colourable r-regular planar graphs are r-edge choosable, and complete graphs of order p+1, where p is a prime, are p-edge choosable.

• Coefficients as the permanents of matrices: This method is in particular used in the study of the list version of vertex-edge weighting and to show that every graph is (2, 3)-choosable.

It is suited as a reference book for a graduate course in mathematics.

Chapter 1

Some Definitions and Notations

In this chapter, we present some basic definitions and notations. Some other definitions are given at the appropriate places of the book.

Definition 1.0.1 A graphG consists of a vertex set $V(G)$ and edge set $E(G)$. A graph G is a finite graph if both $V(G)$ and $E(G)$ are finite sets; otherwise, G is an infinite graph.

The edges of a graph G are unordered pairs $e=\{u,v\}$ of vertices in V. If $e=\{u,v\}$ is an edge of G, then e is incident at u and v. Sometimes we write $e=uv$ instead of $e=\{u,v\}$. When the graph G is clear from the context, we simply write V and E in place of $V(G)$ and $E(G)$, respectively. An edge of the form $\{v,v\}$ is called a loop at vertex v. Two edges of G having the same end vertices are called parallel edges or multiple edges of G. A graph without loops and without multiple edges is called a simple graph. A graph H is a subgraph of G if $V(H)\subseteq V(G)$ and $E(H)\subseteq E(G).$ A subgraph H of G is called a spanning subgraph of G if $V(H)=V(G).$

Definition 1.0.2 The number of edges of G incident at a vertex u of G is called the degree of u in G, and is denoted by $d_G(u)$ or simply by $d(u)$ when the underlying graph G is clear from the context. A loop at u contributes 2 to the degree of u.

Definition 1.0.3 A walkW in a graph G is an alternating sequence of vertices and edges of the form $v_1{e}_1{v}_2{e}_2\dots v_i{e}_i{v}_{i+1}\dots v_{p-1}{e}_{p-1}{v}_p,$ where e_i is the edge $v_i{v}_{i+1},1\le i\le p-1.$ A trail in G is a walk in G in which no edge is repeated. A path is a trail in which no vertex is repeated.

Definition 1.0.4 A walk (resp. trail, path) is closed if its initial and terminal vertices coincide. A closed path is called a cycle.

Definition 1.0.5 A graph G is connected if there is a path between any two distinct vertices of $G;$ otherwise, G is disconnected. A component of a graph G is a maximal connected subgraph of G. So if G is connected, it has just one component.

Definition 1.0.6 Given a graph G, its line graph $L(G)$ is d...