4-Coloring H-Free Graphs When H Is Small
From MaRDI portal
Publication:2891376
DOI10.1007/978-3-642-27660-6_24zbMath1298.05117MaRDI QIDQ2891376
Jian Song, Petr A. Golovach, Daniël Paulusma
Publication date: 15 June 2012
Published in: SOFSEM 2012: Theory and Practice of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-27660-6_24
Related Items
On the parameterized complexity of coloring graphs in the absence of a linear forest, Closing complexity gaps for coloring problems on \(H\)-free graphs, List coloring in the absence of a linear forest, List Coloring in the Absence of a Linear Forest
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- The complexity of colouring problems on dense graphs
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
- Vertex colouring and forbidden subgraphs -- a survey
- On the complexity of 4-coloring graphs without long induced paths
- Colouring Vertices of Triangle-Free Graphs
- Coloring Graphs without Short Cycles and Long Induced Paths
- List Coloring in the Absence of a Linear Forest
- Three Complexity Results on Coloring P k -Free Graphs
- A Certifying Algorithm for 3-Colorability of P 5-Free Graphs
- On graphs with polynomially solvable maximum-weight clique problem
- The NP-Completeness of Edge-Coloring
- A New Algorithm for Generating All the Maximal Independent Sets
- Graph colorings with local constraints -- a survey
- NP completeness of finding the chromatic index of regular graphs
