Planar graph coloring avoiding monochromatic subgraphs: Trees and paths make it difficult

DOI10.1007/S00453-005-1176-8MaRDI QIDQ2498403zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Fedor V. Fomin, Jan Kratochvíl, Hajo Broersma, Gerhard J. Woeginger

Publication date 16 August 2006

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL http://dro.dur.ac.uk/604/1/604.pdf

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• scientific article; zbMATH DE number 2089219
• Coloring graphs characterized by a forbidden subgraph
• Coloring graphs characterized by a forbidden subgraph
• Colorings of oriented planar graphs avoiding a monochromatic subgraph
• Polychromatic colorings of plane graphs

Cited in

(9)

• Vertex 2-coloring without monochromatic cycles of fixed size is NP-complete
• Planar Ramsey graphs
• Dynamic \(F\)-free coloring of graphs
• scientific article; zbMATH DE number 2089219 (Why is no real title available?)
• Colorings of oriented planar graphs avoiding a monochromatic subgraph
• Colorings of plane graphs without long monochromatic facial paths
• Chromatic sums for colorings avoiding monochromatic subgraphs
• Coloring graphs using two colors while avoiding monochromatic cycles
• WORM colorings of planar graphs

This page was built for publication: Planar graph coloring avoiding monochromatic subgraphs: Trees and paths make it difficult

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