Homomorphisms of planar (m,n)-colored-mixed graphs to planar targets |
| |
Institution: | LIRMM, Université de Montpellier, CNRS, Montpellier, France |
| |
Abstract: | An -colored-mixed graph 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 -colored-mixed graph G to another -colored-mixed graph H is a morphism such that each edge (resp. arc) of G is mapped to an edge (resp. arc) of H of the same color (and orientation). An -colored-mixed graph T is said to be -universal if every graph in (the planar -colored-mixed graphs with girth at least g) admits a homomorphism to T.We show that planar -universal graphs do not exist for (and any value of g) and find a minimal (in the number vertices) planar -universal graphs in the other cases. |
| |
Keywords: | Homomorphism Planar graphs Mixed graphs |
本文献已被 ScienceDirect 等数据库收录! |
|