We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
The chromatic number of {ISK4, diamond, bowtie}‐free graphs.
- Authors
Chen, Guantao; Chen, Yuan; Cui, Qing; Feng, Xing; Liu, Qinghai
- Abstract
A graph is said to be ISK4‐free if it does not contain any subdivision of K4 as an induced subgraph. Lévêque, Maffray and Trotignon conjectured that every ISK4‐free graph is 4‐colorable. In this paper, we show that this conjecture is true for the class of {ISK4, diamond, bowtie}‐free graphs, where a diamond is the graph obtained from K4 by removing one edge and a bowtie is the graph consisting of two triangles with one vertex identified.
- Subjects
DIAMONDS; TRIANGLES; LOGICAL prediction
- Publication
Journal of Graph Theory, 2021, Vol 96, Issue 4, p554
- ISSN
0364-9024
- Publication type
Article
- DOI
10.1002/jgt.22631