Colouring vertices of triangle-free graphs without forests
From MaRDI portal
Publication:764907
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
Recommendations
Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Cites Work
- 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 \(\in \mathcal P\) for \(P_{6}\)-free graphs.
- A 4-colour problem for dense triangle-free graphs
- Upper bounds to the clique width of graphs
- Title not available (Why is that?)
- Three complexity results on coloring \(P _{k }\)-free graphs
- The NP-Completeness of Edge-Coloring
- A New Algorithm for Generating All the Maximal Independent Sets
- Title not available (Why is that?)
- Title not available (Why is that?)
- The structure of bull-free graphs II and III -- a summary
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- Recent developments on graphs of bounded clique-width
- The complexity of coloring graphs without long induced paths
- Title not available (Why is that?)
- Paw-free graphs
- Title not available (Why is that?)
- MSOL partitioning problems on graphs of bounded treewidth and clique-width
- Three-colourability and forbidden subgraphs. II: Polynomial algorithms
- Coloring edges and vertices of graphs without short or long cycles
- On the complexity of 4-coloring graphs without long induced paths
- On graphs with polynomially solvable maximum-weight clique problem
- 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
- Some new hereditary classes where graph coloring remains NP-hard
- The Erdős-Hajnal conjecture for bull-free graphs
- 3-colorability and forbidden subgraphs. I: Characterizing pairs
- THE CLIQUE-WIDTH OF BIPARTITE GRAPHS IN MONOGENIC CLASSES
- Title not available (Why is that?)
- Triangle-free graphs and forbidden subgraphs
- Bipartite graphs without a skew star
- Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs
- On coloring graphs without induced forests
- Coloring Bull-Free Perfectly Contractile Graphs
Cited In (32)
- Colouring of graphs with Ramsey-type forbidden subgraphs
- Efficient solvability of the weighted vertex coloring problem for some hereditary class of graphs with $5$-vertex prohibitions
- Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs
- On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size
- Bounding the Clique-Width of H-free Chordal Graphs
- Bounding the Mim-Width of Hereditary Graph Classes.
- On star and biclique edge-colorings
- The coloring problem for classes with two small obstructions
- 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
- Coloring graphs without short cycles and long induced paths
- Clique-Width for Graph Classes Closed under Complementation
- Title not available (Why is that?)
- Bounding the clique-width of \(H\)-free split graphs
- List coloring in the absence of a linear forest
- Bounding clique-width via perfect graphs
- Colouring diamond-free graphs
- A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
- Clique‐width: Harnessing the power of atoms
- Colouring vertices of triangle-free graphs
- The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs
- Title not available (Why is that?)
- List coloring in the absence of two subgraphs
- Bounding Clique-Width via Perfect Graphs
- 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
- Two complexity results for the vertex coloring problem
- Two cases of polynomial-time solvability for the coloring problem
- The \(r\)-coloring and maximum stable set problem in hypergraphs with bounded matching number and edge size
- Coloring triangle-free graphs with fixed size
- $(2P_2,K_4)$-Free Graphs are 4-Colorable
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)
