Browsing Combinatorics and Optimization by Subject "induced path"
Now showing items 1-2 of 2
-
Finding an induced path that is not a shortest path
(Elsevier, 2021-07)We give a polynomial-time algorithm that, with input a graph G and two vertices u; v of G, decides whether there is an induced uv-path that is longer than the shortest uv-path. -
Triangle-free graphs with no six-vertex induced path
(Elsevier, 2018-08)The graphs with no five-vertex induced path are still not understood. But in the triangle-free case, we can do this and one better; we give an explicit construction for all triangle-free graphs with no six-vertex induced ...