List coloring in the absence of two subgraphs
From MaRDI portal
Publication:2636800
DOI10.1016/j.dam.2013.10.010zbMath1283.05096MaRDI QIDQ2636800
Daniël Paulusma, Petr A. Golovach
Publication date: 18 February 2014
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2013.10.010
05C15: Coloring of graphs and hypergraphs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Related Items
A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs, A complexity dichotomy and a new boundary class for the dominating set problem, Critical hereditary graph classes: a survey, Towards an isomorphism dichotomy for hereditary graph classes, On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs, On list \(k\)-coloring convex bipartite graphs, Colouring square-free graphs without long induced paths, The complexity of the 3-colorability problem in the absence of a pair of small forbidden induced subgraphs, Open Problems on Graph Coloring for Special Graph Classes, 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
- Vertex coloring of graphs with few obstructions
- A decidability result for the dominating set problem
- Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
- 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
- Quickly excluding a forest
- Algorithmic complexity of list colorings
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- Generalized coloring for tree-like 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
- Clique-width for 4-vertex forbidden subgraphs
- Improved Complexity Results on k-Coloring P t -Free Graphs
- Colouring of Graphs with Ramsey-Type Forbidden Subgraphs
- A Characterization of b-Perfect Graphs
- Coloring Graphs Characterized by a Forbidden Subgraph
- Algorithms and Almost Tight Results for 3-Colorability of Small Diameter Graphs
- Coloring Graphs without Short Cycles and Long Induced Paths
- List Coloring in the Absence of a Linear Forest
- Choosability of P 5-Free Graphs
- Graph colorings with local constraints -- a survey
- The Complexity of Multiterminal Cuts
- Closing Complexity Gaps for Coloring Problems on H-Free Graphs
- Graph Isomorphism for Graph Classes Characterized by Two Forbidden Induced Subgraphs
- The complexity of satisfiability problems
- GEM- AND CO-GEM-FREE GRAPHS HAVE BOUNDED CLIQUE-WIDTH
- 25 pretty graph colouring problems
