Decomposing and Clique-Coloring (Diamond, Odd-Hole)-Free Graphs: DECOMPOSING AND CLIQUE-COLOURING (DIAMOND, ODD-HOLE)-FREE GRAPHS
More Like this
-
Abstract A graph is said to be ‐free if it does not contain any subdivision of as an induced subgraph. Lévêque, Maffray and Trotignon conjectured that every ‐free graph is 4‐colorable. In this paper, we show that this conjecture is true for the class of {, diamond, bowtie}‐free graphs, where a diamond is the graph obtained from by removing one edge and a bowtie is the graph consisting of two triangles with one vertex identified.