Colouring Vertices of Triangle-Free Graphs
From MaRDI portal
Publication:3057624
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
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