The higher-girth packing conjecture for strongly planar digraphs
A feedback vertex set of a digraph is a set of vertices whose deletion leaves an acyclic digraph, and a strongly planar digraph is a digraph arising from an oriented plane graph with a perfect matching as described in the paper. Let be a strongly planar digraph of girth .
Higher-girth packing conjecture. There exists a packing of pairwise disjoint feedback vertex sets in . Equivalently, can be vertex -coloured such that every directed cycle uses each colour at least once.
The case gives the known -colourability result for strongly planar digraphs, and the directed cycle of length shows that the proposed bound is best possible. The general statement remains open.
References
Primary source
Marcelo Garlet Millani, Raphael Steiner and Sebastian Wiederrecht, “Colouring Non-Even Digraphs”, arXiv:1903.02872 (2019).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.