Applications of Combinatorial Nullstellensatz to Graph Colourings

The Combinatorial Nullstellensatz gives a sufficient condition for a polynomial to have a non-zero point in a given grid. Many combinatorial problems can be stated as the existence of a non-zero point of a polynomial in a certain grid, and hence have the potential of applying Combinatorial Nullstellensatz. This series of lectures explains some applications of Combinatorial Nullstellensatz to graph coloring and related problems. We focus on methods that show certain monomials in the expansion of a polynomial are non-vanishing, i.e., having non-zero coefficients. These include Alon-Tarsi orientations, interpolation formula and permanent method. These methods are illustrated with applications to problems in list colouring of graphs, vertex-edge weighting of graphs, list of forbidden out-degree orientations of graphs, etc.