Answers to two questions on the DP color function

DOI10.37236/9863zbMATH Open1465.05066arXiv2009.08242OpenAlexW3164898278MaRDI QIDQ2030743FDOQ2030743

Seth Thomason, J. A. Mudrock

Publication date: 7 June 2021

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: DP-coloring is a generalization of list coloring that was introduced in 2015 by Dvov{r}'{a}k and Postle. The chromatic polynomial of a graph is a notion that has been extensively studied since the early 20th century. The chromatic polynomial of graph $G$ is denoted $P(G,m)$, and it is equal to the number of proper $m$-colorings of $G$. In 2019, Kaul and Mudrock introduced an analogue of the chromatic polynomial for DP-coloring; specifically, the DP color function of graph $G$ is denoted $P_{DP}(G,m)$. Two fundamental questions posed by Kaul and Mudrock are: (1) For any graph $G$ with $n$ vertices, is it the case that $P(G,m)-P_{DP}(G,m)=O(m^{n-3})$ as $mightarrowinfty$? and (2) For every graph $G$, does there exist $p,NinmathbbN$ such that $P_{DP}(K_{p}veeG,m)=P(K_{p}veeG,m)$ whenever $mgeqN$? We show that the answer to both these questions is yes. In fact, we show the answer to (2) is yes even if we require $p=1$.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

list coloringchromatic polynomialDP-coloring

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Every planar graph is 5-choosable
• The list chromatic index of a bipartite multigraph
• Colorings and orientations of graphs
• The chromatic polynomial and list colorings
• When does the list-coloring function of a graph equal its chromatic polynomial
• On the number of list‐colorings
• Asymptotically good list-colorings
• Criticality, the list color function, and list coloring the Cartesian product of graphs
• The asymptotic behavior of the correspondence chromatic number
• Sharp Dirac's theorem for DP‐critical graphs
• Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
• The list chromatic number of graphs with small clique number
• DP-3-coloring of some planar graphs
• A sufficient condition for DP-4-colorability
• DP-colorings of graphs with high chromatic number
• The Johansson‐Molloy theorem for DP‐coloring
• Every planar graph without 4-cycles adjacent to two triangles is DP-4-colorable
• A note on a Brooks' type theorem for DP‐coloring
• A note on the DP-chromatic number of complete bipartite graphs
• Combinatorial Nullstellensatz and DP-coloring of graphs
• On the chromatic polynomial and counting DP-colorings of graphs
• List coloring and \(n\)-monophilic graphs.

Cited In (8)

• DP‐coloring Cartesian products of graphs
• DP color functions versus chromatic polynomials (II)
• DP color functions versus chromatic polynomials
• A deletion-contraction relation for the DP color function
• Non-chromatic-adherence of the DP color function via generalized theta graphs
• An algebraic approach for counting DP-3-colorings of sparse graphs
• The DP color function of joins and vertex-gluings of graphs
• The DP color function of clique-gluings of graphs

Recommendations

• On DP-coloring of graphs and multigraphs 👍 👎
• Color quantization by dynamic programming and principal analysis 👍 👎
• DP-colorings of hypergraphs 👍 👎
• DP color functions versus chromatic polynomials 👍 👎
• A deletion-contraction relation for the DP color function 👍 👎
• Non-chromatic-adherence of the DP color function via generalized theta graphs 👍 👎
• On DP‐coloring of digraphs 👍 👎
• DP color functions versus chromatic polynomials (II) 👍 👎

This page was built for publication: Answers to two questions on the DP color function

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