Please use this identifier to cite or link to this item:
https://research.matf.bg.ac.rs/handle/123456789/219| Title: | The structure of (theta, pyramid, 1-wheel, 3-wheel)-free graphs | Authors: | Boncompagni, Valerio Radovanović, Marko Vušković, Kristina |
Affiliations: | Algebra and Mathematical Logic | Keywords: | 2-amalgams;bisimplicial cutsets;clique cutsets;decomposition;recognition algorithm;structure;vertex coloring | Issue Date: | 1-Apr-2019 | Journal: | Journal of Graph Theory | Abstract: | In this paper, we study the class of graphs C defined by excluding the following structures as induced subgraphs: theta, pyramid, 1-wheel, and 3-wheel. We describe the structure of graphs in C, and we give a polynomial-time recognition algorithm for this class. We also prove that K4 -free graphs in C are 4-colorable. We remark that C includes the class of chordal graphs, as well as the class of line graphs of triangle-free graphs. |
URI: | https://research.matf.bg.ac.rs/handle/123456789/219 | ISSN: | 03649024 | DOI: | 10.1002/jgt.22415 |
| Appears in Collections: | Research outputs |
Show full item record
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.