PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
1999 | 19 | 1 | 5-11
Tytuł artykułu

Cyclically 5-edge connected non-bicritical critical snarks

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
Snarks are bridgeless cubic graphs with chromatic index χ' = 4. A snark G is called critical if χ'(G-{v,w}) = 3, for any two adjacent vertices v and w.
For any k ≥ 2 we construct cyclically 5-edge connected critical snarks G having an independent set I of at least k vertices such that χ'(G-I) = 4.
For k = 2 this solves a problem of Nedela and Skoviera [6].
Słowa kluczowe
Wydawca
Rocznik
Tom
19
Numer
1
Strony
5-11
Opis fizyczny
Daty
wydano
1999
otrzymano
1997-11-24
poprawiono
1998-12-21
Twórcy
  • Universität Bielefeld, Fakultät für Mathematik, Postfach 100131, 33501 Bielefeld, Germany
  • Princeton University, Program in Applied and Computational Mathematics, Fine Hall, Washington Road, Princeton, New Jersey 08544-1000, USA
Bibliografia
  • [1] D. Blanusa, Problem ceteriju boja (The problem of four colors), Hrvatsko Prirodoslovno Drustvo Glasnik Math.-Fiz. Astr. Ser. II, 1 (1946) 31-42.
  • [2] G. Brinkmann and E. Steffen, Snarks and Reducibility, Ars Combin. 50 (1998) 292-296.
  • [3] P.J. Cameron, A.G. Chetwynd and J.J. Watkins, Decomposition of Snarks,J. Graph Theory 11 (1987) 13-19, doi: 10.1002/jgt.3190110104.
  • [4] M.K. Goldberg, Construction of class 2 graphs with maximum vertex degree 3, J. Combin. Theory (B) 31 (1981) 282-291, doi: 10.1016/0095-8956(81)90030-7.
  • [5] R. Isaacs, Infinite families of non-trivial trivalent graphs which are not Tait colorable, Amer. Math. Monthly 82 (1975) 221-239, doi: 10.2307/2319844.
  • [6] R. Nedela and M. Skoviera, Decompositions and Reductions of Snarks, J. Graph Theory 22 (1996) 253-279, doi: 10.1002/(SICI)1097-0118(199607)22:3<253::AID-JGT6>3.0.CO;2-L
  • [7] M. Preissmann, C-minimal Snarks, Annals Discrete Math. 17 (1983) 559-565.
  • [8] M. Skoviera, personal communication.
  • [9] E. Steffen, Critical Non-bicritical Snarks, Graphs and Combinatorics (to appear).
  • [10] E. Steffen, Classifications and Characterizations of Snarks, Discrete Math. 188 (1998) 183-203, doi: 10.1016/S0012-365X(97)00255-0.
  • [11] E. Steffen, On bicritical Snarks, Math. Slovaca (to appear).
  • [12] J.J. Watkins, Snarks, Ann. New York Acad. Sci. 576 (1989) 606-622, doi: 10.1111/j.1749-6632.1989.tb16441.x.
  • [13] J.J. Watkins, R.J. Wilson, A Survey of Snarks, in: Y. Alavi et al. (eds.), Graph Theory, Combinatorics and Applications (Wiley, New York, 1991) 1129-1144.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1081
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ć.