Complexity of 2-F-PFC for star-pruned oriented trees

Open Complexity Problem (2-F-PFC for oriented trees of maximum degree ≥ 3) · arXiv:2102.07705

arXiv Problem medium confidence— first stated 2022-06-07

Authors: Helena Bergold, Winfried Hochstättler, Raphael Steiner

Status open medium confidence

The paper arXiv:2102.07705, published in Discrete Applied Mathematics (2022), establishes NP-hardness of 2-F-PFC for oriented trees whose leaf-pruned form is an oriented path of length 2 or 3, but explicitly leaves open the analogous question for oriented trees whose leaf-pruned form is a star K_{1,n}. No follow-up paper resolving this complexity question was found in a web search or via Semantic Scholar (which returned zero citations to this paper); the conjecture remains open as of May 2026.

Reviewer notes. Semantic Scholar API returned zero citing papers for arXiv:2102.07705. The published journal version appeared in Discrete Applied Mathematics (ScienceDirect, 2022, doi not verified). The conjecture is moderately recent (≈3 years); absence of follow-up may reflect genuine openness or limited visibility of this specialized complexity question. Confidence is medium rather than high because the paper is old enough that a resolution could exist without being indexed.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Problem. The complexity of the $2$-$F$-PFC where the underlying undirected tree of $F$ has maximum degree at least $3$ remains partially open. In particular, the complexity for those graphs $F$ where successively deleting all leaves yields a star $K_{1,n}$ is not determined.

Context

The paper proves NP-hardness of 2-$\vec{T}$-PFC when the oriented tree $\vec{T}$ reduces to an oriented path of length 2 or 3 after repeatedly removing all leaves. The analogous question for oriented trees whose leaf-pruned form is a star $K_{1,n}$ is explicitly left open in the introduction.

Notes. Stated in prose in the introduction without a formal labelled environment. PDF source — math notation may be garbled.

Source paper

Colorings of oriented planar graphs avoiding a monochromatic subgraph
Helena Bergold, Winfried Hochstättler, Raphael Steiner · 2022-06-07
https://arxiv.org/abs/2102.07705 PDF source