α-diperfect digraphs

• M. Sambinelli USP
• C. N. da Silva UFSCar
• O. Lee UNICAMP

DOI: https://doi.org/10.5753/etc.2018.3173

Abstract

Let D be a digraph. A path partition P of D is a collection of paths such that {V(P) : P ∈ P} is a partition of V(D). We say D is α-diperfect if for every maximum stable set S of D there exists a path partition P of D such that |S ∩ V (P )| = 1 for all P ∈ P and this property holds for every induced subdigraph of D. A digraph C is an anti-directed odd cycle if (i) the underlying graph of C is a cycle x₁x₂ · · · x_2k+1x₁, where k ≥ 2, (ii) the longest path in C has length 2, and (iii) each of the vertices x₁, x₂, x₃, x₄, x₆, x₈, . . . , x_2k is either a source or a sink. Berge (1982) conjectured that a digraph D is α-diperfect if, and only if, D contains no induced anti-directed odd cycle. In this work, we verify this conjecture for digraphs whose underlying graph is series-parallel and for in-semicomplete digraphs.

References

Bang-Jensen, J. r., Guo, Y., Gutin, G., and Volkmann, L. (1997). A classification of locally semicomplete digraphs. Discrete Math., 167/168:101–114. 15th British Combinatorial Conference (Stirling, 1995).

Bang-Jensen, J. r. and Gutin, G. (1998). Generalizations of tournaments: a survey. J. Graph Theory, 28(4):171–202.

Bang-Jensen, J. r., Huang, J., and Prisner, E. (1993). In-tournament digraphs. J. Combin. Theory Ser. B, 59(2):267–287.

Bang-Jensen, J. r., Nielsen, M. H., and Yeo, A. (2006). Longest path partitions in generalizations of tournaments. Discrete Math., 306(16):1830–1839.

Berge, C. (1982). Diperfect graphs. Combinatorica, 2(3):213–222.

Bondy, J. A. and Murty, U. S. R. (2008). Graph theory, volume 244 of Graduate Texts in Mathematics. Springer, New York.

Chen, G., Ehrenmüller, J., Fernandes, C. G., Heise, C. G., Shan, S., Yang, P., and Yates, A. N. (2017). Nonempty intersection of longest paths in series-parallel graphs. Discrete Math., 340(3):287–304.

Chudnovsky, M., Robertson, N., Seymour, P., and Thomas, R. (2006). The strong perfect graph theorem. Ann. of Math. (2), 164(1):51–229.

Galeana-Sánchez, H. and Gómez, R. (2008). Independent sets and non-augmentable paths in generalizations of tournaments. Discrete Math., 308(12):2460–2472.

Gallai, T. and Milgram, A. N. (1960). Verallgemeinerung eines graphentheoretischen Satzes von Rédei. Acta Sci. Math. (Szeged), 21:181–186.

Guo, Y. and Volkmann, L. (1994). Connectivity properties of locally semicomplete digraphs. J. Graph Theory, 18(3):269–280.

Juvan, M., Mohar, B., and Thomas, R. (1999). List edge-colorings of series-parallel graphs. Electron. J. Combin., 6:Research Paper 42, 6 pp. (electronic).

Merker, M. (2015). Decomposing series-parallel graphs into paths of length 3 and triangles. Electronic Notes in Discrete Mathematics, 49:367 – 370.

Meyniel, H. (1989). About colorings, stability and paths in directed graphs. Discrete Math., 74(1-2):149–150. Graph colouring and variations.