The chromatic number of {   ISK  4   , diamond, bowtie}‐free graphs | Zendy

Chen Guantao | Zendy; Chen Yuan | Zendy; Cui Qing | Zendy; Feng Xing | Zendy; Liu Qinghai | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research