On colouring (2P₂,H)-free and (P₅,H)-free graphs

DOI10.1016/J.IPL.2018.02.003MaRDI QIDQ1707976zbMATH OpenOpenAlexFDO

Authors Konrad Dabrowski, Daniël Paulusma

Publication date 4 April 2018

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

computational complexitypathscolouringhereditary graph class\((H_1,H_2)\)-free

Mathematics Subject Classification ID

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

Abstract: The Colouring problem asks whether the vertices of a graph can be coloured with at most $k$ colours for a given integer $k$ in such a way that no two adjacent vertices receive the same colour. A graph is $(H_1,H_2)$-free if it has no induced subgraph isomorphic to $H_1$ or $H_2$. A connected graph $H_1$ is almost classified if Colouring on $(H_1,H_2)$-free graphs is known to be polynomial-time solvable or NP-complete for all but finitely many connected graphs $H_2$. We show that every connected graph $H_1$ apart from the claw $K_{1,3}$ and the $5$-vertex path $P_5$ is almost classified. We also prove a number of new hardness results for Colouring on $(2P_2,H)$-free graphs. This enables us to list all graphs $H$ for which the complexity of Colouring is open on $(2P_2,H)$-free graphs and all graphs $H$ for which the complexity of Colouring is open on $(P_5,H)$-free graphs. In fact we show that these two lists coincide. Moreover, we show that the complexities of Colouring for $(2P_2,H)$-free graphs and for $(P_5,H)$-free graphs are the same for all known cases.

Recommendations

• Colouring \((P_r + P_s)\)-free graphs
• Colouring of graphs with Ramsey-type forbidden subgraphs
• Colouring of graphs with Ramsey-type forbidden subgraphs
• 4-coloring \(H\)-free graphs when \(H\) is small
• Closing complexity gaps for coloring problems on \(H\)-free graphs

Cites work

• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• scientific article; zbMATH DE number 3503283 (Why is no real title available?)
• scientific article; zbMATH DE number 2044943 (Why is no real title available?)
• A survey on the computational complexity of coloring graphs with forbidden subgraphs
• Choosability of P 5-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
• Colouring diamond-free graphs
• Colouring of graphs with Ramsey-type forbidden subgraphs
• Colouring square-free graphs without long induced paths
• Complexity of coloring graphs without paths and cycles
• Determining the chromatic number of triangle-free 2P₃-free graphs in polynomial time
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• List coloring in the absence of two subgraphs
• On algorithms for (P₅, gem)-free graphs
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
• Solving the clique cover problem on (bull, \(C_4\))-free graphs
• Some new hereditary classes where graph coloring remains NP-hard
• The NP-Completeness of Edge-Coloring
• The coloring problem for classes with two small obstructions
• The complexity of satisfiability problems
• The strong perfect graph theorem
• Two cases of polynomial-time solvability for the coloring problem
• Two complexity results for the vertex coloring problem
• Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
• Vertex coloring of graphs with few obstructions

Cited in

(14)

• Colouring of graphs with Ramsey-type forbidden subgraphs
• Colouring of graphs with Ramsey-type forbidden subgraphs
• The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable
• 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
• Colouring (P_r+P_s)-Free Graphs
• Near optimal colourability on hereditary graph families
• On color-critical (\(P_5\),\(\operatorname{co-}P_5\))-free graphs
• Colouring diamond-free graphs
• On 3-coloring of \((2P_4,C_5)\)-free graphs
• Classifying \(k\)-edge colouring for \(H\)-free graphs
• Polynomial cases for the vertex coloring problem
• Making an H $H$‐free graph k $k$‐colorable

This page was built for publication: On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs

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