首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Homomorphisms of planar (m,n)-colored-mixed graphs to planar targets
Institution:LIRMM, Université de Montpellier, CNRS, Montpellier, France
Abstract: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+n3 (and any value of g) and find a minimal (in the number vertices) planar Pg(m,n)-universal graphs in the other cases.
Keywords:Homomorphism  Planar graphs  Mixed graphs
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号