Premium
The chromatic number of { ISK 4 , diamond, bowtie}‐free graphs
Author(s) -
Chen Guantao,
Chen Yuan,
Cui Qing,
Feng Xing,
Liu Qinghai
Publication year - 2021
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.22631
Subject(s) - combinatorics , mathematics , graph , subdivision , vertex (graph theory) , conjecture , chromatic scale , induced subgraph , discrete mathematics , archaeology , history
A graph is said to be ISK 4 ‐free if it does not contain any subdivision of K 4 as an induced subgraph. Lévêque, Maffray and Trotignon conjectured that every ISK 4 ‐free graph is 4‐colorable. In this paper, we show that this conjecture is true for the class of { ISK 4 , diamond, bowtie}‐free graphs, where a diamond is the graph obtained from K 4 by removing one edge and a bowtie is the graph consisting of two triangles with one vertex identified.