# Families of strongly projective graphs

Discussiones Mathematicae Graph Theory (2002)

- Volume: 22, Issue: 2, page 271-292
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topBenoit Larose. "Families of strongly projective graphs." Discussiones Mathematicae Graph Theory 22.2 (2002): 271-292. <http://eudml.org/doc/270746>.

@article{BenoitLarose2002,

abstract = {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.},

author = {Benoit Larose},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {distance-transitive graphs; graph homomorphism; graph product; Strongly projective; product graph; distance-transitive},

language = {eng},

number = {2},

pages = {271-292},

title = {Families of strongly projective graphs},

url = {http://eudml.org/doc/270746},

volume = {22},

year = {2002},

}

TY - JOUR

AU - Benoit Larose

TI - Families of strongly projective graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2002

VL - 22

IS - 2

SP - 271

EP - 292

AB - 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.

LA - eng

KW - distance-transitive graphs; graph homomorphism; graph product; Strongly projective; product graph; distance-transitive

UR - http://eudml.org/doc/270746

ER -

## References

top- [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. Zbl0664.05019
- [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. Zbl0575.05028
- [3] D. Greenwell and L. Lovász, Applications of product colourings, Acta Math. Acad. Sci. Hungar. 25 (1974) 335-340, doi: 10.1007/BF01886093. Zbl0294.05108
- [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. Zbl0845.05062
- [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. Zbl1020.05029
- [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. Zbl0996.05065
- [9] B. Larose and C. Tardif, Strongly rigid graphs and projectivity, Mult. Val. Logic, 22 pages, to appear. Zbl1009.05121
- [10] B. Larose and C. Tardif, Projectivity and independent sets in powers of graphs, J. Graph Theory, 12 pages, to appear. Zbl1003.05077
- [11] L. Lovász, Operations with structures, Acta Math. Acad. Sci. Hungar. 18 (1967) 321-328, doi: 10.1007/BF02280291. Zbl0174.01401
- [12] R.N. McKenzie, G.F. McNulty and W.F. Taylor, Algebras, Lattices and Varieties (Wadsworth and Brooks/Cole, Monterey California, 1987). Zbl0611.08001
- [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. Zbl0222.05111
- [15] A. Szendrei, Simple surjective algebras having no proper subalgebras, J. Austral. Math. Soc. (Series A) 48 (1990) 434-454, doi: 10.1017/S1446788700029979. Zbl0702.08003
- [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. Zbl0509.05059

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.