skip to main content


Title: Decomposing and Clique-Coloring (Diamond, Odd-Hole)-Free Graphs: DECOMPOSING AND CLIQUE-COLOURING (DIAMOND, ODD-HOLE)-FREE GRAPHS
NSF-PAR ID:
10027508
Author(s) / Creator(s):
 ;  
Publisher / Repository:
Wiley Blackwell (John Wiley & Sons)
Date Published:
Journal Name:
Journal of Graph Theory
Volume:
86
Issue:
1
ISSN:
0364-9024
Page Range / eLocation ID:
5 to 41
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Krattenthaler, Christian ; Thibon, Jean-Yves (Ed.)
  2. 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.

     
    more » « less