Remarks on a Conjecture of Barát and Tóth

Abstract

In 2010,  Barát and Tóth 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$.