Packing seagulls

DOI10.1007/S00493-012-2594-2MaRDI QIDQ2392035zbMATH OpenOpenAlexFDO

Authors Maria Chudnovsky, Paul Seymour

Publication date 6 August 2013

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00493-012-2594-2

zbMATH Keywords

Hadwiger conjecturelargest stable set of verticesnumber of disjoint seagulls in a graphpolynomial-time algorithm

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83)

Review text

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.

Recommendations

• Improvements of the theorem of Duchet and Meyniel on Hadwiger's conjecture
• A relative of Hadwiger's conjecture
• scientific article; zbMATH DE number 54802
• Hadwiger's conjecture for graphs with forbidden holes
• An approximate version of Hadwiger's conjecture for claw-free graphs

Cites work

• A special case of Hadwiger's conjecture
• Finding minimum clique capacity
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
• scientific article; zbMATH DE number 3141016 (Why is no real title available?)
• scientific article; zbMATH DE number 3102312 (Why is no real title available?)
• On a special case of Hadwiger's conjecture

Cited in

(14)

• Clique immersions in graphs of independence number two with certain forbidden subgraphs
• A note on Hadwiger's conjecture for \(W_5\)-free graphs with independence number two
• Finding minimum clique capacity
• On the independence polynomial of the corona of graphs
• Hadwiger's conjecture
• An approximate version of Hadwiger's conjecture for claw-free graphs
• Complete graph immersions in dense graphs
• Large minors in graphs with given independence number
• Coloring hypergraphs with excluded minors
• Dense minors of graphs with independence number two
• Dominating K_t-models
• Seymour and Woodall's conjecture holds for graphs with independence number two
• On Seymour's strengthening of Hadwiger's conjecture for graphs with certain forbidden subgraphs
• Odd complete bipartite minors in graphs with independence number two

This page was built for publication: Packing seagulls

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2392035)