Bipartite induced subgraphs and well-quasi-ordering

DOI10.1002/JGT.20528zbMATH Open1232.05182arXiv1005.1328OpenAlexW2167462019MaRDI QIDQ3018076FDOQ3018076

Authors: Nicholas Korpelainen, Vadim Lozin 

Publication date: 21 July 2011

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

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.

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

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

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)

Cites Work

• Graph minors. XX: Wagner's conjecture
• Subgraphs and well‐quasi‐ordering
• Induced subgraphs and well‐quasi‐ordering
• A structure theorem for the consecutive 1's property
• Title not available (Why is that?)
• Letter graphs and well-quasi-order by induced subgraphs
• Bi-complement reducible graphs
• Bipartite graphs totally decomposable by canonical decomposition

Cited In (15)

• Hereditary classes of ordered sets of width at most two
• Two forbidden induced subgraphs and well-quasi-ordering
• 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
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)

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)