DP color functions versus chromatic polynomials

DOI10.1016/J.AAM.2021.102301MaRDI QIDQ2070081zbMATH OpenOpenAlexFDO

Authors Yan Yang, F. M. Dong

Publication date 21 January 2022

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

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

zbMATH Keywords

chromatic polynomial cycle DP color function DP-coloring listing coloring proper coloring spanning tree

Mathematics Subject Classification ID

Trees (05C05) Enumeration in graph theory (05C30) Graph polynomials (05C31)

Abstract: For any graph

G

, the chromatic polynomial of

G

is the function

P (G, m)

which counts the number of proper

m

-colorings of

G

for each positive integer

m

. The DP color function

P_{D P} (G, m)

of

G

, introduced by Kaul and Mudrock in 2019, is a generalization of

P (G, m)

with

P_{D P} (G, m) l e P (G, m)

for each positive integer

m

. Let

P_{D P} (G) a p p r o x P (G)

(resp.

P_{D P} (G) < P (G)

) denote the property that

P_{D P} (G, m) = P (G, m)

(resp.

P_{D P} (G, m) < P (G, m)

) holds for sufficiently large integers

m

.It is an interesting problem of finding graphs

G

for which

P_{D P} (G) a p p r o x P (G)

(resp.

P_{D P} (G, m) < P (G, m)

) holds. Kaul and Mudrock showed that if

G

has an even girth, then

P_{D P} (G) < P (G)

and Mudrock and Thomason recently proved that

P_{D P} (G) a p p r o x P (G)

holds for each graph

G

which has a dominating vertex. We shall generalize their results in this article. For each edge

e

in

G

, let

e l l (e) = i n f t y

if

e

is a bridge of

G

, and let

e l l (e)

be the length of a shortest cycle in

G

containing

e

otherwise. We first show that if

e l l (e)

is even for some edge

e

in

G

, then

P_{D P} (G) < P (G)

holds. However, the converse statement of this conclusion fails with infinitely many counterexamples. We then prove that

P_{D P} (G) a p p r o x P (G)

holds for every graph

G

that contains a spanning tree

T

such that for each

e i n E (G) s e t m i n u s E (T)

,

e l l (e)

is odd and

e

contained in a cycle

C

of length

e l l (e)

with the property that

e l l (e^{'}) < e l l (e)

for each

e^{'} i n E (C) s e t m i n u s (E (T) c u p e)

. Some open problems are proposed in this article.

Recommendations

Cites work

Cited in

(14)

This page was built for publication: DP color functions versus chromatic polynomials

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