Discussiones
Mathematicae Graph Theory 22(2) (2002) 271-292
DOI: https://doi.org/10.7151/dmgt.1175
FAMILIES OF STRONGLY PROJECTIVE GRAPHS
Benoit Larose
Department of Mathematics |
Department of Mathematics and Statistics |
e-mail: larose@discrete.concordia.ca
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.Keywords: distance-transitive graphs, graph homomorphism, graph product.
2000 Mathematics Subject Classification: 05C99, 08A30.
References
[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. |
Received 2 April 2001
Revised 4 December 2001
Close