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)+\chi (G)\le |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)|-\chi (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\ge 2$ yields $lcc(G)+\chi (G)\le |V(G)|+3-m$, which improves the general bound when $m\ge 3$, and determine the restrictions imposed by equality on deletion of an induced $2K_2$.