Colouring of graphs with Ramsey-type forbidden subgraphs

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

zbMATH Keywords

colouringindependent setcliqueforbidden induced subgraphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

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 P₄'S
• Independent Set in P₅-Free Graphs in Polynomial Time
• GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH