Strongly projective graphs

被引：3
作者：
Larose, B
机构：
[1] Champlain Reg Coll, Dept Math, Quebec City, PQ J4P 3P2, Canada
[2] Concordia Univ, Dept Math & Stat, Montreal, PQ H3G 1M8, Canada
来源：
CANADIAN JOURNAL OF MATHEMATICS-JOURNAL CANADIEN DE MATHEMATIQUES | 2002年 / 54卷 / 04期
关键词：
D O I：
10.4153/CJM-2002-029-7
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
We introduce the notion of strongly projective graph, and characterise. these graphs in terms of their neighbourhood poset. We describe certain exponential graphs associated to complete graphs and odd cycles. We extend and generalise a result of Greenwell and Lovasz [6]: if a connected graph G does not admit a homomorphism to K, where K is an odd cycle or a complete graph on at least 3 vertices, then the graph G x K-s admits, up to automorphisms of K, exactly s homomorphisms to K.
引用
收藏
页码：757 / 768
页数：12
相关论文
共 18 条
[1]  
COROMINAS E, 1990, CR ACAD SCI I-MATH, V311, P199
[2]   BRAIDS AND THEIR MONOTONE CLONES [J].
DAVEY, BA ;
NATION, JB ;
MCKENZIE, RN ;
PALFRY, PP .
ALGEBRA UNIVERSALIS, 1994, 32 (02) :153-176
[3]   ALGEBRAIC PROPERTIES OF CROWNS AND FENCES [J].
DEMETROVICS, J ;
RONYAI, L .
ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 1989, 6 (01) :91-99
[4]   ON THE CHROMATIC NUMBER OF THE PRODUCT OF GRAPHS [J].
DUFFUS, D ;
SANDS, B ;
WOODROW, RE .
JOURNAL OF GRAPH THEORY, 1985, 9 (04) :487-495
[5]   THE CHROMATIC NUMBER OF THE PRODUCT OF 2 4-CHROMATIC GRAPHS IS 4 [J].
ELZAHAR, M ;
SAUER, NW .
COMBINATORICA, 1985, 5 (02) :121-126
[6]   APPLICATIONS OF PRODUCT COLORING [J].
GREENWELL, D ;
LOVASZ, L .
ACTA MATHEMATICA ACADEMIAE SCIENTIARUM HUNGARICAE, 1974, 25 (3-4) :335-340
[7]  
Hahn G, 1997, NATO ADV SCI I C-MAT, V497, P107
[8]   2 PROPERTIES OF PROJECTIVE ORDERS [J].
HAZAN, S .
ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 1992, 9 (03) :233-238
[9]  
Hedetniemi S., 1966, Technical Report 03105-44-T
[10]   Hedetniemi's conjecture and the retracts of a product of graphs [J].
Larose, B ;
Tardif, C .
COMBINATORICA, 2000, 20 (04) :531-544
12