The Library
Bipartite induced subgraphs and well-quasi-ordering
Tools
Tools
Tools
Korpelainen, Nicholas and Lozin, Vadim V.. (2011) Bipartite induced subgraphs and well-quasi-ordering. Journal of Graph Theory, Volume 67 (Number 3). pp. 235-249. ISSN 0364-9024
Full text not available from this repository.
Official URL: http://dx.doi.org/10.1002/jgt.20528
Abstract
We study bipartite graphs partially ordered by the induced subgraph relation. Our goal is to distinguish classes of bipartite graphs that are or are not well-quasi-ordered (wqo) by this relation. Answering an open question from [J Graph Theory 16 (1992), 489-502], we prove that P(7)-free bipartite graphs are not wqo. On the other hand, we show that P(6)-free bipartite graphs are wqo. We also obtain some partial results on subclasses of bipartite graphs defined by forbidding more than one induced subgraph. (C) 2011 Wiley Periodicals, Inc. J Graph Theory 67: 235-249, 2011
| Item Type: | Journal Article |
|---|---|
| Subjects: | Q Science > QA Mathematics |
| Divisions: | Faculty of Science > Mathematics |
| Library of Congress Subject Headings (LCSH): | Bipartite graphs, Graph theory |
| Journal or Publication Title: | Journal of Graph Theory |
| Publisher: | John Wiley & Sons Ltd. |
| ISSN: | 0364-9024 |
| Date: | 2011 |
| Volume: | Volume 67 |
| Number: | Number 3 |
| Page Range: | pp. 235-249 |
| Identification Number: | 10.1002/jgt.20528 |
| Status: | Peer Reviewed |
| Publication Status: | Published |
| Funder: | University of Warwick |
| References: | [1] A. Brandst¨adt, V. B. Le, and J. P. Spinrad, Graph Classes: A Survey, SIAM Monograph on Discrete Mathematics and Applications 3, SIAM, Philadelphia, 1999. [2] P. Damaschke, Induced subgraphs and well-quasi-ordering, J Graph Theory 14 (1990), 427–435. [3] G. Ding, Subgraphs and well-quasi-ordering, J Graph Theory 16 (1992), 489–502. [4] J.-L. Fouquet, V. Giakoumakis, and J. M. Vanherpe, Bipartite graphs totally decomposable by canonical decomposition, Inter J Found Comput Sci 10 (1999), 513–533. [5] V. Giakoumakis and J.-M. Vanherpe, Bi-complement reducible graphs, Adv Appl Math 18 (1997), 389–402. [6] V. V. Lozin and G. Rudolf, Minimal universal bipartite graphs, Ars Combin 84 (2007), 345–356. [7] M. Petkovˇsek, Letter graphs and well-quasi-order by induced subgraphs, Discrete Math 244 (2002), 375–388. [8] N. Robertson and P. D. Seymour, Graph minors. XX. Wagner’s conjecture, J Combin Theory Ser B 92 (2004), 325–357. [9] A. C. Tucker, A structure theorem for the consecutive l’s property, J Combin Theory Ser B 12 (1972), 153–162. |
| URI: | http://wrap.warwick.ac.uk/id/eprint/41328 |
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
 |
View Item |
