A Class of Three‐Colorable Triangle‐Free Graphs
Marko Radovanović, Kristina Vušković · Journal of Graph Theory · 2012
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 coloring algorithm, where n denotes the number of vertices and m the number of edges of the input graph.