On the chromatic number of (\(P_6\), diamond)-free graphs
From MaRDI portal
Publication:2413634
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
Related Items (7)
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 ⋮ 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
