Please use this identifier to cite or link to this item:
https://research.matf.bg.ac.rs/handle/123456789/215
Title: | A class of three-colorable triangle-free graphs | Authors: | Radovanović, Marko Vuškovic̈, Kristina |
Affiliations: | Algebra and Mathematical Logic | Keywords: | clique cutsets;coloring;decomposition;star cutsets;triangle-free graphs | Issue Date: | 1-Apr-2013 | Journal: | Journal of Graph Theory | 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. © 2012 Wiley Periodicals, Inc. |
URI: | https://research.matf.bg.ac.rs/handle/123456789/215 | ISSN: | 03649024 | DOI: | 10.1002/jgt.21651 |
Appears in Collections: | Research outputs |
Show full item record
SCOPUSTM
Citations
6
checked on Dec 19, 2024
Page view(s)
12
checked on Dec 24, 2024
Google ScholarTM
Check
Altmetric
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.