Subgraphs and well-quasi-ordering.

*(English)*Zbl 0762.05093Let \(K\) be a class, a quasi-ordering \(\preccurlyeq\) on \(K\) is said to be a well-quasi-ordering (shortly a wqo) if for every infinite sequence \(x_ 1,x_ 2,\dots\) of elements of \(K\) there are \(i,j\), \(i<j\), such that \(x_ i\preccurlyeq x_ j\). For the class \(G\) of all finite simple graphs neither the subgraph relation \(\subseteq\) nor the induced subgraph relation \(\preccurlyeq\) is a wqo.

In the paper ideals \(H\) of \(G\) are studied such that \(\subseteq\) or \(\preccurlyeq\) is a wqo on \(H\). The following theorem is proved: Let \(H\) be an ideal of \(G\), with respect to \(\subseteq\), then the following are equivalent: (1) \((H,\subseteq)\) is a wqo; (2) \((H,\preccurlyeq)\) is a wqo; (3) \(H\) contains only finitely many \(C_ n\) and \(F_ n\), where \(C_ n\) is a circuit on \(n\) vertices, \(F_ n\) is the graph on \(\{y_ 1,y_ 2,z_ 1,z_ 2,x_ 1,x_ 2,\dots,x_ n\}\) with the edge set \(\{y_ 1x_ 1,y_ 2x_ 1,z_ 1x_ n,z_ 2x_ n,x_ 1x_ 2,x_ 2x_ 3,\dots,x_{n-1}x_ n\}\).

For \(\preccurlyeq\) three wqo ideals are presented, one being the class of all graphs without the path on \(n\) vertices as a subgraph, two others are classes of bipartite graphs.

Connections between the obtained results and digraphs are considered (although no necessary and sufficient condition for an ideal \(D\) of digraphs for which \((D,\subseteq)\) is a wqo is known yet). Examples are constructed disproving some of the possible generalizations of the stated results.

In the paper ideals \(H\) of \(G\) are studied such that \(\subseteq\) or \(\preccurlyeq\) is a wqo on \(H\). The following theorem is proved: Let \(H\) be an ideal of \(G\), with respect to \(\subseteq\), then the following are equivalent: (1) \((H,\subseteq)\) is a wqo; (2) \((H,\preccurlyeq)\) is a wqo; (3) \(H\) contains only finitely many \(C_ n\) and \(F_ n\), where \(C_ n\) is a circuit on \(n\) vertices, \(F_ n\) is the graph on \(\{y_ 1,y_ 2,z_ 1,z_ 2,x_ 1,x_ 2,\dots,x_ n\}\) with the edge set \(\{y_ 1x_ 1,y_ 2x_ 1,z_ 1x_ n,z_ 2x_ n,x_ 1x_ 2,x_ 2x_ 3,\dots,x_{n-1}x_ n\}\).

For \(\preccurlyeq\) three wqo ideals are presented, one being the class of all graphs without the path on \(n\) vertices as a subgraph, two others are classes of bipartite graphs.

Connections between the obtained results and digraphs are considered (although no necessary and sufficient condition for an ideal \(D\) of digraphs for which \((D,\subseteq)\) is a wqo is known yet). Examples are constructed disproving some of the possible generalizations of the stated results.

Reviewer: M.DemlovĂˇ (Praha)

Full Text:
DOI

##### References:

[1] | Damaschke, J. Graph Theory 14 pp 427– (1990) |

[2] | Stable sets verus independent sets. Discrete Math. Accepted. |

[3] | Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York (1980). · Zbl 0541.05054 |

[4] | Higman, Proc. London Math. Soc. 2 pp 326– (1952) |

[5] | and , Graph minors–A survey. Surveys in Combinatorics, London Mathematics Society Lecture Note 103 (1985). · Zbl 0568.05025 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.