Colouring Vertices of Triangle-Free Graphs

DOI10.1007/978-3-642-16926-7_18zbMath1309.68091OpenAlexW1594064077MaRDI QIDQ3057624

Konrad K. Dabrowski, Bernard Ries, Rajiv Raman, Vadim V. Lozin

Publication date: 16 November 2010

Published in: Graph Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-16926-7_18

zbMATH Keywords

polynomial-time algorithmtriangle-free graphsvertex colouringclique-width

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

4-Coloring H-Free Graphs When H Is Small ⋮ Adaptable and conflict colouring multigraphs with no cycles of length three or four ⋮ Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time ⋮ On the parameterized complexity of coloring graphs in the absence of a linear forest ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Recent developments on graphs of bounded clique-width
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• 3-colorability and forbidden subgraphs. I: Characterizing pairs
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• Triangle-free graphs and forbidden subgraphs
• A 4-colour problem for dense triangle-free graphs
• Three-colourability and forbidden subgraphs. II: Polynomial algorithms
• Bipartite graphs without a skew star
• Vertex colouring and forbidden subgraphs -- a survey
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• On the complexity of 4-coloring graphs without long induced paths
• THE CLIQUE-WIDTH OF BIPARTITE GRAPHS IN MONOGENIC CLASSES
• Three Complexity Results on Coloring P k -Free Graphs
• On graphs with polynomially solvable maximum-weight clique problem
• The NP-Completeness of Edge-Coloring
• A New Algorithm for Generating All the Maximal Independent Sets
• The 3-Colorability Problem on Graphs with Maximum Degree Four
• On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree

This page was built for publication: Colouring Vertices of Triangle-Free Graphs