Homomorphisms of binary Cayley graphs

被引:4
作者
Beaudou, Laurent [1 ]
Naserasr, Reza [2 ]
Tardif, Claude [3 ]
机构
[1] Univ Clermont Ferrand, CNRS, LIMOS, UMR6158, Aubiere, France
[2] Univ Paris 11, CNRS, LRI, UMR8623, F-91405 Orsay, France
[3] Coll Mil Royal Canada, Kingston, ON, Canada
关键词
Cayley graph; Homomorphism; Projective cube;
D O I
10.1016/j.disc.2015.06.025
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
A binary Cayley graph is a Cayley graph based on a binary group. In 1992, Payan proved that any non-bipartite binary Cayley graph must contain a generalized Mycielski graph of an odd cycle, implying that such a graph cannot have chromatic number 3. We strengthen this result first by proving that any non-bipartite binary Cayley graph must contain a projective cube as a subgraph. We further conjecture that any homomorphism of a non-bipartite binary Cayley graph to a projective cube must be surjective and we prove a special case of this conjecture. (C) 2015 Elsevier B.V. All rights reserved.
引用
收藏
页码:2539 / 2544
页数:6
相关论文
共 10 条
[1]  
Godsil C. D., 2001, GRADUATE TEXTS MATH, V207
[2]  
Hahn G, 1997, NATO ADV SCI I C-MAT, V497, P107
[3]  
Matousek J., 2003, Using the Borsuk-Ulam theorem
[4]   Homomorphisms and edge-colourings of planar graphs [J].
Naserasr, Reza .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2007, 97 (03) :394-400
[5]   Homomorphisms of Signed Graphs [J].
Naserasr, Reza ;
Rollova, Edita ;
Sopena, Eric .
JOURNAL OF GRAPH THEORY, 2015, 79 (03) :178-212
[6]   ON THE CHROMATIC NUMBER OF CUBE-LIKE GRAPHS [J].
PAYAN, C .
DISCRETE MATHEMATICS, 1992, 103 (03) :271-277
[7]  
Sabidussi G., 1968, MONATSH MATH, V68, P426
[8]  
Scapellato R, 1997, NATO ADV SCI I C-MAT, V497, P319
[9]  
Scheinerman E. R., 1997, WILEY INTERSCIENCE S
[10]  
Stiebitz M., 1985, THESIS TU ILMENAU