### Well-quasi-ordering H-contraction-free graphs

**2016-02-01**

1602.00733 | math.CO

A well-quasi-order is an order which contains no infinite decreasing sequence
and no infinite collection of incomparable elements. In this paper, we consider
graph classes defined by excluding one graph as contraction. More precisely, we
give a complete characterization of graphs H such that the class of
H-contraction-free graphs is well-quasi-ordered by the contraction relation.
This result is the contraction analogue on the previous dichotomy theorems of
Damsaschke [Induced subgraphs and well-quasi-ordering, Journal of Graph Theory,
14(4):427-435, 1990] on the induced subgraph relation, Ding [Subgraphs and
well-quasi-ordering, Journal of Graph Theory, 16(5):489-502, 1992] on the
subgraph relation, and B{\l}asiok et al. [Induced minors and
well-quasi-ordering, ArXiv e-prints, 1510.07135, 2015] on the induced minor
relation.

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**2018-07-13**

1807.04969 | math.CO

Let $H$ be a planar graph. By a classical result of Robertson and Seymour,
there is a function $f:\m… show more

**2018-12-08**

1812.03250 | cs.DM

Given a graph $G=(V,E)$ and a set $S_0\subseteq V$, an irreversible
$k$-threshold conversion process… show more

**2019-04-05**

1904.02951 | math.CO

A metric graph is a pair $(G,d)$, where $G$ is a graph and $d:E(G)
\to\mathbb{R}_{\geq0}$ is a dista… show more

**2018-11-09**

1811.04801 | cs.DM

The $k$-dimensional Weisfeiler-Leman algorithm ($k$-WL) is a fruitful
approach to the Graph Isomorph… show more

**2018-10-25**

1810.10940 | cs.DS

The maximum independent set problem is known to be NP-hard in the class of
subcubic graphs, i.e. gra… show more

**2018-10-16**

1810.06872 | cs.CC

A semitotal dominating set of a graph $G$ with no isolated vertex is a
dominating set $D$ of $G$ suc… show more

**2016-05-29**

1605.09055 | math.CO

If a graph has $n\ge4k$ vertices and more than $n^2/4$ edges, then it
contains a copy of $C_{2k+1}$.… show more

**2016-08-26**

1608.07413 | cs.DM

A \emph{long unichord} in a graph is an edge that is the unique chord of some
cycle of length at lea… show more

**2017-04-24**

1704.07284 | cs.DS

For a fixed collection of graphs ${\cal F}$, the ${\cal F}$-M-Deletion
problem consists in, given a … show more

**2017-03-15**

1703.05102 | cs.DS

Deciding whether a given graph has a square root is a classical problem that
has been studied extens… show more

**2018-09-14**

1809.05443 | cs.DM

A graph $G$ realizes the degree sequence $S$ if the degrees of its vertices
is $S$. Hakimi gave a ne… show more

**2018-03-20**

1803.07581 | cs.DM

A class $\mathcal{F}$ of graphs has the induced Erd\H{o}s-P\'osa property if
there exists a function… show more

**2016-07-02**

1607.00476 | cs.DM

A graph is equimatchable if all of its maximal matchings have the same size.
A graph is claw-free if… show more

**2018-12-13**

1812.05314 | math.CO

A graph is CIS if every maximal clique interesects every maximal stable set.
Currently, no good char… show more

**2018-11-29**

1811.12252 | cs.DM

We consider the Graph Isomorphism problem for classes of graphs characterized
by two forbidden induc… show more

**2017-08-31**

1708.09686 | cs.DM

A \emph{biclique} is a maximal bipartite complete induced subgraph of $G$.
The \emph{biclique graph}… show more