PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2009 | 29 | 3 | 469-480
Tytuł artykułu

Independent transversals of longest paths in locally semicomplete and locally transitive digraphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
We present several results concerning the Laborde-Payan-Xuang conjecture stating that in every digraph there exists an independent set of vertices intersecting every longest path. The digraphs we consider are defined in terms of local semicompleteness and local transitivity. We also look at oriented graphs for which the length of a longest path does not exceed 4.
Wydawca
Rocznik
Tom
29
Numer
3
Strony
469-480
Opis fizyczny
Daty
wydano
2009
otrzymano
2007-10-26
poprawiono
2009-05-15
zaakceptowano
2009-05-15
Twórcy
  • Instituto de Matemáticas de la Universidad Nacional Autónoma de México, Circuito Exterior, Ciudad Universitaria, C.P. 04510, México D.F., México
  • Instituto de Matemáticas de la Universidad Nacional Autónoma de México, Circuito Exterior, Ciudad Universitaria, C.P. 04510, México D.F., México
  • Instituto de Matemáticas de la Universidad Nacional Autónoma de México, Circuito Exterior, Ciudad Universitaria, C.P. 04510, México D.F., México
Bibliografia
  • [1] J. Bang-Jensen, Locally semicomplete digraphs: A generalization of tournaments, J. Graph Theory 14 1990) 371-390, doi: 10.1002/jgt.3190140310.
  • [2] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Springer Monographs in Mathematics, 2001).
  • [3] J. Bang-Jensen and G. Gutin, Generalization of tournaments: A survey, J. Graph Theory 14 (1998) 371-390, doi: 10.1002/jgt.3190140310.
  • [4] J. Bang-Jensen, M.H. Nielsen and A. Yeo, Longest path partitions in generalizations of tournaments, Discrete Math. 306 (2006) 1830-1839, doi: 10.1016/j.disc.2006.03.063.
  • [5] E. Boros and V. Gurvich, Perfect graphs, kernels, and cores of cooperative games, Discrete Math. 306 (2006) 2336-2354, doi: 10.1016/j.disc.2005.12.031.
  • [6] V. Chvátal and L. Lovász, Every directed graph has a semi-kernel, Lecture Notes in Math. Vol. 411 (Springer, Berlin, 1974).
  • [7] M. Frick, S. Van Aardt, G. Dlamini, J. Dunbar and O. Oellermann, The directed path partition conjecture, Discuss. Math. Graph Theory 25 (2005) 331-343, doi: 10.7151/dmgt.1286.
  • [8] M. Frick, S. Van Aardt, J. Dunbar, M. Nielsen and O. Oellermann, A traceability conjecture for oriented graphs, The Electronic Journal of Combinatorics 15 (2008) #R150.
  • [9] H. Galeana-Sánchez and R. Gómez, Independent sets and non-augmentable paths in generalization of tournaments, Discrete Math. 308 (2008) 2460-2472, doi: 10.1016/j.disc.2007.05.016.
  • [10] J.M. Laborde, C. Payan and N.H. Xuong, Independent sets and longest paths in digraphs, in: Graphs and other combinatorial topics, Proceedings of the Third Czechoslovak Symposium of Graph Theory (1982) 173-177.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1458
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ć.