PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2002 | 22 | 2 | 271-292
Tytuł artykułu

Families of strongly projective graphs

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Wydawca
Rocznik
Tom
22
Numer
2
Strony
271-292
Opis fizyczny
Daty
wydano
2002
otrzymano
2001-04-02
poprawiono
2001-12-04
Twórcy
  • Department of Mathematics, Champlain Regional College, 900 Riverside St-Lambert, QC, Canada, J4P 3P2
  • Department of Mathematics and Statistics, Concordia University, 1455 de Maisonneuve West, Montréal, QC, Canada, H3G 1M8
Bibliografia
  • [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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1175
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.