Local Clique Covers and Chromatic Number
Abstract
The local clique cover number lcc(G) is the minimum valency of an edge-clique cover of G. We prove the conjectured inequality lcc(G)+χ(G)≤ |V(G)|+1 for every finite simple graph. The proof gives an independent set improvement of an endpoint-cover estimate and applies the resulting construction to an induced four-vertex path. We further prove that the cover can be chosen so that every nonuniversal vertex has valency at most $|V(G)|-χ(G)$. Consequently, every graph attaining equality has a universal vertex. The stronger statement follows by reducing a counterexample of minimum order to a prime double-critical graph and refining the induced path extension. We also show that an induced matching of size m≥2 yields lcc(G)+χ(G)≤ |V(G)|+3−m, which improves the general bound when m≥3, and determine the restrictions imposed by equality on deletion of an induced 2K2.
Related
- Bounded chromatic number of graphs with small clique number and large minimum degree
- Complete characterization of disconnected one-point unions of cycles with local antimagic chromatic number 2
- Necessary and sufficient conditions of a class of bipartite graphs with local antimagic chromatic number 2 - an algebraic approach
- Local Antimagic Chromatic Number of Middle Graph and Direct Product of Graphs
- Clique and chromatic numbers of graph powers: spectral bounds and anticodes
BibTeX
@misc{davoodi2026local,
title = {{Local Clique Covers and Chromatic Number}},
author = {Akbar Davoodi},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.07988},
eprint = {2609.07988},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.07988},
}
RIS
TY - UNPB
TI - Local Clique Covers and Chromatic Number
AU - Akbar Davoodi
PY - 2026
DA - 2026/09/07
PB - arXiv
DO - 10.48550/arxiv.2609.07988
UR - https://arxiv.org/abs/2609.07988
AB - The local clique cover number lcc(G) is the minimum valency of an edge-clique cover of G. We prove the conjectured inequality lcc(G)+χ(G)≤ |V(G)|+1 for every finite simple graph. The proof gives an independent set improvement of an endpoint-cover estimate and applies the resulting construction to an induced four-vertex path. We further prove that the cover can be chosen so that every nonuniversal vertex has valency at most $|V(G)|-χ(G)$. Consequently, every graph attaining equality has a universal vertex. The stronger statement follows by reducing a counterexample of minimum order to a prime double-critical graph and refining the induced path extension. We also show that an induced matching of size m≥2 yields lcc(G)+χ(G)≤ |V(G)|+3−m, which improves the general bound when m≥3, and determine the restrictions imposed by equality on deletion of an induced 2K_2.
ER -