Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl

PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2010 | 30 | 2 | 315-333

Tytuł artykułu

Mácajová and Škoviera conjecture on cubic graphs

Treść / Zawartość

Warianty tytułu

Języki publikacji

EN

Abstrakty

EN
A conjecture of Mácajová and Skoviera asserts that every bridgeless cubic graph has two perfect matchings whose intersection does not contain any odd edge cut. We prove this conjecture for graphs with few vertices and we give a stronger result for traceable graphs.

Słowa kluczowe

Wydawca

Rocznik

Tom

30

Numer

2

Strony

315-333

Opis fizyczny

Daty

wydano
2010
otrzymano
2008-12-31
poprawiono
2009-09-12
zaakceptowano
2009-11-09

Twórcy

  • L.I.F.O., Faculté des Sciences, B.P. 6759, Université d'Orléans, 45067 Orléans Cedex 2, France
  • L.I.F.O., Faculté des Sciences, B.P. 6759, Université d'Orléans, 45067 Orléans Cedex 2, France

Bibliografia

  • [1] J.A. Bondy and U.S.R. Murty, Graph Theory, volume 244 of Graduate Text in Mathematics (Springer, 2008).
  • [2] J. Edmonds, Maximum matching and a polyhedron with (0,1) vertices, J. Res. Nat. Bur. Standards (B) 69 (1965) 125-130.
  • [3] G. Fan and A. Raspaud, Fulkerson's conjecture and circuit covers, J. Combin. Theory (B) 61 (1994) 133-138, doi: 10.1006/jctb.1994.1039.
  • [4] J.L. Fouquet and J.M. Vanherpe, On Fan Raspaud Conjecture, manuscript, 2008.
  • [5] D.R. Fulkerson, Blocking and anti-blocking pairs of polyhedra, Math. Programming 1 (1971) 168-194, doi: 10.1007/BF01584085.
  • [6] T. Kaiser, D. Král and S. Norine, Unions of perfect matchings in cubic graphs, Electronic Notes in Discrete Math. 22 (2005) 341-345, doi: 10.1016/j.endm.2005.06.079.
  • [7] T. Kaiser and A. Raspaud, Non-intersecting perfect matchings in cubic graphs, Electronic Notes in Discrete Math. 28 (2007) 293-299, doi: 10.1016/j.endm.2007.01.042.
  • [8] E. Màcajová and M. Skoviera, Fano colourings of cubic graphs and the Fulkerson conjecture, Theor. Comput. Sci. 349 (2005) 112-120, doi: 10.1016/j.tcs.2005.09.034.
  • [9] E. Màcajová and M. Skoviera, http://garden.irmacs.sfu.ca/?q=op/intersecting two perfect matchings, 2007.
  • [10] P. Seymour, On multi-colourings of cubic graphs, and conjectures of Fulkerson and Tutte, Proc. London Math. Soc. 38 (1979) 423-460, doi: 10.1112/plms/s3-38.3.423.

Typ dokumentu

Bibliografia

Identyfikatory

Identyfikator YADDA

bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1496
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ć.