Bipartite induced subgraphs and well-quasi-ordering

DOI10.1002/JGT.20528MaRDI QIDQ3018076zbMATH OpenOpenAlexFDO

Authors Nicholas Korpelainen, Vadim Lozin

Publication date 21 July 2011

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1005.1328

zbMATH Keywords

bipartite graphinduced subgraphwell-quasi-ordering

Mathematics Subject Classification ID

Partial orders, general (06A06) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We study bipartite graphs partially ordered by the induced subgraph relation. Our goal is to distinguish classes of bipartite graphs which are or are not well-quasi-ordered (wqo) by this relation. Answering an open question from cite{Ding92}, 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.

Recommendations

• Two forbidden induced subgraphs and well-quasi-ordering
• Subgraphs and well‐quasi‐ordering
• Graphs without large bicliques and well-quasi-orderability by the induced subgraph relation
• Induced subgraphs and well‐quasi‐ordering
• Labelled induced subgraphs and well-quasi-ordering

Cites work

• scientific article; zbMATH DE number 5720940 (Why is no real title available?)
• A structure theorem for the consecutive 1's property
• Bi-complement reducible graphs
• Bipartite graphs totally decomposable by canonical decomposition
• Graph minors. XX: Wagner's conjecture
• Induced subgraphs and well‐quasi‐ordering
• Letter graphs and well-quasi-order by induced subgraphs
• Subgraphs and well‐quasi‐ordering

Cited in

(15)

• Two forbidden induced subgraphs and well-quasi-ordering
• Hereditary classes of ordered sets of width at most two
• Clique-width and well-quasi-ordering of triangle-free graph classes
• Well-quasi-ordering versus clique-width
• Letter graphs and well-quasi-order by induced subgraphs
• On well quasi-order of graph classes under homomorphic image orderings
• Labelled induced subgraphs and well-quasi-ordering
• Well-quasi-order for permutation graphs omitting a path and a clique
• scientific article; zbMATH DE number 7551866 (Why is no real title available?)
• Labelled well-quasi-order for permutation classes
• Recent progress on well-quasi-ordering graphs
• Combinatorics and algorithms for quasi-chain graphs
• Combinatorics and algorithms for quasi-chain graphs
• Well-quasi-ordering and Embeddability of Relational Structures
• scientific article; zbMATH DE number 4010572 (Why is no real title available?)

This page was built for publication: Bipartite induced subgraphs and well-quasi-ordering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3018076)