On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs

DOI10.1016/j.ipl.2018.02.003zbMath1476.68200arXiv1712.02447OpenAlexW2787859587MaRDI QIDQ1707976

Konrad K. Dabrowski, Daniël Paulusma

Publication date: 4 April 2018

Published in: Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

pathscomputational complexitycolouringhereditary graph class\((H_1,H_2)\)-free

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable, Colouring \((P_r + P_s)\)-free graphs, Near optimal colourability on hereditary graph families, Polynomial cases for the vertex coloring problem, The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs, Colouring (P_r+P_s)-Free Graphs, Colouring square-free graphs without long induced paths

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Complexity of coloring graphs without paths and cycles
• Vertex coloring of graphs with few obstructions
• Colouring of graphs with Ramsey-type forbidden subgraphs
• Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
• The coloring problem for classes with two small obstructions
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• Two complexity results for the vertex coloring problem
• Some new hereditary classes where graph coloring remains NP-hard
• On algorithms for (\(P_5\), gem)-free graphs
• The strong perfect graph theorem
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
• Coloring vertices of claw-free graphs in three colors
• Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
• Colouring diamond-free graphs
• Solving the clique cover problem on (bull, \(C_4\))-free graphs
• List coloring in the absence of two subgraphs
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• Choosability of P 5-Free Graphs
• Colouring square-free graphs without long induced paths.
• The NP-Completeness of Edge-Coloring
• Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
• The complexity of satisfiability problems
• Two cases of polynomial-time solvability for the coloring problem