On the chromatic number of (\(P_6\), diamond)-free graphs

DOI10.1007/S00373-018-1905-9zbMath1397.05066OpenAlexW2803423204MaRDI QIDQ2413634

Suchismita Mishra, T. Karthick

Publication date: 14 September 2018

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-018-1905-9

zbMATH Keywords

chromatic numberclique numberdiamond-free graphsgraph classes\(P_6\)-free graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (8)

Colouring graphs with no induced six-vertex path or diamond ⋮ THE CHROMATIC NUMBER OF -FREE GRAPHS ⋮ An optimal χ‐bound for (P6, diamond)‐free graphs ⋮ Improved bounds on the chromatic number of (\(P_5\), flag)-free graphs ⋮ Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey ⋮ Strong cliques in diamond-free graphs ⋮ Linear χ -binding functions for some classes of ( P ₃ ∪ P ₂ )-free graphs ⋮ Colouring graphs with no induced six-vertex path or diamond

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Clique separator decomposition of hole-free and diamond-free graphs and algorithmic consequences
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• Maximal cliques in \(\{P_{2} \cup P_{3},C_{4}\}\)-free graphs
• Updating the complexity status of coloring graphs without a fixed induced linear forest
• The strong perfect graph theorem
• Bisimplicial vertices in even-hole-free graphs
• \(K_{4}\)-free graphs with no odd holes
• Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
• Coloring perfect \((K_ 4\)-e)-free graphs
• Coloring the hypergraph of maximal cliques of a graph with no long path
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• Triangle-free graphs and forbidden subgraphs
• Three-colourability and forbidden subgraphs. II: Polynomial algorithms
• Colouring of \((P_3 \cup P_2)\)-free graphs
• Algorithmic graph theory and perfect graphs
• Vertex colouring and forbidden subgraphs -- a survey
• Triangle-free \(2P_3\)-free graphs are 4-colorable
• The chromatic number of \(\{P_5,K_4\}\)-free graphs
• Vizing bound for the chromatic number on some graph classes
• Forbidden Subgraphs and 3-Colorings
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• Perfect coloring and linearly χ-boundP6-free graphs
• Obstructions for three-coloring graphs with one forbidden induced subgraph
• Reducibility among Combinatorial Problems
• Hereditary graph classes: When the complexities of <scp>coloring</scp> and <scp>clique cover</scp> coincide
• Colouring Diamond-free Graphs.
• Sur le coloriage des graphs

This page was built for publication: On the chromatic number of (\(P_6\), diamond)-free graphs