Colouring vertices of triangle-free graphs without forests

DOI10.1016/j.disc.2011.12.012zbMath1237.05071MaRDI 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 algorithm; triangle-free graphs; vertex colouring; clique-width

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C15: Coloring of graphs and hypergraphs

Related Items

Unnamed Item, On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size, Clique-Width for Graph Classes Closed under Complementation, $(2P_2,K_4)$-Free Graphs are 4-Colorable, Two cases of polynomial-time solvability for the coloring problem, Bounding the clique-width of \(H\)-free split graphs, Colouring of graphs with Ramsey-type 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, The weighted coloring problem for two graph classes characterized by small forbidden induced structures, 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, The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs, Colouring diamond-free graphs, Bounding clique-width via perfect graphs, Coloring graphs without short cycles and long induced paths, List coloring in the absence of two subgraphs, Bounding Clique-Width via Perfect Graphs, Bounding the Clique-Width of H-free Chordal Graphs, Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs, On star and biclique edge-colorings, A Survey on the Computational Complexity of Coloring Graphs with Forbidden 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