Clique partitions and distinct color sets in list colorings
Abstract
For an n-vertex graph G and an integer m≥ n, let f'(G,m) be the minimum number of distinct color sets used by proper colorings from m-element lists that are disjoint at distinct nonadjacent vertices. A clique-partition assignment gives a common list to the vertices of each part of a clique partition and uses disjoint lists on different parts. In this paper, we construct a graph on 20 vertices for which these assignments do not attain f'(G,20), and a fixed graph on 25 vertices for which they fail to attain the minimum for every allowed list size. For every triangle-free graph G on n≥2 vertices, we prove f'(G,m)=binomm2ν(G)mn−2ν(G) (m≥ n), where ν(G) is the size of a maximum matching, and characterize all minimizing assignments in terms of maximum matchings. For clique blow-ups of each fixed odd cycle of length at least five, we determine the minimum up to constant factors uniformly over the blow-up size and all allowed list sizes, and obtain an exponential separation from the clique-partition value. We also prove that a noncomplete graph G satisfies f'(G,n)=n2 if and only if all edges of its complement have a common endpoint. These results disprove the general clique-partition conjecture of Gravier, Maffray, and Mohar (\emph{Discrete Mathematics}, 2003) and its extension by Wu and Zhang (\emph{Applied Mathematics Letters}, 2006), while establishing both triangle-free conjectures.
Related
BibTeX
@misc{yue2026clique,
title = {{Clique partitions and distinct color sets in list colorings}},
author = {Jun Yue},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.07924},
eprint = {2611.07924},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.07924},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Clique partitions and distinct color sets in list colorings
AU - Jun Yue
PY - 2026
DA - 2026/11/05
PB - arXiv
DO - 10.48550/arxiv.2611.07924
UR - https://arxiv.org/abs/2611.07924
AB - For an n-vertex graph G and an integer m≥ n, let f'(G,m) be the minimum number of distinct color sets used by proper colorings from m-element lists that are disjoint at distinct nonadjacent vertices. A clique-partition assignment gives a common list to the vertices of each part of a clique partition and uses disjoint lists on different parts. In this paper, we construct a graph on 20 vertices for which these assignments do not attain f'(G,20), and a fixed graph on 25 vertices for which they fail to attain the minimum for every allowed list size. For every triangle-free graph G on n≥2 vertices, we prove f'(G,m)=binomm2^ν(G)m^n−2ν(G) (m≥ n), where ν(G) is the size of a maximum matching, and characterize all minimizing assignments in terms of maximum matchings. For clique blow-ups of each fixed odd cycle of length at least five, we determine the minimum up to constant factors uniformly over the blow-up size and all allowed list sizes, and obtain an exponential separation from the clique-partition value. We also prove that a noncomplete graph G satisfies f'(G,n)=n^2 if and only if all edges of its complement have a common endpoint. These results disprove the general clique-partition conjecture of Gravier, Maffray, and Mohar (\emph{Discrete Mathematics}, 2003) and its extension by Wu and Zhang (\emph{Applied Mathematics Letters}, 2006), while establishing both triangle-free conjectures.
ER -