5
$\begingroup$

It is well known that the finite rooted trees are well-quasi-ordered by the topological minor relation (a.k.a. homeomorphic embedding). Are they also wqo by the (induced) subgraph relation?

I'm confused because it seems to me that Nash-Williams proof can easily be adapted to induced subgraphs. This would be a stronger (and simpler) result.

Does anyone know a bad sequence?

$\endgroup$

1 Answer 1

8
$\begingroup$

Consider the rooted trees shown below (with root at the top):

   *          *          *          *          *          *  
   |\         |\         |\         |\         |\         |\  
   * *        * *        * *        * *        * *        * *        
   |\         |          |          |          |          |          
   * *        *          *          *          *          *          
              |\         |          |          |          |          
              * *        *          *          *          *   
                         |\         |          |          |   ...
                         * *        *          *          *  
                                    |\         |          |  
                                    * *        *          *  
                                               |\         |  
                                               * *        *  
                                                          |\  
                                                          * *

Clearly none of them is an induced subgraph of another, so this is an infinite antichain in the induced subgraph ordering of finite rooted trees, which is therefore not a well-quasi-order.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.