The K6K_6 minor conjecture for triangles and induced K3,3K_{3,3} minors

About 2 years old · traced to

Let GG be a graph. A minor of GG is obtained by deleting vertices and edges and contracting edges; an induced minor is obtained by deleting vertices and edges and contracting connected vertex sets. A triangle is a cycle of length three.

K6K_6 minor conjecture. If GG contains K6K_6 as a minor, then GG contains a triangle as a subgraph or GG contains K3,3K_{3,3} as an induced minor.

This proposes a structural consequence of having a K6K_6 minor, separating the presence of a triangle from the induced-minor obstruction K3,3K_{3,3}. The source presents it as an open proposal and gives no resolution.

References

Primary source

Maria Chudnovsky, Meike Hatzel, Tuukka Korhonen, Nicolas Trotignon and Sebastian Wiederrecht, “Unavoidable induced subgraphs in graphs with complete bipartite induced minors”, arXiv:2405.01879 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.