Decomposing and clique-coloring (diamond, odd-hole)-free graphs

DOI10.1002/JGT.22110MaRDI QIDQ5360874zbMATH OpenOpenAlexFDO

Authors Maria Chudnovsky, Irene Lo

Publication date 26 September 2017

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/jgt.22110

zbMATH Keywords

perfect graphsdiamond-free graphsodd-hole-free graphsclique-coloring

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15) Perfect graphs (05C17)

Recommendations

• Complexity of clique-coloring odd-hole-free graphs
• Clique-coloring some classes of odd-hole-free graphs
• On graphs without a \(C_{4}\) or a diamond
• Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
• Colouring diamond-free graphs

Cited in

(21)

• Complexity-separating graph classes for vertex, edge and total colouring
• A linear-time algorithm for clique-coloring planar graphs
• scientific article; zbMATH DE number 6297711 (Why is no real title available?)
• Structural parameterizations of clique coloring
• List-coloring clique-hypergraphs of \(K_5\)-minor-free graphs strongly
• On the structure of (even hole, kite)-free graphs
• Recognition algorithm for diamond-free graphs
• Clique-coloring some classes of odd-hole-free graphs
• Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs
• \(K_{4}\)-free graphs with no odd holes
• On the complexity of local-equitable coloring of graphs
• Colouring diamond-free graphs
• 2-divisibility of some odd hole free graphs
• Perfect graphs of arbitrarily large clique-chromatic number
• Equitable clique-coloring in claw-free graphs with maximum degree at most 4
• Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
• A generalization of Grötzsch Theorem on the local-equitable coloring
• scientific article; zbMATH DE number 7559420 (Why is no real title available?)
• Colouring diamond-free graphs
• Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
• Complexity of clique-coloring odd-hole-free graphs

This page was built for publication: Decomposing and clique-coloring (diamond, odd-hole)-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5360874)