On the edge-density of 4-critical graphs (Q624211): Difference between revisions

A graph \(G\) is called critical if, for all proper subgraphs \(H\) of \(G\), the chromatic number of \(H\) is less than the chromatic number of \(G\); it is called \(k\)-critical if it is critical and its chromatic number is \(k\). For \(k\geq 4\), \textit{T. Gallai} [Publ. Math. Inst. Hung. Acad. Sci., Ser. A 8, 165--192 (1963; Zbl 0121.18401)] conjectured that every \(k\)-critical graph with \(n\) vertices has at least \(\frac{k-1}{2}n+\frac{(k-3)(n-k)}{2(k-1)}\) edges. The low-vertex subgraph of a \(k\)-critical graph is the subgraph induced by the vertices of minimum degree, i.e., the vertices of degree \(k-1\). The authors prove Gallai's conjecture for \(4\)-critical graphs whose low-vertex subgraph is connected: Every \(n\)-vertex \(4\)-critical graph in which the subgraph induced by vertices of degree \(3\) is connected has at least \(\frac{5}{3}n-\frac{2}{3}\) edges.