期刊
EUROPEAN JOURNAL OF COMBINATORICS
卷 118, 期 -, 页码 -出版社
ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD
DOI: 10.1016/j.ejc.2023.103890
关键词
-
类别
DP-coloring is a generalization of list coloring that calculates the minimum number of DP-colorings in a graph's cover. This paper presents a new approach to compute the DP-coloring number and provides improved bounds compared to existing methods. It also proves that the DP-color function is not chromatic adherent.
DP-coloring (or correspondence coloring) is a generalization of list coloring that has been widely studied since its introduction by Dvorak and Postle in 2015. As the analogue of the chromatic polynomial of a graph G, P(G, m), and the list color function, Pl(G, m), the DP-color function of G, denoted by P-DP(G, m), counts the minimum number of DP-colorings over all possible m-fold covers. It follows that P-DP(G, m) <= P-l(G, m) <= P(G, m). A function f is chromatic-adherent if for every graph G, f(G, a) = P(G, a) for some a >= chi(G) implies that f(G, m) = P(G, m) for all m >= a. It is known that the DP-color function is not chromatic adherent, but there are only two known graphs that demonstrate this. Suppose G is an n-vertex graph and H is a 3-fold cover of G. In this paper we associate with H a polynomial f(G,H) is an element of F-3[x(1), ... , x(n)] so that the number of non-zeros of f(G,H) equals the number of H-colorings of G. We then use a well-known result of Alon and Furedi on the number of non-zeros of a polynomial to establish a non-trivial lower bound on P-DP(G, 3) when 2n > |E(G)|. An easy consequence of this is that P-DP(G, 3) >= 3(n/6) for every n-vertex planar graph G of girth at least 5, improving the previously known bounds on both P-DP(G, 3) and P-l(G, 3). Finally, we use this bound to show that there are infinitely many graphs that demonstrate the non-chromatic-adherence of the DP-color function.(c) 2023 Elsevier Ltd. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据