Note on a min-max conjecture of Woodall
Let \((D,\ell)\) denote a pair consisting of a digraph \(D= (V,A)\) and a nonnegative-integer-valued function \(\ell\) defined on the arcs of \(D\). \(\text{girth}(D,\ell)\) is the length of a shortest cycle and \(\text{trans}(D,\ell)\) is the cardinality of a maximum collection of transversals such that each arc \(\alpha\) is contained in at most \(\ell(\alpha)\) members of this collection. A digraph is called series-parallel if its underlying graph does not contain a subdivision of \(K_4\). The authors prove the following theorem: If \(D\) is a series-parallel digraph and \(D\) has at least one cycle, then \(\text{girth}(D,\ell)= \text{trans}(D,\ell)\). The theorem means truth of Woodall's conjecture when the digraph is series-parallel.
- Complexity of packing common bases in matroids
- \(\alpha\)-diperfect digraphs
- The Merino-Welsh conjecture holds for series-parallel graphs
- Disjoint dijoins for classes of dicuts in finite and infinite digraphs
- On Packing Dijoins in Digraphs and Weighted Digraphs
- A min-max relation on dicuts and dijoins in weighted chordal digraphs
- Partitioning series-parallel multigraphs into v^*-excluding edge covers
This page was built for publication: Note on a min-max conjecture of Woodall
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2746483)
