Colouring vertices of triangle-free graphs without forests

DOI10.1016/j.disc.2011.12.012zbMath1237.05071OpenAlexW2077936668MaRDI QIDQ764907

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

Publication date: 16 March 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2011.12.012

zbMATH Keywords

polynomial-time algorithmtriangle-free graphsvertex colouringclique-width

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items (29)

List coloring in the absence of two subgraphs ⋮ Colouring diamond-free graphs ⋮ The weighted coloring problem for two graph classes characterized by small forbidden induced structures ⋮ Efficient solvability of the weighted vertex coloring problem for some hereditary class of graphs with $5$-vertex prohibitions ⋮ Bounding the Clique-Width of H-free Chordal Graphs ⋮ Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs ⋮ Colouring of graphs with Ramsey-type forbidden subgraphs ⋮ Bounding the mim‐width of hereditary graph classes ⋮ Clique‐width: Harnessing the power of atoms ⋮ Bounding clique-width via perfect graphs ⋮ The \(r\)-coloring and maximum stable set problem in hypergraphs with bounded matching number and edge size ⋮ Clique-Width for Graph Classes Closed under Complementation ⋮ On star and biclique edge-colorings ⋮ Coloring graphs without short cycles and long induced paths ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ The coloring problem for classes with two small obstructions ⋮ On the complexity of the minimum domination problem restricted by forbidden induced subgraphs of small size ⋮ Improved complexity results on \(k\)-coloring \(P_t\)-free graphs ⋮ Two complexity results for the vertex coloring problem ⋮ Bounding the Mim-Width of Hereditary Graph Classes. ⋮ The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs ⋮ List coloring in the absence of a linear forest ⋮ Bounding Clique-Width via Perfect Graphs ⋮ Two cases of polynomial-time solvability for the coloring problem ⋮ Bounding the clique-width of \(H\)-free split graphs ⋮ Unnamed Item ⋮ On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size ⋮ $(2P_2,K_4)$-Free Graphs are 4-Colorable ⋮ The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some new hereditary classes where graph coloring remains NP-hard
• The structure of bull-free graphs II and III -- a summary
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• MSOL partitioning problems on graphs of bounded treewidth and clique-width
• The Erdős-Hajnal conjecture for bull-free graphs
• Recent developments on graphs of bounded clique-width
• Paw-free graphs
• 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
• Upper bounds to the clique width of graphs
• On the complexity of 4-coloring graphs without long induced paths
• Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs
• On Coloring Graphs without Induced Forests
• THE CLIQUE-WIDTH OF BIPARTITE GRAPHS IN MONOGENIC CLASSES
• Coloring Bull-Free Perfectly Contractile Graphs
• 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
• Optimizing Bull-Free Perfect Graphs

This page was built for publication: Colouring vertices of triangle-free graphs without forests