Geodesic
Families of strongly projective graphs
Discussiones Mathematicae. Graph Theory, Tome 22 (2002) no. 2, pp. 271-292 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

We give several characterisations of strongly projective graphs which generalise in many respects odd cycles and complete graphs [7]. We prove that all known families of projective graphs contain only strongly projective graphs, including complete graphs, odd cycles, Kneser graphs and non-bipartite distance-transitive graphs of diameter d ≥ 3.
Keywords: distance-transitive graphs, graph homomorphism, graph product 
@article{DMGT_2002_22_2_a5,
     author = {Larose, Benoit},
     title = {Families of strongly projective graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {271--292},
     year = {2002},
     volume = {22},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2002_22_2_a5/}
}
TY  - JOUR
AU  - Larose, Benoit
TI  - Families of strongly projective graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2002
SP  - 271
EP  - 292
VL  - 22
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2002_22_2_a5/
LA  - en
ID  - DMGT_2002_22_2_a5
ER  - 
%0 Journal Article
%A Larose, Benoit
%T Families of strongly projective graphs
%J Discussiones Mathematicae. Graph Theory
%D 2002
%P 271-292
%V 22
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2002_22_2_a5/
%G en
%F DMGT_2002_22_2_a5
Larose, Benoit. Families of strongly projective graphs. Discussiones Mathematicae. Graph Theory, Tome 22 (2002) no. 2, pp. 271-292. http://geodesic.mathdoc.fr/item/DMGT_2002_22_2_a5/

[1] D. Duffus, B. Sands and R.E. Woodrow, On the chromatic number of the product of graphs, J. Graph Theory 9 (1985) 487-495, doi: 10.1002/jgt.3190090409.

[2] M. El-Zahar and N. Sauer, The chromatic number of the product of two 4-chromatic graphs is 4, Combinatorica 5 (1985) 121-126, doi: 10.1007/BF02579374.

[3] D. Greenwell and L. Lovász, Applications of product colourings, Acta Math. Acad. Sci. Hungar. 25 (1974) 335-340, doi: 10.1007/BF01886093.

[4] G. Hahn and C. Tardif, Graph homomorphisms: structure and symmetry, in: G. Hahn and G. Sabidussi, eds, Graph Symmetry, Algebraic Methods and Applications, NATO ASI Ser. C 497 (Kluwer Academic Publishers, Dordrecht, 1997) 107-166.

[5] S. Hazan, On triangle-free projective graphs, Algebra Universalis, 35 (1996) 185-196, doi: 10.1007/BF01195494.

[6] W. Imrich and S. Klavžar, Product Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization (John Wiley and Sons, 2000).

[7] B. Larose, Strongly projective graphs, Canad. J. Math. 17 pages, to appear.

[8] B. Larose and C. Tardif, Hedetniemi's conjecture and the retracts of products of graphs, Combinatorica 20 (2000) 531-544, doi: 10.1007/s004930070006.

[9] B. Larose and C. Tardif, Strongly rigid graphs and projectivity, Mult. Val. Logic, 22 pages, to appear.

[10] B. Larose and C. Tardif, Projectivity and independent sets in powers of graphs, J. Graph Theory, 12 pages, to appear.

[11] L. Lovász, Operations with structures, Acta Math. Acad. Sci. Hungar. 18 (1967) 321-328, doi: 10.1007/BF02280291.

[12] R.N. McKenzie, G.F. McNulty and W.F. Taylor, Algebras, Lattices and Varieties (Wadsworth and Brooks/Cole, Monterey California, 1987).

[13] J. Nesetril, X. Zhu, On sparse graphs with given colorings and homomorphisms, preprint, 13 pages, 2000.

[14] D.H. Smith, Primitive and imprimitive graphs, Quart. J. Math. Oxford (2) 22 (1971) 551-557, doi: 10.1093/qmath/22.4.551.

[15] A. Szendrei, Simple surjective algebras having no proper subalgebras, J. Austral. Math. Soc. (Series A) 48 (1990) 434-454, doi: 10.1017/S1446788700029979.

[16] C. Tardif, personal communication, 2000.

[17] J.W. Walker, From graphs to ortholattices and equivariant maps, J. Combin. Theory (B) 35 (1983) 171-192, doi: 10.1016/0095-8956(83)90070-9.