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$.
@article{10_37236_3396,
author = {At{\'\i}lio G. Luiz and R. Bruce Richter},
title = {Remarks on a conjecture of {Bar\'at} and {T\'oth}},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {1},
doi = {10.37236/3396},
zbl = {1300.05105},
url = {http://geodesic.mathdoc.fr/articles/10.37236/3396/}
}
TY - JOUR
AU - Atílio G. Luiz
AU - R. Bruce Richter
TI - Remarks on a conjecture of Barát and Tóth
JO - The electronic journal of combinatorics
PY - 2014
VL - 21
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/3396/
DO - 10.37236/3396
ID - 10_37236_3396
ER -
%0 Journal Article
%A Atílio G. Luiz
%A R. Bruce Richter
%T Remarks on a conjecture of Barát and Tóth
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/3396/
%R 10.37236/3396
%F 10_37236_3396
Atílio G. Luiz; R. Bruce Richter. Remarks on a conjecture of Barát and Tóth. The electronic journal of combinatorics, Tome 21 (2014) no. 1. doi: 10.37236/3396
