Colouring vertices of triangle-free graphs without forests

DOI10.1016/J.DISC.2011.12.012zbMATH Open1237.05071OpenAlexW2077936668MaRDI QIDQ764907FDOQ764907

Authors Konrad Dabrowski, Vadim Lozin, 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

clique-widthpolynomial-time algorithmtriangle-free graphsvertex colouring

Mathematics Subject Classification ID

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

Recommendations

• Colouring vertices of triangle-free graphs
• On coloring graphs without induced forests
• Coloring graphs characterized by a forbidden subgraph
• Coloring graphs characterized by a forbidden subgraph
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs

Cites work

• scientific article; zbMATH DE number 3882470 (Why is no real title available?)
• scientific article; zbMATH DE number 2044943 (Why is no real title available?)
• scientific article; zbMATH DE number 1833071 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• scientific article; zbMATH DE number 5279372 (Why is no real title available?)
• scientific article; zbMATH DE number 5179133 (Why is no real title available?)
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• 3-colorability and forbidden subgraphs. I: Characterizing pairs
• A 4-colour problem for dense triangle-free graphs
• A New Algorithm for Generating All the Maximal Independent Sets
• Bipartite graphs without a skew star
• Coloring Bull-Free Perfectly Contractile Graphs
• Coloring edges and vertices of graphs without short or long cycles
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• MSOL partitioning problems on graphs of bounded treewidth and clique-width
• Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs
• On coloring graphs without induced forests
• On graphs with polynomially solvable maximum-weight clique problem
• On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• On the complexity of 4-coloring graphs without long induced paths
• Optimizing Bull-Free Perfect Graphs
• Paw-free graphs
• Recent developments on graphs of bounded clique-width
• Some new hereditary classes where graph coloring remains NP-hard
• THE CLIQUE-WIDTH OF BIPARTITE GRAPHS IN MONOGENIC CLASSES
• The 3-Colorability Problem on Graphs with Maximum Degree Four
• The Erdős-Hajnal conjecture for bull-free graphs
• The NP-Completeness of Edge-Coloring
• The complexity of coloring graphs without long induced paths
• The structure of bull-free graphs II and III -- a summary
• Three complexity results on coloring \(P _{k }\)-free graphs
• Three-colourability and forbidden subgraphs. II: Polynomial algorithms
• Triangle-free graphs and forbidden subgraphs
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• Upper bounds to the clique width of graphs

Cited in

(33)

• Coloring triangle-free graphs with fixed size
• Coloring graphs without short cycles and long induced paths
• Colouring of graphs with Ramsey-type forbidden subgraphs
• List coloring in the absence of a linear forest
• Clique‐width: Harnessing the power of atoms
• Colouring vertices of triangle-free graphs
• On the complexity of the vertex 3-coloring problem for the hereditary graph classes with forbidden subgraphs of small size
• On star and biclique edge-colorings
• \((2P_2,K_4)\)-free graphs are 4-colorable
• The \(r\)-coloring and maximum stable set problem in hypergraphs with bounded matching number and edge size
• Bounding the clique-width of \(H\)-free chordal graphs
• A survey on the computational complexity of coloring graphs with forbidden subgraphs
• Colouring diamond-free graphs
• scientific article; zbMATH DE number 7274066 (Why is no real title available?)
• Bounding clique-width via perfect graphs
• Bounding the mim‐width of hereditary graph classes
• The coloring problem for classes with two small obstructions
• The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
• Clique-width for graph classes closed under complementation
• List coloring in the absence of two subgraphs
• Clique-width of graph classes defined by two forbidden induced subgraphs
• Efficient solvability of the weighted vertex coloring problem for some hereditary class of graphs with 5-vertex prohibitions
• Bounding the Mim-Width of Hereditary Graph Classes.
• 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
• On vertex coloring without monochromatic triangles
• Two complexity results for the vertex coloring problem
• Bounding clique-width via perfect graphs
• The weighted coloring problem for two graph classes characterized by small forbidden induced structures
• scientific article; zbMATH DE number 7204407 (Why is no real title available?)
• The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs
• Two cases of polynomial-time solvability for the coloring problem
• Bounding the clique-width of \(H\)-free split graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q764907)