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

DOI10.1016/J.IPL.2018.02.003zbMATH Open1476.68200arXiv1712.02447OpenAlexW2787859587MaRDI QIDQ1707976FDOQ1707976

Konrad Dabrowski, Daniël Paulusma

Publication date: 4 April 2018

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

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.

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)

Cites Work

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

Cited In (9)

• 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
• 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)