Colorings of oriented planar graphs avoiding a monochromatic subgraph

DOI10.1016/j.dam.2022.05.015zbMath1505.05053arXiv2102.07705OpenAlexW3129896241MaRDI QIDQ2166215

Helena Bergold, Raphael Steiner, Winfried Hochstättler

Publication date: 24 August 2022

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2102.07705

zbMATH Keywords

planar digraphsNP-hardnessdigraph coloring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)

Cites Work

• Partitions of graphs into cographs
• 2-list-coloring planar graphs without monochromatic triangles
• Subcolorings and the subchromatic number of a graph
• The dichromatic number of a digraph
• Decomposing a planar graph into degenerate graphs
• Planar graph coloring avoiding monochromatic subgraphs: Trees and paths make it difficult
• On the linear vertex-arboricity of a planar graph

This page was built for publication: Colorings of oriented planar graphs avoiding a monochromatic subgraph