Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Twin-width VI: the lens of contraction sequences   A contraction sequence of a graph consists of iteratively merging two of its
vertices until only one vertex remains. The recently introduced twin-width
graph invariant is based on contraction sequences. More precisely, if one puts
red edges between two vertices representing non-homogeneous subsets, the
twin-width is the minimum integer $d$ such that a contraction sequence keeps
red degree at most $d$. By changing the condition imposed on the trigraphs
(i.e., graphs with some edges being red) and possibly slightly tweaking the
notion of contractions, we show how to characterize the well-established
bounded rank-width, tree-width, linear rank-width, path-width, and proper
minor-closed classes by means of contraction sequences. As an application we
give a transparent alternative proof of the celebrated Courcelle's theorem
(actually of its generalization by Courcelle, Makowsky, and Rotics), that
MSO$_2$ (resp. MSO$_1$) model checking on graphs with bounded tree-width (resp.
bounded rank-width) is fixed-parameter tractable in the size of the input
sentence.
  We then explore new avenues along the general theme of contraction sequences
both in order to refine the landscape between bounded tree-width and bounded
twin-width (via spanning twin-width) and to capture more general classes than
bounded twin-width. To this end, we define an oriented version of twin-width,
where appearing red edges are oriented away from the newly contracted vertex,
and the mere red out-degree should remain bounded. Surprisingly, classes of
bounded oriented twin-width coincide with those of bounded twin-width. Finally
we examine, from an algorithmic standpoint, the concept of partial contraction
sequences, where, instead of terminating on a single-vertex graph, the sequence
ends when reaching a particular target class.

20
The categories of this paper are: acc-phys
15
The categories of this paper are: nucl-ex
27
The categories of this paper are: comp-gas
26
The categories of this paper are: bayes-an
25
The categories of this paper are: patt-sol
32
The categories of this paper are: atom-ph
11
The categories of this paper are: hep-lat
21
The categories of this paper are: adap-org
19
The categories of this paper are: eess
31
The categories of this paper are: ao-sci
16
The categories of this paper are: stat
6
The categories of this paper are: astro-ph
13
The categories of this paper are: quant-ph
7
The categories of this paper are: hep-th
8
The categories of this paper are: hep-ex
3
The categories of this paper are: physics