Coloring Graphs without Short Cycles and Long Induced Paths

DOI10.1007/978-3-642-22953-4_17zbMATH Open1342.05039OpenAlexW264442127MaRDI QIDQ3088283FDOQ3088283

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

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
• Three Complexity Results on Coloring P k -Free Graphs
• The NP-Completeness of Edge-Coloring
• The complexity of satisfiability problems
• Updating the complexity status of coloring graphs without a fixed induced linear forest
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Graph colorings with local constraints -- a survey
• Vertex colouring and forbidden subgraphs -- a survey
• Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
• List Coloring in the Absence of a Linear Forest
• Triangle-free graphs and forbidden subgraphs
• Colouring Vertices of Triangle-Free Graphs

Cited In (7)

• The chromatic number of a graph with two odd holes and an odd girth
• The coloring problem for classes with two small obstructions
• Approximately coloring graphs without long induced paths
• Acyclic coloring of graphs without bichromatic long path
• List coloring in the absence of two subgraphs
• Title not available (Why is that?)
• 4-Coloring H-Free Graphs When H Is Small

This page was built for publication: Coloring Graphs without Short Cycles and Long Induced Paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3088283)