Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time

DOI10.1016/J.TCS.2011.12.076zbMath1241.05030OpenAlexW1982039109MaRDI QIDQ417995

Daniël Paulusma, Jian Song, Petr A. Golovach, Hajo J. Broersma

Publication date: 14 May 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.12.076

zbMATH Keywords

chromatic numbertriangle-freeforbidden induced subgraph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (21)

4-Coloring H-Free Graphs When H Is Small ⋮ List coloring in the absence of two subgraphs ⋮ Vertex coloring of graphs with few obstructions ⋮ Colouring diamond-free graphs ⋮ Colouring square-free graphs without long induced paths. ⋮ Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs ⋮ Colouring of graphs with Ramsey-type forbidden subgraphs ⋮ On the power of threshold-based algorithms for detecting cycles in the \textsc{CONGEST} model ⋮ On the power of threshold-based algorithms for detecting cycles in the CONGEST model ⋮ On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs ⋮ Coloring graphs without short cycles and long induced paths ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ On the parameterized complexity of coloring graphs in the absence of a linear forest ⋮ Polynomial cases for the vertex coloring problem ⋮ Maximum regular induced subgraphs in \(2P_3\)-free graphs ⋮ List coloring in the absence of a linear forest ⋮ Sparse regular induced subgraphs in \(2P_3\)-free graphs ⋮ Coloring Graphs without Short Cycles and Long Induced Paths ⋮ Updating the complexity status of coloring graphs without a fixed induced linear forest ⋮ List Coloring in the Absence of a Linear Forest ⋮ Colouring square-free graphs without long induced paths

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• Triangle-free graphs and forbidden subgraphs
• Vertex colouring and forbidden subgraphs -- a survey
• Linear time solvable optimization problems on graphs of bounded clique-width
• On the complexity of 4-coloring graphs without long induced paths
• Colouring Vertices of Triangle-Free Graphs
• THE CLIQUE-WIDTH OF BIPARTITE GRAPHS IN MONOGENIC CLASSES
• Three Complexity Results on Coloring P k -Free Graphs
• A Certifying Algorithm for 3-Colorability of P 5-Free Graphs
• On graphs with polynomially solvable maximum-weight clique problem
• A New Algorithm for Generating All the Maximal Independent Sets
• Graph colorings with local constraints -- a survey

This page was built for publication: Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time