betaFeedback

WorksMathematics

Equality in the clique bound for critical graphs

Abstract

A graph is kk-critical if its chromatic number is kk and every proper subgraph is (k−1)(k-1)-colorable. Gao and Ma (2023) proved that every nn-vertex kk-critical graph with n>k≥4n > k \ge 4 contains at most n−k+3n - k + 3 cliques of size k−1k - 1, and asked which graphs attain this bound. We answer this question by showing that equality holds if and only if n−k+3n - k + 3 is odd and the graph is isomorphic to the join of a complete graph on k−3k - 3 vertices and a cycle of length n−k+3n - k + 3. More generally, for n>k≥3n>k\ge3, we determine when the size of a nonempty family of distinct (k−1)(k-1)-cliques in an nn-vertex kk-critical graph attains the upper bound s−k+3s-k+3, where ss is the number of vertices covered by the family. Equality holds if and only if the graph is such a join (with the complete part empty when k=3k = 3) and the family consists of all its (k−1)(k-1)-cliques.

Paper details

vlnc:W_2btvrere
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

ChatGPT

View statement
Looking for related papers…