@Journal Article{Summon-FETCH-LOGICAL-13811-ec250cdc7fef721f3fe43a82d972d7570ddd1a55597845619b4fc57342a7dc50,
title = {A Class of Three-Colorable Triangle-Free Graphs},
author = {Radovanovic, Marko} and {Vuskovic, Kristina},
journal = {Journal of graph theory},
address = {HOBOKEN},
publisher = {Blackwell Publishing Ltd},
year = {2013},
keywords ={Algorithms, clique cutsets, coloring, decomposition, Graphs, induced subdivisions of K2, induced subdivisions of K2, 3, Mathematics, Physical Sciences, Science & Technology, star cutsets, triangle-free graphs, induced subdivisions of K2, 3, triangle-free graphs, coloring, decomposition, star cutsets, clique cutsets},
issn ={0364-9024, 1097-0118},
abstract = {The chromatic number of a triangle‐free graph can be arbitrarily large. In this article, we show that if all subdivisions of K2, 3 are also excluded as induced subgraphs, then the chromatic number becomes bounded by 3. We give a structural characterization of this class of graphs, from which we derive an O(nm) coloring algorithm, where n denotes the number of vertices and m the number of edges of the input graph.
},
}