Discussiones Mathematicae Graph Theory 29(3) (2009)
469-480
doi: 10.7151/dmgt.1458
Hortensia Galeana-Sánchez, Ricardo Gómez and Juan José Montellano-Ballesteros
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
Keywords: independent set, longest path, locally semicomplete, locally transitive.
2000 Mathematics Subject Classification: 05C20, 05C38.
[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. |
Received 26 October 2007
Revised 15 May 2009
Accepted15 May 2009