Remarks on a conjecture of Barát and Tóth (Q405159)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Remarks on a conjecture of Barát and Tóth |
scientific article |
Statements
Remarks on a conjecture of Barát and Tóth (English)
0 references
4 September 2014
0 references
Summary: \textit{J. Barát} and \textit{G. Tóth} [ibid. 17, No. 1, Research Paper R73, 15 p. (2010; Zbl 1188.05051)] verified that any \(r\)-critical graph with at most \(r+4\) vertices has a subdivision of \(K_r\). Based in this result, the authors conjectured that, for every positive integer \(c\), there exists a bound \(r(c)\) such that for any \(r\), where \(r \geq r(c)\), any \(r\)-critical graph on \(r+c\) vertices has a subdivision of \(K_r\). In this note, we verify the validity of this conjecture for \(c=5\), and show counterexamples for all \(c \geq 6\).
0 references
colour-critical graphs
0 references
Hajós conjecture
0 references
Albertson conjecture
0 references