Coloring Graphs without Short Cycles and Long Induced Paths
From MaRDI portal
Publication:3088283
DOI10.1007/978-3-642-22953-4_17zbMath1342.05039MaRDI QIDQ3088283
Daniël Paulusma, Jian Song, Petr A. Golovach
Publication date: 19 August 2011
Published in: Fundamentals of Computation Theory (Search for Journal in Brave)
Full work available at URL: http://dro.dur.ac.uk/14121/1/14121.pdf
05C38: Paths and cycles
05C15: Coloring of graphs and hypergraphs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
The coloring problem for classes with two small obstructions, List coloring in the absence of two subgraphs, 4-Coloring H-Free Graphs When H Is Small
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
- Updating the complexity status of coloring graphs without a fixed induced linear forest
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
- Triangle-free graphs and forbidden subgraphs
- Vertex colouring and forbidden subgraphs -- a survey
- Colouring Vertices of Triangle-Free Graphs
- List Coloring in the Absence of a Linear Forest
- Three Complexity Results on Coloring P k -Free Graphs
- The NP-Completeness of Edge-Coloring
- Graph colorings with local constraints -- a survey
- The complexity of satisfiability problems