错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Bounds for DP Color Function and Canonical Labelings

  • Ziqing Li,
  • Yan Yang

摘要

The DP-coloring is a generalization of the list coloring, introduced by Dvořák and Postle. Let \({\mathcal {H}}=(L,H)\) H = ( L , H ) be a cover of a graph G and \(P_{DP}(G,{\mathcal {H}})\) P DP ( G , H ) be the number of \({\mathcal {H}}\) H -colorings of G. The DP color function \(P_{DP}(G,m)\) P DP ( G , m ) of G, introduced by Kaul and Mudrock, is the minimum value of \(P_{DP}(G,{\mathcal {H}})\) P DP ( G , H ) where the minimum is taken over all possible m-fold covers \({\mathcal {H}}\) H of G. For the family of n-vertex connected graphs, one can deduce that trees maximize the DP color function, from two results of Kaul and Mudrock. In this paper we obtain tight upper bounds for the DP color function of n-vertex 2-connected graphs. Another concern in this paper is the canonical labeling in a cover. It is well known that if an m-fold cover \({\mathcal {H}}\) H of a graph G has a canonical labeling, then \(P_{DP}(G,{\mathcal {H}})=P(G,m)\) P DP ( G , H ) = P ( G , m ) in which P(Gm) is the chromatic polynomial of G. However the converse statement of this conclusion is not always true. We give examples that for some m and G, there exists an m-fold cover \({\mathcal {H}}\) H of G such that \(P_{DP}(G,{\mathcal {H}})=P(G,m)\) P DP ( G , H ) = P ( G , m ) , but \({\mathcal {H}}\) H has no canonical labelings. We also prove that when G is a unicyclic graph or a theta graph, for each \(m\ge 3\) m 3 , if \(P_{DP}(G,{\mathcal {H}})=P (G,m)\) P DP ( G , H ) = P ( G , m ) , then \({\mathcal {H}}\) H has a canonical labeling.