Local Clique Covers and Chromatic Number
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)\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)|-χ(G)$. Consequently, every graph attaining equality has a universal vertex. The stronger statement follows by reducing a counterexample of minimum order to…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.07988
curl -X POST /api/v1/records/arxiv/2609.07988/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.07988/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'