TY - Journal Article
T1 - A Class of Three-Colorable Triangle-Free Graphs
JF - Journal of graph theory
VL - 72
IS - 4
SP - 430
EP - 439
A1 - Radovanovic, Marko
A2 - Vuskovic, Kristina
CY - HOBOKEN
PB - Blackwell Publishing Ltd
PY - 2013
UR - https://bonnus.ulb.uni-bonn.de/SummonRecord/FETCH-LOGICAL-13811-ec250cdc7fef721f3fe43a82d972d7570ddd1a55597845619b4fc57342a7dc50
N2 - 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.
KW - Algorithms
KW - clique cutsets
KW - coloring
KW - decomposition
KW - Graphs
KW - induced subdivisions of K2
KW - induced subdivisions of K2, 3
KW - Mathematics
KW - Physical Sciences
KW - Science & Technology
KW - star cutsets
KW - triangle-free graphs
KW - induced subdivisions of K2
KW - 3
KW - triangle-free graphs
KW - coloring
KW - decomposition
KW - star cutsets
KW - clique cutsets
ER -