Colouring \((P_r + P_s)\)-free graphs

DOI10.1007/s00453-020-00675-wzbMath1441.68095arXiv1804.11091OpenAlexW3123316771MaRDI QIDQ2182090

Tomáš Masařík, Jana Novotná, Tereza Klimošová, Daniël Paulusma, Josef Malík, Veronika Slívová

Publication date: 21 May 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1804.11091

zbMATH Keywords

vertex colouring\(H\)-free graphlinear forest

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)

Related Items (10)

The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable ⋮ Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter ⋮ 3-colouring \(P_t\)-free graphs without short odd cycles ⋮ On algorithmic applications of sim-width and mim-width of \((H_1,H_2)\)-free graphs ⋮ List 3-coloring graphs with no induced \(P_6 + rP_3\) ⋮ List \(k\)-colouring \(P_t\)-free graphs: a mim-width perspective ⋮ Colouring graphs of bounded diameter in the absence of small cycles ⋮ On 3-coloring of \((2P_4,C_5)\)-free graphs ⋮ On 3-coloring of \((2P_4,C_5)\)-free graphs ⋮ Injective colouring for H-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• Updating the complexity status of coloring graphs without a fixed induced linear forest
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• The complexity of colouring problems on dense graphs
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• Three-colourability and forbidden subgraphs. II: Polynomial algorithms
• On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs
• Independent feedback vertex set for \(P_5\)-free graphs
• Three-coloring and list three-coloring of graphs without induced paths on seven vertices
• Vertex colouring and forbidden subgraphs -- a survey
• Three complexity results on coloring \(P_k\)-free graphs
• List 3-coloring graphs with no induced \(P_6 + rP_3\)
• Closing complexity gaps for coloring problems on \(H\)-free graphs
• List coloring in the absence of a linear forest
• \(H\)-colouring \(P_t\)-free graphs in subexponential time
• On the complexity of 4-coloring graphs without long induced paths
• Open Problems on Graph Coloring for Special Graph Classes
• 4‐Coloring P ₆ ‐Free Graphs with No Induced 5‐Cycles
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• The NP-Completeness of Edge-Coloring
• Graph colorings with local constraints -- a survey
• Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
• 3-Colorable Subclasses of $P_8$-Free Graphs
• NP completeness of finding the chromatic index of regular graphs
• Colouring (P_r+P_s)-Free Graphs
• Four-coloring P₆-free graphs
• Polynomial-time algorithm for Maximum Weight Independent Set on P₆-free graphs

This page was built for publication: Colouring \((P_r + P_s)\)-free graphs