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


Colouring of generalized signed triangle-free planar graphs
Authors:Yiting Jiang  Daphne Der-Fen Liu  Yeong-Nan Yeh  Xuding Zhu
Abstract:We view an undirected graph G as a symmetric digraph, where each edge xy is replaced by two opposite arcs e=(x,y) and e?1=(y,x). Assume S is an inverse closed subset of permutations of positive integers. We say G is S-k-colourable if for any mapping σ:E(G)S with σ(x,y)=(σ(y,x))?1, there is a mapping f:V(G)[k]={1,2,,k} such that σe(f(x))f(y) for each arc e=(x,y). The concept of S-k-colourable is a common generalization of several other colouring concepts. This paper is focused on finding the sets S such that every triangle-free planar graph is S-3-colourable. Such a set S is called TFP-good. Grötzsch’s theorem is equivalent to say that S={id} is TFP-good. We prove that for any inverse closed subset S of S3 which is not isomorphic to {id,(12)}, S is TFP-good if and only if either S={id} or there exists a[3] such that for each πS, π(a)a. It remains an open question to determine whether or not S={id,(12)} is TFP-good.
Keywords:Corresponding author.  Triangle-free planar graphs  List colouring  Oriented graphs  Signed graphs
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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