Seymour's self-minor conjecture

From Egres Open
Jump to: navigation, search

Every countably infinite graph is a proper minor of itself.


Remarks

Seymour originally conjectured this for any infinite graph, but it turned out to be false [1]. On the other hand, it is known to be true for infinite trees of any size [2]. See also Seymour's self-minor conjecture on the Open Problem Garden.

References

  1. Oporowski, Bogdan. A counterexample to Seymour's self‐minor conjecture Journal of graph theory 14.5 (1990): 521-524, DOI link
  2. Pott, Julian.The self-minor conjecture for infinite trees. preprint (2009), PDF