Berge's conjecture on alpha-diperfect digraphs

Let DD be a digraph. A stable set is a set of pairwise non-adjacent vertices, and a path partition is a collection of disjoint paths containing every vertex of DD exactly once. A stable set and a path partition are orthogonal when each path contains exactly one vertex of the stable set. A digraph satisfies the lphalpha-property when every maximum stable set has an orthogonal path partition, and it is lphalpha-diperfect when every induced subdigraph satisfies the lphalpha-property. An anti-directed odd cycle is a non-oriented cycle C=x1x2x2k+1x1C=x_1x_2\dots x_{2k+1}x_1, where k2k\geq 2, and each of x1,x2,x3,x4,x6,x8,,x2kx_1,x_2,x_3,x_4,x_6,x_8,\ldots,x_{2k} is either a source or a sink. Berge's conjecture. A digraph DD is lphalpha-diperfect if and only if DD does not contain an anti-directed odd cycle as an induced subdigraph. Berge's obstruction gives a forbidden-subdigraph direction for alpha-diperfectness; the supplied text does not report a resolution of the characterization.

Sources & referencesView supporting material

Primary source

Lucas Ismaily Bezerra Freitas and Orlando Lee, “3-anti-circulant digraphs are α-diperfect and BE-diperfect”, arXiv:2203.05024 (2022).

Additional references

3 papers in this index state this conjecture (2017–2022). The statement above is taken from the most recent of them; the others are arXiv:2111.12168, arXiv:1708.06691.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.