On the chromatic polynomial and counting DP-colorings of graphs

DOI10.1016/j.aam.2020.102131zbMath1479.05109arXiv1904.07697OpenAlexW3099195868MaRDI QIDQ2221788

Jeffrey A. Mudrock, Hemanshu Kaul

Publication date: 2 February 2021

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

graph coloringchromatic polynomiallist coloringDP-coloringlist color function

Mathematics Subject Classification ID

Graph polynomials (05C31) Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (11)

A deletion-contraction relation for the DP color function ⋮ The DP color function of joins and vertex-gluings of graphs ⋮ Partial DP-coloring of graphs ⋮ Counting colorings of triangle-free graphs ⋮ DP color functions versus chromatic polynomials (II) ⋮ DP‐coloring Cartesian products of graphs ⋮ On the list color function threshold ⋮ An algebraic approach for counting DP-3-colorings of sparse graphs ⋮ Non-chromatic-adherence of the DP color function via generalized theta graphs ⋮ Answers to two questions on the DP color function ⋮ DP color functions versus chromatic polynomials

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• When does the list-coloring function of a graph equal its chromatic polynomial
• Sidorenko's conjecture, colorings and independent sets
• Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
• The chromatic polynomial and list colorings
• Colorings and orientations of graphs
• Every planar graph is 5-choosable
• DP-3-coloring of some planar graphs
• Every planar graph without 4-cycles adjacent to two triangles is DP-4-colorable
• A sufficient condition for DP-4-colorability
• A note on the DP-chromatic number of complete bipartite graphs
• The list chromatic index of a bipartite multigraph
• Asymptotically good list-colorings
• Criticality, the list color function, and list coloring the Cartesian product of graphs
• On DP-coloring of graphs and multigraphs
• Incidence matrices and interval graphs
• DP-colorings of graphs with high chromatic number
• DP-colorings of hypergraphs
• The asymptotic behavior of the correspondence chromatic number
• On the number of list‐colorings
• On chordal graphs and their chromatic polynomials
• Sharp Dirac's theorem for DP‐critical graphs
• The Johansson‐Molloy theorem for DP‐coloring
• A note on a Brooks' type theorem for DP‐coloring

This page was built for publication: On the chromatic polynomial and counting DP-colorings of graphs