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

DOI10.1007/s00453-005-1176-8zbMath1095.68075OpenAlexW2132724824WikidataQ60488763 ScholiaQ60488763MaRDI QIDQ2498403

Jan Kratochvíl, Fedor V. Fomin, Hajo J. 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) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15)

Related Items (9)

Dynamic \(F\)-free coloring of graphs ⋮ Colorings of oriented planar graphs avoiding a monochromatic subgraph ⋮ Colorings of plane graphs without long monochromatic facial paths ⋮ Partitioning a triangle-free planar graph into a forest and a forest of bounded degree ⋮ WORM colorings of planar graphs ⋮ Vertex 2-coloring without monochromatic cycles of fixed size is NP-complete ⋮ Chromatic sums for colorings avoiding monochromatic subgraphs ⋮ Coloring Graphs Using Two Colors While Avoiding Monochromatic Cycles ⋮ Planar Ramsey graphs

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