Abstract | ||
---|---|---|
An (m, n)-colored-mixed graph G = (V, A(1), A(2), ..., A(m), E-1, E-2, ..., E-n) 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 phi : 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 P-g((m,n))-(the planar (m, n)-colored-mixed graphs with girth at least g) admits a homomorphism to T. We show that planar P(m,n) g-universal graphs do not exist for 2m +n (and any value of g) and find a minimal (in the number vertices) planar P(m,n) g-universal graphs in the other cases. (C) 2021 Elsevier B.V. All rights reserved. |
Year | DOI | Venue |
---|---|---|
2021 | 10.1016/j.disc.2021.112600 | DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
Homomorphism, Planar graphs, Mixed graphs | Journal | 344 |
Issue | ISSN | Citations |
12 | 0012-365X | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Fabien Jacques | 1 | 0 | 0.34 |
Pascal Ochem | 2 | 258 | 36.91 |