On the edge-density of 4-critical graphs (Q624211): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 09:18, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the edge-density of 4-critical graphs |
scientific article |
Statements
On the edge-density of 4-critical graphs (English)
0 references
8 February 2011
0 references
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.
0 references
graph colouring
0 references
critical graph
0 references
edge-density
0 references
Gallai's conjecture
0 references