Geodesic
Families of strongly projective graphs
Discussiones Mathematicae. Graph Theory, Tome 22 (2002) no. 2, pp. 271-292.

Voir la notice de l'article provenant de la source Library of Science

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},
     publisher = {mathdoc},
     volume = {22},
     number = {2},
     year = {2002},
     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
PB  - mathdoc
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
%I mathdoc
%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.