Colouring of graphs with Ramsey-type forbidden subgraphs
From MaRDI portal
Publication:393895
DOI10.1016/j.tcs.2013.12.004zbMath1279.68104OpenAlexW2107830209MaRDI QIDQ393895
Konrad K. Dabrowski, Petr A. Golovach, Daniël Paulusma
Publication date: 24 January 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2013.12.004
Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (21)
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 ⋮ Colouring square-free graphs without long induced paths. ⋮ Bounding the Clique-Width of H-free Chordal Graphs ⋮ Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs ⋮ Clique‐width: Harnessing the power of atoms ⋮ Bounding clique-width via perfect graphs ⋮ Towards an isomorphism dichotomy for hereditary graph classes ⋮ Clique-Width for Graph Classes Closed under Complementation ⋮ Classifying the clique-width of \(H\)-free bipartite graphs ⋮ On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ Two complexity results for the vertex coloring problem ⋮ The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs ⋮ 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 ⋮ Colouring square-free graphs without long induced paths
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
- Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number
- On the parameterized complexity of coloring graphs in the absence of a linear forest
- The coloring problem for classes with two small obstructions
- Some new hereditary classes where graph coloring remains NP-hard
- Updating the complexity status of coloring graphs without a fixed induced linear forest
- Colouring vertices of triangle-free graphs without forests
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- Recent developments on graphs of bounded clique-width
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- Coloring the hypergraph of maximal cliques of a graph with no long path
- 3-colorability and forbidden subgraphs. I: Characterizing pairs
- 4-coloring \(H\)-free graphs when \(H\) is small
- On the structure of (\(P_{5}\),\,gem)-free graphs
- Edge dominating set and colorings on graphs with fixed clique-width
- Vertex colouring and forbidden subgraphs -- a survey
- Upper bounds to the clique width of graphs
- Clique-width for 4-vertex forbidden subgraphs
- Approximating clique-width and branch-width
- Improved Complexity Results on k-Coloring P t -Free Graphs
- Colouring of Graphs with Ramsey-Type Forbidden Subgraphs
- A Characterization of b-Perfect Graphs
- List Coloring in the Absence of a Linear Forest
- THE CLIQUE-WIDTH OF BIPARTITE GRAPHS IN MONOGENIC CLASSES
- Graph colorings with local constraints -- a survey
- On the Band-, Tree-, and Clique-Width of Graphs with Bounded Vertex Degree
- Closing Complexity Gaps for Coloring Problems on H-Free Graphs
- List Coloring in the Absence of Two Subgraphs
- ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P4'S
- Independent Set in P5-Free Graphs in Polynomial Time
- GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH
This page was built for publication: Colouring of graphs with Ramsey-type forbidden subgraphs
