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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1458,
author = {Hortensia Galeana-S\'anchez and Ricardo G\'omez and Juan Jos\'e Montellano-Ballesteros},
title = {Independent transversals of longest paths in locally semicomplete and locally transitive digraphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {29},
year = {2009},
pages = {469-480},
zbl = {1193.05084},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1458}
}
Hortensia Galeana-Sánchez; Ricardo Gómez; Juan José Montellano-Ballesteros. Independent transversals of longest paths in locally semicomplete and locally transitive digraphs. Discussiones Mathematicae Graph Theory, Tome 29 (2009) pp. 469-480. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1458/
[000] [1] J. Bang-Jensen, Locally semicomplete digraphs: A generalization of tournaments, J. Graph Theory 14 1990) 371-390, doi: 10.1002/jgt.3190140310.
[001] [2] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications (Springer Monographs in Mathematics, 2001). | Zbl 0958.05002
[002] [3] J. Bang-Jensen and G. Gutin, Generalization of tournaments: A survey, J. Graph Theory 14 (1998) 371-390, doi: 10.1002/jgt.3190140310. | Zbl 0920.05033
[003] [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. | Zbl 1103.05036
[004] [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. | Zbl 1103.05034
[005] [6] V. Chvátal and L. Lovász, Every directed graph has a semi-kernel, Lecture Notes in Math. Vol. 411 (Springer, Berlin, 1974). | Zbl 0297.05116
[006] [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. | Zbl 1118.05040
[007] [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. | Zbl 1178.05046
[008] [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. | Zbl 1147.05042
[009] [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.