Colouring of graphs with Ramsey-type forbidden subgraphs
From MaRDI portal
Publication:393895
DOI10.1016/j.tcs.2013.12.004zbMath1279.68104MaRDI 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
68Q25: Analysis of algorithms and problem complexity
05C15: Coloring of graphs and hypergraphs
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Unnamed Item, On the Complexity of the Vertex 3-Coloring Problem for the Hereditary Graph Classes With Forbidden Subgraphs of Small Size, Efficient solvability of the weighted vertex coloring problem for some hereditary class of graphs with $5$-vertex prohibitions, Clique-Width for Graph Classes Closed under Complementation, Two cases of polynomial-time solvability for the coloring problem, Bounding the clique-width of \(H\)-free split graphs, Clique‐width: Harnessing the power of atoms, Two complexity results for the vertex coloring problem, Classifying the clique-width of \(H\)-free bipartite graphs, The weighted coloring problem for two graph classes characterized by small forbidden induced structures, Towards an isomorphism dichotomy for hereditary graph classes, On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs, The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs, Colouring square-free graphs without long induced paths, Colouring diamond-free graphs, Bounding clique-width via perfect graphs, 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, A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs, 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
