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

### 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.

Highlights - Most important sentences from the article

Let $H$ be a planar graph. By a classical result of Robertson and Seymour, there is a function $f:\m… show more 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 Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 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 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 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 Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 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 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 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 Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 2018-11-29 1811.12252 | cs.DM We consider the Graph Isomorphism problem for classes of graphs characterized by two forbidden induc… show more 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