Orientations of 10‐Edge‐Connected Planar Multigraphs and Applications

ABSTRACT

A graph is called strongly ‐connected if for each boundary function with , there exists an orientation of such that for each . We show that every planar multigraph with 5 edge‐disjoint spanning trees is strongly ‐connected. This verifies a special case of the Additive Base Conjecture when restricted to planar graphs. Hence, every 10‐edge‐connected directed planar graph admits an antisymmetric ‐flow. By duality, every orientation of a planar graph of girth at least 10 admits a homomorphism to a 5‐vertex tournament. Our result also gives a new proof of the known result that every planar graph of girth at least 10 has a homomorphism to the 5‐cycle.