Premium
A Class of Three‐Colorable Triangle‐Free Graphs
Author(s) -
Radovanović Marko,
Vušković Kristina
Publication year - 2013
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21651
Subject(s) - combinatorics , mathematics , chromatic scale , bounded function , graph , discrete mathematics , 1 planar graph , class (philosophy) , chordal graph , computer science , artificial intelligence , mathematical analysis
The chromatic number of a triangle‐free graph can be arbitrarily large. In this article, we show that if all subdivisions of K 2, 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 ( n m ) coloring algorithm, where n denotes the number of vertices and m the number of edges of the input graph.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom