English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The famous K\H{o}nig-Egerv\'ary theorem is equivalent to the statement thatthe matching number equals the vertex cover number for every induced subgraphof some graph if and only if that graph is bipartite. Inspired by this result,we consider the set ${\cal G}_k$ of all graphs such that, for every inducedsubgraph, the maximum number of disjoint paths of order $k$ equals the minimumorder of a set of vertices intersecting all paths of order $k$. For $k\in \{3,4\}$, we give complete structural descriptions of the graphs in ${\cal G}_k$.Furthermore, for odd $k$, we give a complete structural description of thegraphs in ${\cal G}_k$ that contain no cycle of order less than $k$. For thesegraph classes, our results yield efficient recognition algorithms as well asefficient algorithms that determine maximum sets of disjoint paths of order $k$and minimum sets of vertices intersecting all paths of order $k$.

On the K\H{o}nig-Egerv\'ary Theorem for $k$-Paths