Korpelainen, Nicholas and Lozin, Vadim V.. (2011) Two forbidden induced subgraphs and well-quasi-ordering. Discrete Mathematics & Theoretical Computer Science, Vol.311 (No.16). pp. 1813-1822. ISSN 1365-8050

Full text not available from this repository.

Abstract

It is known that a class of graphs defined by a single forbidden induced subgraph G is well-quasi-ordered by the induced subgraph relation if and only if G is an induced subgraph of P(4). However, very little is known about well-quasi-ordered classes of graphs defined by more than one forbidden induced subgraph. We conjecture that for any natural number k, there are finitely many minimal classes of graphs defined by k forbidden induced subgraphs which are not well-quasi-ordered by the induced subgraph relation and prove the conjecture for k = 2. We explicitly reveal many of the minimal classes defined by two forbidden induced subgraphs which are not well-quasi-ordered and many of those which are well-quasi-ordered by the induced subgraph relation.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science > Mathematics
Library of Congress Subject Headings (LCSH):	Graph theory
Journal or Publication Title:	Discrete Mathematics & Theoretical Computer Science
Publisher:	D M T C S
ISSN:	1365-8050
Date:	2011
Volume:	Vol.311
Number:	No.16
Page Range:	pp. 1813-1822
Identification Number:	10.1016/j.disc.2011.04.023
Status:	Peer Reviewed
Publication Status:	Published
References:	[1] A. Brandstädt, (P5, diamond)-free graphs revisited: structure and linear time optimization, Discrete Appl. Math. 138 (2004) 13–27. [2] A. Brandstädt, S. Mahfud, Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time, Inform. Process. Lett. 84 (2002) 251–259. [3] P. Damaschke, Induced subgraphs and well-quasi-ordering, J. Graph Theory 14 (1990) 427–435. [4] Guoli Ding, Subgraphs and well-quasi-ordering, J. Graph Theory 16 (1992) 489–502. [5] Guoli Ding, Stable sets versus independent sets, Discrete Math. 117 (1993) 73–87. [6] G. Higman, Ordering by divisibility of abstract algebras, Proc. Lond. Math. Soc. 2 (1952) 326–336. [7] N. Korpelainen, V. Lozin, Bipartite induced subgraphs and well-quasi-ordering, J. Graph Theory (2011) published online, doi:10.1002/jgt.20528. [8] J.B. Kruskal, Well-quasi-ordering, the tree theorem, and Vazsonyi’s conjecture, Trans. Amer. Math. Soc. 95 (1960) 210–225. [9] R. McConnell, J.P. Spinrad, Modular decomposition and transitive orientation, Discrete Math. 201 (1999) 189–241. [10] S. Olariu, Paw-free graphs, Inform. Process. Lett. 28 (1988) 53–54. [11] M. Petkovšek, Letter graphs and well-quasi-order by induced subgraphs, Discrete Math. 244 (2002) 375–388. [12] N. Robertson, P.D. Seymour, Graph Minors. XX. Wagner’s conjecture, J. Combin. Theory Ser. B 92 (2004) 325–357. [13] I.E. Zverovich, A solution to a problem of Jacobson, Kézdy and Lehel, Graphs Combin. 20 (2004) 571–577.
URI:	http://wrap.warwick.ac.uk/id/eprint/39489

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item