Families of strongly projective graphs
Benoit Larose
Discussiones Mathematicae Graph Theory, Tome 22 (2002), p. 271-292 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2002-01-01
EUDML-ID : urn:eudml:doc:270746 
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1175,
     author = {Benoit Larose},
     title = {Families of strongly projective graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {22},
     year = {2002},
     pages = {271-292},
     zbl = {1029.05133},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1175}
}

Benoit Larose. Families of strongly projective graphs. Discussiones Mathematicae Graph Theory, Tome 22 (2002) pp. 271-292. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1175/

[000] [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. | Zbl 0664.05019

[001] [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. | Zbl 0575.05028

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

[003] [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.

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

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

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

[007] [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. | Zbl 0996.05065

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

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

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

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

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

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

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

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

[016] [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. | Zbl 0509.05059