Combinatorial Nullstellensatz and DP-coloring of graphs

DOI10.1016/J.DISC.2020.112115MaRDI QIDQ2005703zbMATH OpenOpenAlexFDO

Authors Hemanshu Kaul, J. A. Mudrock

Publication date 8 October 2020

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2003.01112

zbMATH Keywords

Alon-Tarsi numbercombinatorial NullstellensatzDP-coloringgraph coloringlist coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: We initiate the study of applying the Combinatorial Nullstellensatz to the DP-coloring of graphs even though, as is well-known, the Alon-Tarsi theorem does not apply to DP-coloring. We define the notion of good covers of prime order which allows us to apply the Combinatorial Nullstellensatz to DP-coloring. We apply these tools to DP-coloring of the cones of certain bipartite graphs and uniquely 3-colorable graphs. We also extend a result of Akbari, Mirrokni, and Sadjad (2006) on unique list colorability to the context of DP-coloring. We establish a sufficient algebraic condition for a graph $G$ to satisfy $ch{i}_{DP}(G)leq3$, and we completely determine the DP-chromatic number of squares of all cycles.

Review text

The authors show how to apply the very well-known tool of the combinatorial Nullstellensatz to a variation of the list-coloring problem for graphs. The paper is very valuable and gives new significant light to the combinatorial Nullstellensatz theorem.

Recommendations

• Combinatorial Nullstellensatz
• On DP-coloring of graphs and multigraphs
• Neighbor sum distinguishing total colorings via the combinatorial nullstellensatz
• DP-degree colorable hypergraphs
• A paintability version of the combinatorial Nullstellensatz, and list colorings of \(k\)-partite \(k\)-uniform hypergraphs

Cites work

• A note on a Brooks' type theorem for DP-coloring
• A note on the DP-chromatic number of complete bipartite graphs
• A relation between choosability and uniquely list colorability
• A solution to a colouring problem of P. Erdős
• A sufficient condition for DP-4-colorability
• Algebraically solvable problems: describing polynomials as equivalent to explicit solutions
• Alon-Tarsi number and modulo Alon-Tarsi number of signed graphs
• Choosability of powers of circuits
• Colorings and orientations of graphs
• Combinatorial Nullstellensatz
• Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
• DP-3-coloring of some planar graphs
• DP-colorings of graphs with high chromatic number
• DP-colorings of hypergraphs
• Every planar graph without 4-cycles adjacent to two triangles is DP-4-colorable
• Flexible color lists in Alon and Tarsi's theorem, and time scheduling with unreliable participants
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 3563170 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• List Total Colourings of Graphs
• On DP-coloring of graphs and multigraphs
• On the Alon-Tarsi number and chromatic-choosability of Cartesian products of graphs
• On two generalizations of the Alon-Tarsi polynomial method
• Planar graphs without 4-cycles adjacent to triangles are DP-4-colorable
• Proof of the list edge coloring conjecture for complete graphs of prime degree
• Sharp Dirac's theorem for DP-critical graphs
• The Alon-Tarsi number of planar graphs
• The asymptotic behavior of the correspondence chromatic number
• The Johansson-Molloy theorem for DP-coloring

Cited in

(16)

• Answers to two questions on the DP color function
• Edge-face list coloring of Halin graphs
• A deletion-contraction relation for the DP color function
• The DP color function of joins and vertex-gluings of graphs
• Coloring linear hypergraphs: the Erdős-Faber-Lovász conjecture and the combinatorial nullstellensatz
• Partial DP-coloring of graphs
• Non-chromatic-adherence of the DP color function via generalized theta graphs
• The combinatorial Nullstellensatz and DFT on perfect matchings in bipartite graphs.
• scientific article; zbMATH DE number 7491440 (Why is no real title available?)
• Combinatorial Nullstellensatz
• Transformation invariance in the combinatorial Nullstellensatz and nowhere-zero points of non-singular matrices
• A paintability version of the combinatorial Nullstellensatz, and list colorings of \(k\)-partite \(k\)-uniform hypergraphs
• An algebraic approach for counting DP-3-colorings of sparse graphs
• On polynomial representations of dual DP color functions
• Some orientation theorems for restricted DP-colorings of graphs
• DP color functions of hypergraphs

This page was built for publication: Combinatorial Nullstellensatz and DP-coloring of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2005703)