Colorings of oriented planar graphs avoiding a monochromatic subgraph (Q2166215): Difference between revisions

Let \(F\) and \(D\) be two fixed simple digraphs. An \(F\)-free \(k\)-coloring of \(D\) is a vertex-coloring in which no induced copy of \(F\) in \(D\) is monochromatic. The authors study the complexity of deciding for fixed \(F\) and \(k\) whether a given simple digraph has an \(F\)-free \(k\)-coloring. This is a directed version of the previous problem of determining the complexity of coloring planar graphs avoiding a monochromatic induced copy of some connected planar graph \(F\). It can be obtained 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)\geq 3\), every oriented planar graph \(D\) admits an \(F\)-free 3-coloring. In this paper, the authors mainly prove the following two main results. \begin{itemize} \item[(1)] 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. \item[(2)] 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. \end{itemize}