Berge's conjecture on alpha-diperfect digraphs
Berge's conjecture on alpha-diperfect digraphs
Let 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 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 -property when every maximum stable set has an orthogonal path partition, and it is -diperfect when every induced subdigraph satisfies the -property. An anti-directed odd cycle is a non-oriented cycle , where , and each of is either a source or a sink. Berge's conjecture. A digraph is -diperfect if and only if 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.