The higher-girth packing conjecture for strongly planar digraphs

About 7 years old · traced to

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 DD be a strongly planar digraph of girth gg.

Higher-girth packing conjecture. There exists a packing of gg pairwise disjoint feedback vertex sets in DD. Equivalently, DD can be vertex gg-coloured such that every directed cycle uses each colour at least once.

The case g=3g=3 gives the known 22-colourability result for strongly planar digraphs, and the directed cycle of length gg 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

Never refreshed

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.