The higher-girth packing conjecture for strongly planar digraphs
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.