arXiv Analytics

Sign in

arXiv:1407.6531 [math.CO]AbstractReferencesReviewsResources

On triangle-free graphs that do not contain a subdivision of the complete graph on four vertices as an induced subgraph

Nicolas Trotignon, Kristina Vušković

Published 2014-07-24, updated 2014-07-25Version 2

We prove a decomposition theorem for the class of triangle-free graphs that do not contain a subdivision of the complete graph on four vertices as an induced subgraph. We prove that every graph of girth at least~5 in this class is 3-colorable.

Categories: math.CO
Related articles: Most relevant | Search more
arXiv:1010.1455 [math.CO] (Published 2010-10-07)
Nim on the Complete Graph
arXiv:1204.3709 [math.CO] (Published 2012-04-17, updated 2013-10-29)
Decompositions of complete graphs into cycles of arbitrary lengths
arXiv:1311.2785 [math.CO] (Published 2013-11-12, updated 2014-05-14)
On the Buratti-Horak-Rosa Conjecture about Hamiltonian Paths in Complete Graphs

Links

Toolbox