A Class of Three-Colorable Triangle-Free Graphs

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 deri...

Full description

Saved in:
Bibliographic details
Volume: 72
Main Author: Radovanovic, Marko
Vuskovic, Kristina
Format: Journal Article
Language: English
Zielgruppe: Academic
Place of publication: HOBOKEN Blackwell Publishing Ltd 01.04.2013
WILEY-BLACKWELL
Wiley Subscription Services, Inc
published in: Journal of graph theory Vol. 72; no. 4; pp. 430 - 439
ORCID: 0000-0002-6990-1793
Data of publication: 2013-04
ISSN: 0364-9024
1097-0118
EISSN: 1097-0118
Discipline: Mathematics
Bibliography: Partially supported by Serbian Ministry for Education and Science grants III44006 and 174033, Serbian-French Technology Co-Operation grant Pavle Savić 2010-2011, and EPSRC grant EP/H021426/1.
Partially supported by Serbian Ministry for Education and Science grants III44006 and 174033, Serbian‐French Technology Co‐Operation grant Pavle Savić 2010‐2011, and EPSRC grant EP/H021426/1.
Subjects:
3
Online Access: available in Bonn?
CODEN: JGTHDO
Database: Istex
Web of Knowledge
Science Citation Index Expanded
Web of Science
Web of Science - Science Citation Index Expanded - 2013
CrossRef
Academic OneFile (A&I only)
Database information Databases - DBIS