Structure theorem for tournaments omitting N 5
Brenda J. Latka · Journal of Graph Theory · 2003
Abstract A finite tournament T is tight if the class of finite tournaments omitting T is well‐quasi‐ordered. We show here that a certain tournament N 5 on five vertices is tight. This is one of the main steps in an exact classification of the tight tournaments, as explained in [10]; the third and final step is carried out in [11]. The proof involves an encoding of the indecomposable tournaments omitting N 5 by a finite alphabet, followed by an application of Kruskal's Tree Theorem. This problem arises in model theory and in computational complexity in a more general form, which remains open: the problem is to give an effective criterion for a finite set { T 1 ,…, T k } of finite tournaments to be tight in the sense that the class of all finite tournaments omitting each of T 1 ,…, T k is well‐quasi‐ordered. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 165–192, 2003