Premium
Decomposing and Clique‐Coloring (Diamond, Odd‐Hole)‐Free Graphs
Author(s) -
Chudnovsky Maria,
Lo Irene
Publication year - 2017
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.22110
Subject(s) - combinatorics , mathematics , induced subgraph , monochromatic color , graph , clique , clique number , discrete mathematics , vertex (graph theory) , physics , optics
A diamond is a graph on four vertices with exactly one pair of nonadjacent vertices, and an odd hole is an induced cycle of odd length greater than 3. If G and H are graphs, G is H‐free if no induced subgraph of G is isomorphic to H . A clique‐coloring of G is an assignment of colors to the vertices of G such that no inclusion‐wise maximal clique of size at least 2 is monochromatic. We show that every (diamond, odd‐hole)‐free graph is 3‐clique‐colorable, answering a question of Bacsó et al. (SIAM J Discrete Math 17(3) (2004), 361–376).
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom