2025/03/12 by Fiorini, Samuel, Kober, Stefan, Seweryn, Michał T. +2 · 1 citation
#05C10 #05C83 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2503.09230
A \em rooted graph is a graph together with a designated vertex subset, called the \em roots. In this paper, we consider rooted graphs embedded in a fixed surface. A collection of faces of the embedding is a \em face cover if every root is incident to some face in the collection. We prove that every 3-connected, rooted graph that has no rooted K2,t minor and is embedded in a surface of Euler genus g, has a face cover whose size is upper-bounded by some function of g and t, provided that the face-width of the embedding is large enough in terms of g. In the planar case, we prove an unconditional O(t4) upper bound, improving a result of Böhme and Mohar~\citeBM02. The higher genus case was claimed without a proof by Böhme, Kawarabayashi, Maharry and Mohar~\citeBKMM08.