Hereditary characterization conjecture for
Hereditary characterization conjecture for
Let be a positive integer, let be the graph class defined in the paper, and for a graph let denote the maximum number of pairwise vertex-disjoint -paths and let denote the minimum size of a vertex set meeting every -path. A subgraph need not be induced.
Hereditary characterization conjecture. For every positive integer , the set equals the set of all graphs such that
for every subgraph of .
The claim generalizes observations proved in the paper for . It gives a proposed characterization of through the equality of maximum -matchings and minimum -vertex covers in every subgraph, but remains open for general positive integer .
Sources & referencesView supporting material
Primary source
Stéphane Bessy, Pascal Ochem and Dieter Rautenbach, “On the Kőnig-Egerváry Theorem for k-Paths”, arXiv:1710.07748 (2017).
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.