ML p(r)ior | Well-quasi-ordering H-contraction-free graphs

Well-quasi-ordering H-contraction-free graphs

2016-02-01
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.
PDF

Highlights - Most important sentences from the article

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

Related Articles

2018-07-13

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2019-04-05

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
PDF

Highlights - Most important sentences from the article

2018-11-09

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

Highlights - Most important sentences from the article

2018-10-25

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

Highlights - Most important sentences from the article

2018-10-16

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2017-04-24

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

Highlights - Most important sentences from the article

2017-03-15

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article

2016-07-02

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

Highlights - Most important sentences from the article

2018-12-13

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

Highlights - Most important sentences from the article

2018-11-29

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

Highlights - Most important sentences from the article

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
PDF

Highlights - Most important sentences from the article