2020/08/31 by Jacques, Fabien, Ochem, Pascal
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2008.13747
An (m, n)-colored-mixed graph G=(V, A1, A2,⋯, Am, E1, E2,⋯, En) is a graph having m colors of arcs and n colors of edges. We do not allow two arcs or edges to have the same endpoints. A homomorphism from an (m,n)-colored-mixed graph G to another (m, n)-colored-mixed graph H is a morphism φ:V(G)→ V(H) such that each edge (resp. arc) of G is mapped to an edge (resp. arc) of H of the same color (and orientation). An (m,n)-colored-mixed graph T is said to be Pg(m, n)-universal if every graph in Pg(m, n) (the planar (m, n)-colored-mixed graphs with girth at least g) admits a homomorphism to T. We show that planar Pg(m, n)-universal graphs do not exist for 2m+n≥3 (and any value of g) and find a minimal (in the number vertices) planar Pg(m, n)-universal graphs in the other cases.