List coloring in the absence of two subgraphs
From MaRDI portal
Publication:2636800
DOI10.1016/j.dam.2013.10.010zbMath1283.05096OpenAlexW2034537604MaRDI 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
Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items (12)
A complexity dichotomy and a new boundary class for the dominating set problem ⋮ Colouring square-free graphs without long induced paths. ⋮ Clique-Width of Graph Classes Defined by Two Forbidden Induced Subgraphs ⋮ Towards an isomorphism dichotomy for hereditary graph classes ⋮ On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ Critical hereditary graph classes: a survey ⋮ On list \(k\)-coloring convex bipartite graphs ⋮ Open Problems on Graph Coloring for Special Graph Classes ⋮ 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 ⋮ A dichotomy for the dominating set problem for classes defined by small forbidden induced subgraphs
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
This page was built for publication: List coloring in the absence of two subgraphs
