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

DOI10.1007/S00453-005-1176-8zbMATH Open1095.68075DBLPjournals/algorithmica/BroersmaFKW06OpenAlexW2132724824WikidataQ60488763 ScholiaQ60488763MaRDI QIDQ2498403FDOQ2498403

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

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

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)

Cited In (9)

• Vertex 2-coloring without monochromatic cycles of fixed size is NP-complete
• Planar Ramsey graphs
• Dynamic \(F\)-free coloring of graphs
• Title not available (Why is that?)
• 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)