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

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

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

(10)

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

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)