Induced subgraphs

1. Well-Quasi-Ordering and Induced Subgraphs
Well-Quasi-Ordering
and
Induced Subgraphs
Antonis Antonopoulos (NTUA)
Just Treewidth in Athens '13

2. Well-Quasi-Ordering and Induced Subgraphs
Introduction
Basic Denitions
A binary relationon a setQis called aquasi-orderingif
isreexiveandtransitive.
A sequenceq1;q2; : : :of members ofQis called agood
sequenceif9i<j:qiqj. Otherwise, is called a bad
sequence.
We call (Q;) awell-quasi ordering(wqo) if there is no bad
sequence.
AnidealofQis a subgraphQ
0
ofQsuch that:
qq
0
2Q
0
)q2Q
0
We denote bytheinduced subgraphrelation.
Pnbe the class of graphs withoutPnsubgraph.
LetF(Q) be the class ofQ-labeled graphs (G;f) s.t.G2 F,
wheref:V(G)!Q.

3. Well-Quasi-Ordering and Induced Subgraphs
Main Results
Main Results
For (G;f);(G
0
;f
0
)2 F(Q), we dene (G;f)l(G
0
;f
0
) if
GG
0
andf(v)f
0
((v));8v2V(G), whereis an
isomorphism fromGto an induced subgraph ofG
0
.
Theorem
(Pn(Q);l)is a wqo provided that(Q;)is.
And as a consequence, we have:
Theorem
(Pn;)is a wqo.

4. Well-Quasi-Ordering and Induced Subgraphs
Main Results
Main Results
Theorem's proof can be summarized as follows:
Thetypeof a graph is dened as: a single vertex has type 1, and for
n>1, a graphGhas type at mostnif for some vertexv2V(G),
every connecetd component ofGnvhas type at mostn1.
Lemma
Every graph inPnhas type at mostn.
For a quasi-ordering (Q;), letQ

be theset of all nite
sequencesof members ofQ. Suppose (q1; : : : ;qs) and (q
0
1
; : : : ;q
0
t)
are members ofQ

. (q1; : : : ;qs)

(q
0
1
; : : : ;q
0
t) if
91i1< <ists.t.q1q
0
i1
; : : : ;qsq
0
is
.
Lemma
(Q

;

) is a wqo provided (Q;) is.

5. Well-Quasi-Ordering and Induced Subgraphs
Main Results
Main Results
LetTnbe the class of graphs of type at mostn.
Lemma
(Tn(Q);l) is a wqo provided (Q;) is.
We denote byD(F) the class of all digraphsDs.t. the
underlying graph ofDbelongs toF.
Theorem
letFbe an ideal of graphs with respect to \". Then, the
following are equivalent:
i
(D(F);d)is a wqo.
ii
(D(F);d)is a wqo.
iii
Fis contained inPnfor some positive integer n.

6. Well-Quasi-Ordering and Induced Subgraphs
Main Results
Main Results
LetTnbe the class of graphs of type at mostn.
Lemma
(Tn(Q);l) is a wqo provided (Q;) is.
We denote byD(F) the class of all digraphsDs.t. the
underlying graph ofDbelongs toF.
Theorem
letFbe an ideal of graphs with respect to \". Then, the
following are equivalent:
i
(D(F);d)is a wqo.
ii
(D(F);d)is a wqo.
iii
Fis contained inPnfor some positive integer n.

7. Well-Quasi-Ordering and Induced Subgraphs
Main Results
Main Results
We are going to characterize the idealsFof graphs, such that
(F;) is a wqo.
Theorem
letFbe an ideal of graphs with respect to \". Then, the
following are equivalent:
i
(F;)is a wqo.
ii
(F;)is a wqo.
iii
Fcontains only nitely many graphs Cnand Fn.

8. Well-Quasi-Ordering and Induced Subgraphs
A counterexample
A Counterexample
We 've seen that (Pn;) is a wqo.
IfLis the class of graphs that do not have induced subgraph
Pn, is (Ln;) a wqo?
It has been shown that the answer is yes forn= 4. Forn
bigger than 4, the followingbad sequenceshows that the
answer is no:
For eachn= 3;4: : :, letSnbe the graph onfx1; : : : ;x2ngsuch
thatx1x2;x2x3; : : : ;x2n1x2n;x2nx1are edges ofSn, and the other
edges ofSnare all the pairs of the formx2ix2j. It is not dicult to
see thatS3;S4; : : :is a bad sequence. Moreover, for each
n= 3;4; : : :,Snhasnoinduced subgraphs 2K2and2K2.

9. Well-Quasi-Ordering and Induced Subgraphs
Other Results
Bipartite graphs
LetHbe the class ofbipartitegraphsGsuch thatGdoes not
have an induced subgraphP7,J1orJ2.
Theorem
(H;)is a wqo.
Lemma
Let G be a connected bipartite graph withjV(G)j>1. If the
bipartite complementG of G is also connected, then G has an
induced P7, J1or J2.

10. Well-Quasi-Ordering and Induced Subgraphs
Other Results
Bipartite graphs
Theorem
i
LetG1be the class of graphs without induced K3and
K2+ 2K1. Then(G1;)is a wqo.
ii
LetG2be the class of graphs without induced K3and P5.
Then(G2;)is a wqo.
LetHnbe the class of bipartite graphs without inducedPn
andPn(bipartite complement). Then:
Theorem
H6is a wqo.

11. Well-Quasi-Ordering and Induced Subgraphs
Other Results
References
G. Ding,Subgraphs and Well-Quasi-Ordering, Journal of Graph
Theory, vol. 16, no. 5, 489-502 (1992)
R. Diestel,Graph Theory, Springer-Verlag, 2000
Jir Fiala,Introduction to graph minors and treewidth, Lecture
Notes, 2007
Thank You!