Packing seagulls (Q2392035)

A seagull in a graph is an induced path with \(3\) vertices. The main result of this very extensive paper is the following: Theorem: If \(G\) is a graph (not equal to \(K_1 + C_5)\)) with \(\alpha(G) \leq 2\), then \(G\) contains \(k\) disjoint seagulls if and only if (a) \(| V(G)| \geq 3k\), (b) \(G\) is \(k\)-connected, (c) for every clique \(C\) of \(G\), if \(D\) denotes the set of vertices in \(V(G)-C\) that have both a neighbor and and a non-neighbor in \(C\), then \(| D| + | V(G)-C| \geq 2k\), and (d) the complement \(\overline{G}\) has a matching with \(k\) edges. The motivation for the study of these results is the Hadwiger conjecture that every graph with \(G\) with \(\chi(G) = t\) contains a \(K_t\)-minor. More precisely, it is motivated by the following open conjecture, which is implied by the Hadwiger conjecture: If \(G\) is a graph with \(\alpha(G) \leq 2\), then \(G\) contains \(K_t\) as a minor for \(t = \lceil | V(G)| /2 \rceil\). It is also shown that there is a polynomial-time algorithm to determine if a graph \(G\) with \(\alpha(G) \leq 2\) has \(k\) vertex-disjoint seagulls, even though it is NP-complete for graphs in general.