Can I read Colorings of Oriented Planar Graphs Avoiding a Monochromatic Subgraph on EtoBox?

Colorings of Oriented Planar Graphs Avoiding a Monochromatic Subgraph by Bergold, Helena; Hochstättler, Winfried; Steiner, Raphael is a scholarly article available to read on EtoBox.

What is Colorings of Oriented Planar Graphs Avoiding a Monochromatic Subgraph about?

For a fixed simple digraph $F$ and a given simple digraph $D$, an $F$-free $k$-coloring of $D$ is a vertex-coloring in which no induced copy of $F$ in $D$ is monochromatic. We study the complexity of deciding for fixed $F$ and $k$ whether a given simple digraph admits an $F$-free $k$-coloring. Our main focus is on the restriction of the problem to planar input digraphs, where it is only interesting to study the cases $k \in \{2,3\}$. From known results it follows that for every fixed digraph $F$ whose underlying graph is not a forest, every planar digraph $D$ admits an $F$-free $2$-coloring, and that for every fixed digraph $F$ with $\Delta(F) \ge 3$, every oriented planar graph $D$ admits an $F$-free $3$-coloring. We show in contrast, that - if $F$ is an orientation of a path of length at least $2$, then it is NP-hard to decide whether an acyclic and planar input digraph $D$ admits an $F$-free $2$-coloring. - if $F$ is an orientation of a path of length at least $1$, then it is NP-hard to decide whether an acyclic and planar input digraph $D$ admits an $F$-free $3$-coloring.

Author

Bergold, Helena; Hochstättler, Winfried; Steiner, Raphael

Published

2021

Language

EN