Remarks on a conjecture of Barát and Tóth (Q405159): Difference between revisions

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\).