proposition2[theorem]Proposition theorem2[theorem]Theorem
corollary2[theorem]Corollary lemma2[theorem]Lemma claim2[theorem]Claim
property2[theorem]Property Masaryk University, Brno, Czech
republichlineny@fi.muni.czhttps://orcid.org/0000-0003-2125-1514 Masaryk
University, Brno, Czech
republic484988@mail.muni.czhttps://orcid.org/0000-0001-9585-2553 Petr Hliněný
and Jan Jedelský [500]Mathematics of computing Graph theory

#  $\mathcal{H}$-Clique-Width and a Hereditary Analogue of Product Structure

Petr Hliněný  Jan Jedelský

###### Abstract

We introduce a novel generalization of the notion of clique-width which aims
to bridge the gap between classical hereditary width measures and the recently
introduced graph product structure theory. Bounding the new ${\cal H}$-clique-
width, in the special case of ${\cal H}$ being the class of paths, is
equivalent to admitting a hereditary (i.e., induced) product structure of a
path times a graph of bounded clique-width. Furthermore, every graph admitting
the usual (non-induced) product structure of a path times a graph of bounded
tree-width, has bounded ${\cal H}$-clique-width and, as a consequence, it
admits the usual product structure in an induced way. We prove further basic
properties of ${\cal H}$-clique-width in general.

###### keywords:

product structure, hereditary class, clique-width, twin-width

##  1 Introduction

A prominent structural result by Dujmović, Joret, Micek, Morin, Ueckerdt and
Wood [DBLP:journals/jacm/DujmovicJMMUW20], known as the Planar product
structure theorem, claims that every planar graph can be found as a subgraph
in the strong product of a path and a graph of small tree-width. We refer to
Section 2 and Theorem 2.2 for the definitions and details.

The original motivation for this rather recent product structure theorem was
to bound the queue number of planar graphs, but the theorem has quickly found
interesting applications and follow-up results, among which we may mention
[DBLP:journals/corr/abs-2001-08860, DBLP:journals/jacm/DujmovicEGJMM21,
DBLP:journals/siamdm/BonamyGP22, Dujmovic2020Planar,
DBLP:journals/combinatorics/UeckerdtWY22, DBLP:journals/jctb/DujmovicMW23].
Namely, the product structure theory has been used to study non-repetitive
colourings [Dujmovic2020Planar], to design short labelling schemes
[DBLP:journals/jacm/DujmovicEGJMM21, DBLP:journals/siamdm/BonamyGP22], or to
bound the twin-width of planar graphs [DBLP:journals/corr/abs-2202-11858,
DBLP:conf/wg/JacobP22, DBLP:conf/icalp/HlinenyJ23].

The basic goal of the product structure theory can be seen in studying graph
classes which admit such product structure, that is, they can be constructed
as subgraphs of the strong product of a path and a graph of small tree-width.
Within this setting, there are two major restrictions; first that the
containment (subgraph) relation is not induced, and second that this kind of a
superstructure can exist only for sparse graph classes.

We aim to give a different perspective on the product structure (Definition
2.1) addressing both mentioned issues, that is, getting graphs which admit the
traditional product structure as induced subgraphs in such strong product, and
allowing also dense graphs to occur.

Our alternative view is two-sided and is closely related to another classical
structural notion in graph theory – the clique-width measure. On one hand, any
graph admitting the traditional product structure can be obtained as an
induced subgraph of the strong product of a path and a suitable graph of
bounded clique-width and even bounded tree-width (Theorem 4.8). On the other
hand, a graph admits the latter induced product structure, if and only if it
has bounded ${\cal H}$-clique-width where ${\cal H}$ is the class of reflexive
paths (Theorem 4.1). This dual nature of our view is another promising
enhancement. Moreover, we believe this view can contribute to finding
potential algorithmic applications of product structure theory.

The wide scope of our definition suggests to study ${\cal H}$-clique-width for
other graph families ${\cal H}$ in addition to paths, too. We study and
characterize relations of ${\cal H}$-clique-width to ordinary clique-width
(Theorem 3.1), to local clique-width (Theorem 3.5), and in parts to twin-width
(Corollary 4.5). The full potential of this new concept when ${\cal H}$ is a
family of specific graphs other than paths is yet to be explored, especially
in the case of ${\cal H}$ formed by suitable dense graphs. We conclude with a
number of open questions related to the new concept (Section 5).

##  2 Preliminaries

We consider finite simple graphs, i.e. without parallel edges or loops, but in
one specific context (Definition 2.1) we allow graphs with optional
(self-)loops, thereafter called loop graphs. Precisely, a _loop graph_ is a
multigraph allowing loops (at most one per vertex), but not allowing parallel
edges. In the context of loop graphs, we specially call a graph $G$ a
reflexive (loop) graph if every vertex of $G$ has a loop. We naturally use
terms _reflexive path_ , _reflexive clique_ , and _reflexive independent set_
to denote ordinary paths, cliques, and independent sets, respectively, with
loops added to all vertices. We write $G_{1}\subseteq_{i}G_{2}$ to say that
$G_{1}$ is an induced subgraph of $G_{2}$. Note that if
$G_{1}\subseteq_{i}G_{2}$ for loop graphs, then possible loops of $G_{2}$ on
vertices of $G_{1}$ are also inherited.

A graph $G$ is a matching if $G$ is simple and all vertex degrees in $G$ are
$1$. A graph $G\subseteq K_{n,n}$ is an antimatching if $G$ is obtained from
$K_{n,n}$ by removing a matching of $n$ edges. A graph $G$ is a half-graph if
$G$ is a bipartite simple graph with the bipartition
$\\{u_{1},\ldots,u_{n}\\}$ and $\\{v_{1},\ldots,v_{n}\\}$, such that
$u_{i}v_{j}\in E(G)$ if and only if $i\leq j$.

#### Width measures.

As a traditional structural decomposition, a tree decomposition of a graph $G$
is a tuple $(T,{\cal X})$ where $T$ is a tree, and ${\cal X}=\\{X_{t}:t\in
V(T)\\}$ where $X_{t}\subseteq V(G)$ is a collection of bags which satisfy the
following: (i) $\bigcup_{t\in V(T)}X_{t}=V(G)$, (ii) for every vertex $v\in
V(G)$, the set of the nodes $t\in V(T)$ such that $v\in X_{t}$ forms a subtree
in $T$, and (iii) for every edge $uv\in E(G)$, there exists $t\in V(T)$ such
that $\\{u,v\\}\subseteq X_{t}$. The tree-width of $G$ is the minimum of
$\max_{t\in V(T)}|X_{t}|-1$ over all tree decompositions of $G$.

Our work is more closely related to another measure, which is a “dense
counterpart” of tree-width. The clique-width of a graph $G$ is the minimum
integer $\ell$ such that $G$ (irrespective of labelling) is the value of an
algebraic $\ell$-expression defined by the following operations:

  * •

create a new vertex of label (colour) $i$ for some $i\in\\{1,\ldots,\ell\\}$;

  * •

take the disjoint union of two labelled graphs;

  * •

for $1\leq i\not=j\leq\ell$, add all (missing) edges between a vertex of label
$i$ and a vertex of label $j$;

  * •

for $1\leq i\not=j\leq\ell$, recolour each vertex of label $i$ to have label
$j$.

The last measure we consider, twin-width, was introduced a few years ago by
Bonnet et al. in [DBLP:journals/jacm/BonnetKTW22]. A _trigraph_ is a simple
graph $G$ in which some edges are marked as red, and with respect to the red
edges only, we naturally speak about _red neighbours_ and _red degree_ in $G$.
For a pair of (possibly not adjacent) vertices $x_{1},x_{2}\in V(G)$, we
define a contraction of the pair $x_{1},x_{2}$ as the operation creating a
trigraph $G^{\prime}$ which is the same as $G$ except that $x_{1},x_{2}$ are
replaced with a new vertex $x_{0}$ (said to stem from $x_{1},x_{2}$) such
that:

  * •

the (full) neighbourhood of $x_{0}$ in $G^{\prime}$ (i.e., including the red
neighbours), denoted by $N_{G^{\prime}}(x_{0})$, equals the union of the
neighbourhoods $N_{G}(x_{1})$ of $x_{1}$ and $N_{G}(x_{2})$ of $x_{2}$ in $G$
except $x_{1},x_{2}$ themselves, that is,
$N_{G^{\prime}}(x_{0})=(N_{G}(x_{1})\cup
N_{G}(x_{2}))\setminus\\{x_{1},x_{2}\\}$, and

  * •

the red neighbours of $x_{0}$, denoted here by $N_{G^{\prime}}^{r}(x_{0})$,
inherit all red neighbours of $x_{1}$ and of $x_{2}$ and add those in
$N_{G}(x_{1})\Delta N_{G}(x_{2})$, that is,
$N_{G^{\prime}}^{r}(x_{0})=\big{(}N_{G}^{r}(x_{1})\cup
N_{G}^{r}(x_{2})\cup(N_{G}(x_{1})\Delta
N_{G}(x_{2}))\big{)}\setminus\\{x_{1},x_{2}\\}$, where $\Delta$ denotes the
symmetric set difference.

A _contraction sequence_ of a trigraph $G$ is a sequence of successive
contractions turning $G$ into a single vertex, and its width $d$ is the
maximum red degree of any vertex in any trigraph of the sequence. The _twin-
width_ of a trigraph $G$ is the minimum width over all possible contraction
sequences of $G$. The twin-width of a multigraph or a loop graph is defined as
the twin-width of its simplification.

#### Introducing ${\cal H}$-clique-width.

Our main contribution is the following new concept.

######  Definition 2.1 (${\cal H}$-clique-width).

Let ${\cal H}$ be a family of loop graphs, and $\ell>0$ be an integer.
Consider labels of the form $(i,v)$ where $i\in\\{1,\ldots,\ell\\}$ and $v\in
V(H)$ for some (fixed) $H\in{\cal H}$.

  1. a)

For $H\in{\cal H}$, let an $(H,\ell)$-expression be an algebraic expression
using the following four operations on vertex-labelled graphs:

     * •

creating a new vertex with single label $(i,v)$ for some
$i\in\\{1,\ldots,\ell\\}$ and $v\in V(H)$;

     * •

taking the disjoint union of two labelled graphs;

     * •

for $1\leq i\not=j\leq\ell$, _adding edges between $i$ and $j$_, which means
to add all edges between the vertices of label $(i,v)$ and the vertices of
label $(j,w)$ over all pairs $(v,w)\in V(H)^{2}$ such that $vw\in E(H)$
(including the case of a single vertex $v=w$ with a loop, which will often be
assumed to exist for the graphs $H$); and

     * •

for $1\leq i\not=j\leq\ell$, _recolouring $i$ to $j$_, which means to relabel
all vertices with label $(i,v)$ where $v\in\\!V(H)$ to label $(j,v)$.

  2. b)

The _${\cal H}$ -clique-width_ $\mathop{\text{${{\cal H}}$\rm-cw}}(G)$ of a
simple graph $G$ is defined as the smallest integer $\ell$ such that (some
labelling of) $G$ is the value of an $(H,\ell)$-expression for some $H\in{\cal
H}$. If it is not possible to build $G$ this way, then let
$\mathop{\text{${{\cal H}}$\rm-cw}}(G)=\infty$.

Given an $(H,\ell)$-expression of value (a labelled graph) $G$, we use the
following terminology; the graph $H$ is the parameter of the expression, and
when referring to a label $(i,v)$ of $x\in V(G)$, the integer $i$ is the
colour and $v$ the parameter vertex of $x$.

Observe that, throughout an $(H,\ell)$-expression $\varphi$ valued $G$, the
colours of vertices of $G$ may arbitrarily change by the recolouring
operations, but the parameter vertex of every $x\in V(G)$ stays the same (is
uniquely determined for $x$) in $\varphi$.

It is obvious that ${\cal H}$-clique-width (similarly to ordinary clique-
width) is monotone under taking induced subgraphs. On the other hand, it is
not apriori clear whether ${\cal H}$-clique-width is (at least functionally)
closed under taking the complement of a graph; we will address this
interesting issue in the concluding section. Another remark concerns the
family ${\cal H}$ which should be generally treated as an infinite class of
(finite) loop graphs, due to ${\cal H}$-clique-width being asymptotically the
same as ordinary clique-width in the case of finite ${\cal H}$ – see Theorem
3.1.

To further briefly illustrate Definition 2.1, we add few more observations:

######  Claim 1.

  1. a)

If ${\cal H}=\\{K_{1}\\}$, then $\mathop{\text{${{\cal H}}$\rm-cw}}(G)<\infty$
if and only if $G$ has no edges. If ${\cal H}=\\{K_{1}^{\circ}\\}$, where
$K_{1}^{\circ}$ stands for a single vertex with a loop, then
$\mathop{\text{${{\cal H}}$\rm-cw}}(G)=\mathop{\mbox{\rm cw}}(G)<\infty$.

  2. b)

If ${\cal H}$ contains a loop graph with at least one loop, then
$\mathop{\text{${{\cal H}}$\rm-cw}}(G)\leq\mathop{\mbox{\rm cw}}(G)$.

  3. c)

If ${\cal H}=\\{H\\}$, then $\mathop{\text{${{\cal H}}$\rm-cw}}(H_{1})\leq 2$
holds for every simple graph $H_{1}$ obtained from an induced subgraph of $H$
by removing loops.

  4. d)

If ${\cal H}=\\{H\\}$ and $H$ is disconnected, then for every connected simple
graph $G$ we have $\mathop{\text{${{\cal H}}$\rm-
cw}}(G)=\mathop{\text{${\\{H_{0}\\}}$\rm-cw}}(G)$ for some connected component
$H_{0}$ of $H$.

  5. e)

If ${\cal H}=\\{K_{2}\\}$ (no loops), then $\mathop{\text{${{\cal H}}$\rm-
cw}}(G)<\infty$ if and only if $G$ is a simple bipartite graph. More
generally, for any ${\cal H}$, we have $\mathop{\text{${{\cal H}}$\rm-
cw}}(G)<\infty$ for a simple graph $G$, if and only if $G$ has a homomorphism
into some $H\in{\cal H}$.

  6. f)

For any $k\geq 3$ and ${\cal H}=\\{K_{k}\\}$, it is NP-hard to decide whether
$\mathop{\text{${{\cal H}}$\rm-cw}}(G)<\infty$.

  7. g)

Let ${\cal H}$ be a family containing arbitrarily long reflexive paths. If $G$
is any square grid, then $\mathop{\text{${{\cal H}}$\rm-cw}}(G)\leq 5$ (while
$\mathop{\mbox{\rm cw}}(G)$ is unbounded in such case).

a) There is no edge in $K_{1}$, and so Definition 2.1 cannot create an edge in
$G$. On the other hand, $(K_{1}^{\circ},\ell)$-expressions in Definition 2.1
exactly coincide with traditional $\ell$-expressions of clique-width
(replacing every label $i$ with $(i,v)$ where $\\{v\\}=V(K_{1}^{\circ})$).

b) We pick $v\in V(H)$ for $H\in{\cal H}$ such that $v$ has a loop in $H$.
Then, in an ordinary $\mathop{\mbox{\rm cw}}(G)$-expression for $G$, we
replace every label $i$ with $(i,v)$ to get an $(H,\mathop{\mbox{\rm
cw}}(G))$-expression for $G$, similarly to part a).

c) We simply make an $(H,2)$-expression for $H_{1}$ as follows; in an
arbitrary order $V(H_{1})=\\{v_{1},\ldots,v_{n}\\}$ of the vertices, for
$k=1,\ldots,n$, we add a new vertex labelled $(2,v_{k})$, add edges between
$1$ and $2$, and recolour $2$ to $1$. This creates exactly the non-loop edges
of $H_{1}$.

d) This follows from the facts that the recolouring operation of Definition
2.1 does not allow to change the initially assigned parameter vertex of $H$,
and hence every edge of $G$ created within an $(H,\ell)$-expression has a
preimage edge in $H$. So, an expression creating connected $G$ may only use
parameter vertices of a connected component of $H$.

e) Considering the previous argument turned around, every edge created within
an $(H,\ell)$-expression has a unique homomorphic image in $H$ (possibly a
loop). In the opposite direction, for a homomorphism $h:G\to H\in{\cal H}$, we
make an $(H,|V(G)|)$-expression starting with the disjoint union of vertices
labelled $(i_{x},h(x))$ for all $x\in V(G)$ where $i_{x}\not=i_{y}$ for
$x\not=y$, and then simply add the edges of $G$ one by one using the colours
(i.e., $i_{x}$).

f) By e), we have $\mathop{\text{${{\cal H}}$\rm-cw}}(G)<\infty$ if and only
if $G$ is $k$-colourable.

g) Let $G$ be an $a\times b$ grid, i.e., $|V(G)|=ab$. We take $H\in{\cal H}$
such that $|V(H)|\geq b$, choose a consecutive subpath on
$\\{v_{1},\ldots,v_{b}\\}\subseteq V(H)$, and make an $(H,5)$-expression
valued $G$ as follows. As in c), we define an $(H,3)$-(sub)expression creating
a “vertical” copy $P_{1}$ of the path on $b$ vertices, but now using three
colours such that the resulting labels of $P_{1}$ are with alternating colours
$2$ and $3$, precisely as $(2,v_{1})$, $(3,v_{2})$, $(2,v_{3})$,
$(3,v_{4}),\ldots$. We likewise create a copy $P_{2}$ of the same path with
alternating colours in labels $(4,v_{1})$, $(5,v_{2})$, $(4,v_{3})$,
$(5,v_{4}),\ldots$. Then we make a disjoint union and add edges between
colours $2,4$ and between $3,5$ – this creates precisely the “horizontal”
edges between the labels $(2,v_{i})$ and $(4,v_{i})$, and between
$(3,v_{i+1})$ and $(5,v_{i+1})$, for $i=1,3,\ldots$. In a subsequent round, we
recolour colours $2,3$ to $1$ (this concerns only $P_{1}$), and continue the
same process with adding a path $P_{3}$ with alternating colours again $2$ and
$3$, and adding the “horizontal” edges. After $a-1$ rounds, we build the
desired $a\times b$ square grid $G$.

#### Product structure theory.

The strong product $G_{1}\boxtimes G_{2}$ of two simple graphs is the graph
$G$ on the vertex set $V(G):=V(G_{1})\times V(G_{2})$ such that, for any
$[u,u^{\prime}],\,[v,v^{\prime}]\in V(G)$, we have
$\\{[u,u^{\prime}],\,[v,v^{\prime}]\\}\in E(G)$ if and only if ($uv\in
E(G_{1})$ and $u^{\prime}v^{\prime}\in E(G_{2})$) or ($u=v$ and
$u^{\prime}v^{\prime}\in E(G_{2})$) or ($uv\in E(G_{1})$ and
$u^{\prime}=v^{\prime}$).

For an illustration, the strong product $P\boxtimes Q$ of two paths $P,Q$ is
the square grid with diagonals. It may be interesting to observe that, in the
context of loops graphs, if both $G_{1}$ and $G_{2}$ are reflexive, then the
definition of the strong product $G_{1}\boxtimes G_{2}$ could be shortened as
‘$uv\in E(G_{1})$ and $u^{\prime}v^{\prime}\in E(G_{2})$’, and the result
would be the same except that all vertices would have loops.

Origins of graph product structure theory go back to the aforementioned
seminal paper [DBLP:journals/jacm/DujmovicJMMUW20]:

######  Theorem 2.2 ([DBLP:journals/jacm/DujmovicJMMUW20], improved in
[DBLP:journals/combinatorics/UeckerdtWY22]).

Every planar graph is a subgraph of the strong product $P\boxtimes M$ where
$P$ is a path and $M$ is a planar graph of tree-width at most $6$.

There exist alternative refined formulations of Theorem 2.2, such as using the
strong product $P\boxtimes K_{3}\boxtimes M$ where $M$ is now of tree-width at
most $3$ which is of importance in some applications (such as in refining the
upper bound on the queue number of planar graphs).

##  3 Properties of ${\cal H}$-Clique-Width

We first characterize the asymptotic difference between the ordinary clique-
width and the ${\cal H}$-clique-width for families of loop graphs ${\cal H}$.

We recall the concept of neighbourhood diversity by Lampis
[DBLP:journals/algorithmica/Lampis12]. Two vertices $x,y$ of a simple graph
$G$ are of the same neighbourhood type if and only if they have the same set
of neighbours in $V(G)\setminus\\{x,y\\}$. We shall use an adjusted version of
this concept, suitable for our loop graphs; Two vertices $x,y$ of a simple
loop graph $G$ are of the same total neighbourhood type, if and only if they
have the same set of neighbours in $V(G)$ when $x$ counts as a neighbour of
$x$ if there is a loop on $x$ (and likewise with $y$). A loop graph $G$ is of
total neighbourhood diversity at most $d$ if $V(G)$ can be partitioned into
$d$ parts such that every pair in the same part have the same total
neighbourhood type.

The slight, but very important in our context, difference of these two notions
in presence of loops can be observed, e.g., on: loopless cliques $K_{n}$
(neighbourhood diversity $1$ and total neighbourhood diversity $n$) vs.
reflexive cliques $K_{n}^{\circ}$ (total neighbourhood diversity $1$), or
loopless stars $K_{1,n}$ (both neighbourhood diversities equal $2$) vs.
reflexive stars $K_{1,n}^{\circ}$ (total neighbourhood diversity $n$).

A loop graph class ${\cal G}$ is of component-bounded total neighbourhood
diversity if there exists an integer $d$ such that each connected component of
every graph of ${\cal G}$ is of total neighbourhood diversity at most $d$.

######  Theorem 3.1.

Let ${\cal H}$ be a family of loop graphs. There exists a function $f$ such
that, $\mathop{\mbox{\rm cw}}(G)\leq f(\mathop{\text{${{\cal H}}$\rm-cw}}(G))$
holds for all simple graphs $G$, if and only if ${\cal H}$ is of component-
bounded total neighbourhood diversity.

######  Proof 3.2.

In the ‘$\Leftarrow$’ direction, we may assume $G$ is connected (we will later
take the maximum over connected components). By 1 d), $\mathop{\text{${{\cal
H}}$\rm-cw}}(G)=\mathop{\text{${\\{H_{0}\\}}$\rm-cw}}(G)=\ell$ for a connected
component $H_{0}$ of some $H\in{\cal H}$. The total neighbourhood diversity of
$H_{0}$ is at most some constant $d$, by the theorem assumption. Then, in an
$(H_{0},\ell)$-expression for $G$, we may equivalently replace the parameter
vertices of $H_{0}$ by $d$ new colours, giving a $d\ell$-expression for $G$.
So, $\mathop{\mbox{\rm cw}}(G)\leq d\cdot\mathop{\text{${{\cal H}}$\rm-
cw}}(G)$.

A proof of the ‘$\Rightarrow$’ direction is based on the following natural
technical claim:

######  Claim 2 (Ding et al. [DBLP:journals/jct/DingOOV96, Corollary 2.4]).

For every $k$ there exists $m$ such that the following holds. If $F$ is a
bipartite connected simple graph with the bipartition $V(F)=A\cup B$, $|A|\geq
m$ and the vertices of $A$ have pairwise different neighbourhood types (in
$B$), then $F$ contains an induced subgraph isomorphic to one of the following
graphs on $2k$ vertices: a matching, an antimatching, or a half-graph.

Having 2 at hand, we continue as follows. Assume that ${\cal H}$ is not of
component-bounded total neighbourhood diversity. Let $H\in{\cal H}$ (or a
component thereof) be a connected loop graph of total neighbourhood diversity
$\geq c_{1}$, and $C\subseteq V(H)$ be vertices representing these $c_{1}$
total neighbourhood types. By Ramsey theorem, for sufficiently large $c_{1}$
we find a subset $C_{1}\subseteq C$, $|C_{1}|=2c_{2}-1$, such that $C_{1}$
induces a clique or an independent set in $G$, and then we can select
$C_{2}\subseteq C_{1}$, $|C_{2}|=c_{2}$ such that either all vertices of
$C_{2}$ have loops, or none has. We have got one of the two possibilities:

  * •

$C_{2}$ is a reflexive independent set or a loopless clique in $G$.

  * •

Or, all vertices of $C_{2}$ have the same total neighbourhood type in $C_{2}$
(empty or full $C_{2}$), and so they have pairwise different neighbourhood
types in $D:=V(G)\setminus C_{2}$. Consequently, we may apply 2 to the
bipartite subgraph “between” $C_{2}$ and $D$.

Regarding the second point, in more detail, we say that a bipartite graph
$F_{1}$ with a fixed bipartition $V(F_{1})=A_{1}\cup B_{1}$ is a bi-induced
subgraph of a graph $H$, if $F_{1}\subseteq H$ such that every edge of $H$
with one end in $A_{1}$ and the other end in $B_{1}$ belongs to $F_{1}$. 2
hence implies that one of the three claimed subgraphs is bi-induced in $H$.

Altogether, for every $k$ and sufficiently large $c_{1}$ depending on $k$, we
have connected $H\in{\cal H}$ containing one of the five said substructures;
an induced reflexive independent set or an induced loopless clique on $k$
vertices, or a bi-induced matching, a bi-induced antimatching, or a bi-induced
half-graph on $2k$ vertices. In each of these five cases, we can construct a
“grid-like” graph of bounded ${\cal H}$-clique-width whose ordinary clique-
width grows linearly with $k$. We leave details of these natural constructions
for the Appendix.

The following lemma provides remaining technical details for the proof of
Theorem 3.1. It is easy to check that its assumptions cover all five cases of
$H\in{\cal H}$ listed at the end of the proof there.

######  Lemma 3.3.

Let $k\geq 3$ be an integer, and $H_{1}$ be a loop graph satisfying the
following:

  * •

$H_{1}$ is connected.

  * •

There exist sets $A,B\subseteq V(H_{1})$, $|A|=|B|=k$, such that either $A=B$,
or $A\cap B=\emptyset$.

  * •

We can write $A=\\{u_{1},\ldots,u_{k}\\}$ and
$B=\\{u^{\prime}_{1},\ldots,u^{\prime}_{k}\\}$ such that, for some of the
following three conditions on integers $C(i,j)\in\\{$‘ $i<j$’,‘ $i=j$’,‘
$i\not=j$’$\\}$ we have; for all $(i,j)\in\\{1,\ldots,k\\}^{2}$,
$\\{u_{i},u^{\prime}_{j}\\}\in E(H_{1})$ if and only if $C(i,j)$ is false.
(Note that, if $A=B$, we assume $u_{i}=u^{\prime}_{i}$ and deal also with
loops.)

Then, there exists a constant $\ell_{0}$ independent of $k$ such that the
class of graphs of $\\{H_{1}\\}$-clique-width at most $\ell_{0}$ has ordinary
clique-width $\Omega(k)$.

######  Proof 3.4.

We construct, via an $(H_{1},{\cal O}(1))$-expression, a graph $G_{k}$ of
ordinary clique-width $\Omega(k)$ as follows.

Similarly as in 1 c), we create a loopless copy $G^{\prime}_{1}$ of the graph
$H_{1}$, such that every vertex $x\in V(G^{\prime}_{1})$ which is a copy of a
vertex $v\in B$ has the label with colour $2$ and parameter vertex $v$ and, if
$A\not=B$, every vertex $x\in V(G^{\prime}_{1})$ which is a copy of $w\in A$
has the label with colour $1$ and parameter vertex $w$. Vertices of
$V(G^{\prime}_{i})$ that are not copies of $A\cup B$ have labels with colour
$0$ and the respective parameter vertex from $V(H_{1})\setminus(A\cup B)$.

We set $G_{1}:=G^{\prime}_{1}$, and for $a=2,\ldots,k$ we do:

  * •

We, likewise, create a loopless copy $G^{\prime}_{a}$ of $H_{1}$, now with
colour $3$ in the labels of the copy of $A$ in $V(G^{\prime}_{a})$ and, if
$A\not=B$, with colour $4$ in the labels of the copy of $B$ in
$V(G^{\prime}_{a})$. The labels of $V(G^{\prime}_{a})$ besides the copies of
$A\cup B$ are again with colour $0$.

  * •

Then we make a disjoint union $G_{a}:=G_{a-1}\,\dot{\cup}\,G^{\prime}_{a}$,
and add edges between colours $2$ and $3$.

  * •

If $A=B$, we recolour $2$ to $1$ and $3$ to $2$. If $A\not=B$, we recolour $2$
and $3$ to $1$ and $4$ to $2$.

Altogether, the graph $G_{k}$ has $k\cdot|V(H_{1})|$ vertices, $k$ disjoint
copies $G^{\prime}_{a}$ of $H_{1}$, and every copy $G^{\prime}_{a}$ has $k$
vertices which are, in a well-defined way – cf. condition $C(i,j)$, adjacent
to corresponding $k$ vertices of the subsequent copy $G^{\prime}_{a+1}$ (if
$a<k$). There are no other edges in $G_{k}$. For clarity (and in resemblance
to Theorem 4.1), we imagine the copy $G^{\prime}_{a}$ of $H_{1}$ as “column
$a$” of $G_{k}$, and the set of the copies of $u_{i}$ and $u^{\prime}_{i}$ of
$H_{1}$ as “row $i$” of $G_{k}$. Possible remaining vertices of
$G^{\prime}_{a}$ (those of colour $0$ in their label) are not part of any row,
as they do not participate in inter-column edges of $G_{k}$. Observe that, if
$A\not=B$, the adjacency pattern occurring between columns $a$ and $a+1$ is
exactly the same as the edges between $B$ and $A$ in $H_{1}$, and so the same
as the “mirrored” adjacency pattern between the copies of $A$ and of $B$
within column $a$ (or $a+1$).

Now, assume we have an (ordinary) $\ell$-expression $\varphi$ valued $G_{k}$
for some integer $\ell$. We apply an argument which is folklore in this area.
There must exist a subexpression $\varphi_{1}$ of $\varphi$ making a subset of
vertices $X\subseteq V(G_{k})$ (it is irrelevant which of the edges of
$G_{k}[X]$ this $\varphi_{1}$ makes), such that
$\frac{1}{3}|V(G_{k})|\leq|X|\leq\frac{2}{3}|V(G_{k})|$. Let
$\bar{X}=V(G_{k})\setminus X$.

Consider any $1\leq a<k$; then the columns $a$ and $a+1$ differ with respect
to $X$ in at most $3\ell$ rows ($\leq\ell$ if $A=B$); meaning that in $\leq
3\ell$ rows $i$ we have a situation that a vertex of row $i$ in one of the
columns $a$ or $a+1$ belongs to $X$, and a vertex of row $i$ in the other
column belongs to $\bar{X}$. This follows since we have at most $\ell$
different colours in $\varphi_{1}$ which can be used to further distinguish
different adjacencies, as given by the condition $C(i,j)$ of the lemma,
between the columns $a$ and $a+1$, or within each one of the columns $a$ or
$a+1$ if $A\not=B$.

Likewise, at most $\ell$ columns are such that they intersect both $X$ and
$\bar{X}$. This follows similarly since every column is a copy of connected
$H_{1}$, and so it needs in $\varphi_{1}$ a special colour for its (at least
one) “private” edge from $X$ to $\bar{X}$. The two latter conditions together
are in a clear contradiction with
$\frac{1}{3}|V(G_{k})|\leq|X|\leq\frac{2}{3}|V(G_{k})|$ if $\ell\in o(k)$.

Secondly, there is an interesting relation to established concepts in the case
of parameter families ${\cal H}$ of bounded degrees. Let the local clique-
width of a graph $G$ be the integer function $\lambda$ defined as follows;
$\lambda(r)$ is the maximum clique-width of the $r$-neighbourhood of a vertex
$v$ in $G$, over all $v\in V(G)$. We say that a graph class ${\cal G}$ is of
bounded local clique-width if there exists an integer function upper-bounding
the local clique-width of every member of ${\cal G}$. For instance, the class
of grids is of bounded local clique-width, but of unbounded clique-width.

######  Theorem 3.5.

Let ${\cal H}$ be a family of loop graphs of maximum degree $\Delta$. Then the
class of graphs of ${\cal H}$-clique-width at most $\ell$ is of bounded local
clique-width in terms of $\Delta$ and $\ell$.

######  Proof 3.6.

Let $H\in{\cal H}$ and $G$ be a graph that is a value of an
$(H,\ell)$-expression $\varphi$. Choose $x\in V(G)$, and assume a vertex $y\in
V(G)$ at distance at most $r$ from $x$ in $G$. Let $v,w\in V(H)$ be the
parameter vertices in $\varphi$ of $x$ and $y$, respectively. As argued in 1
e), there is a homomorphism $G\to H$ taking a path between $x$ and $y$ into a
walk between $v$ and $w$ in $H$, and so the distance from $v$ to $w$ in $H$ is
at most $r$. Since $\Delta(H)\leq\Delta$, the $r$-neighbourhood of $v$ in $H$
has at most $(\Delta+1)^{r}$ vertices, and hence $\varphi$ restricted to the
$r$-neighbourhood of $x$ in $G$ uses only at most $(\Delta+1)^{r}$ parameter
vertices which can be replaced in $\varphi$ by unique colours. This way we
obtain an (ordinary) $\ell\cdot(\Delta+1)^{r}$-expression whose value is the
$r$-neighbourhood of $x$ in $G$. We can thus set
$f(r):=\ell\cdot(\Delta+1)^{r}$ (independently of $H\in{\cal H}$ and $G$) to
certify bounded local clique-width of every $G$ such that
$\mathop{\text{${{\cal H}}$\rm-cw}}(G)\leq\ell$.

A similar structural relation of ${\cal H}$-clique-width to the parameter
twin-width is stated later in Corollary 4.5, as a consequence of a product-
structure-like characterization.

From Theorem 3.5 we, for instance, immediately get tractability of FO model
checking, which is FPT for all classes of bounded local clique-width — this
well-known fact follows by a combination of the ideas of Frick and Grohe
[DBLP:journals/jacm/FrickG01] and of Dawar, Grohe and Kreutzer
[DBLP:conf/lics/DawarGK07]:

######  Corollary 3.7.

For every family ${\cal H}$ of loop graphs, the FO model checking problem of a
graph $G$ is in FPT when parameterized by the formula, the maximum degree of
${\cal H}$ and the ${\cal H}$-clique-width of $G$. ∎

Furthermore, it may be interesting to ask to which extent Theorem 3.5 can be
reversed. This cannot be done straightforwardly since there are families
${\cal H}$ of unbounded degrees, such that classes of bounded ${\cal
H}$-clique-width not only have bounded local clique-width, but even bounded
ordinary clique-width. One example is ${\cal H}_{1}$ the class of all
reflexive cliques by Theorem 3.1. On the other hand, e.g., for ${\cal H}_{2}$
being the class of all reflexive stars, there are graphs whose ${\cal
H}_{2}$-clique-width is bounded by a constant, and they contain arbitrarily
large induced grids and a universal vertex adjacent to everything (a
construction similar to 1 g) ). Such graph hence have unbounded local clique-
width.

##  4 Approaching Induced Product Structure

In this section we restrict our attention to families ${\cal H}$ formed by
reflexive loop graphs (i.e., all vertices have loops in the graphs of ${\cal
H}$), which makes most natural sense with respect to the strong-product
structure studied.

######  Theorem 4.1.

Let ${\cal H}$ be a family of reflexive loop graphs, and ${\cal H}^{\prime}$
be the family of simple graphs obtained from the graphs of ${\cal H}$ by
removing all loops. For every integer $\ell\geq 2$ the following holds. A
simple graph $G$ is of ${\cal H}$-clique-width at most $\ell$, if and only if
$G$ is isomorphic to an induced subgraph of the strong product
$H^{\prime}\boxtimes M$ where $H^{\prime}\in{\cal H}^{\prime}$ and $M$ is a
simple graph of clique-width at most $\ell$.

######  Proof 4.2.

In the ‘$\Leftarrow$’ direction, it is enough to show that
$\mathop{\text{${{\cal H}}$\rm-cw}}(G)\leq\ell$ for $G:=H^{\prime}\boxtimes
M$. Let $\varphi$ be an $\ell$-expression of the graph $M$, and let
$H^{\circ}$ be obtained from $H^{\prime}$ by adding loops to all vertices. We
are going to transform $\varphi$ into an $(H^{\circ},\ell)$-expression as
follows. First, for each $x\in V(M)$ we independently construct a copy
$H^{\prime}_{x}$ of $H^{\prime}$, using only $2\leq\ell$ colours by 1 c). That
is, the parameter vertex of every $v_{x}\in V(H^{\prime}_{x})$ is the preimage
$v\in V(H^{\prime})$ of $v_{x}$. Then, at every moment the expression
$\varphi$ introduces a new vertex $y\in V(M)$ of colour $i$, we take
(substitute) the copy $H^{\prime}_{y}$ and recolour it to $i$. The remaining
operations (union, recolouring, and adding edges) stay in place in $\varphi$,
but are now applied according to Definition 2.1.

We claim that the value $G$ of the resulting transformed
$(H^{\circ},\ell)$-expression $\sigma$ is $H^{\prime}\boxtimes M$. Indeed, the
vertex set is $V(G)=V(H^{\prime})\times V(M)$, and for each $m\in V(M)$ the
subgraph induced on $V(H^{\prime})\times\\{m\\}$ is a copy of $H^{\prime}$.
For any $[v_{1},m_{1}],[v_{2},m_{2}]\in V(G)$ and $m_{1}\not=m_{2}$; if
$\\{[v_{1},m_{1}],[v_{2},m_{2}]\\}\in E(G)$, then $v_{1}v_{2}\in E(H^{\circ})$
by Definition 2.1, and $m_{1}m_{2}\in E(M)$ by the definition of $\sigma$.
Hence $\\{[v_{1},m_{1}],[v_{2},m_{2}]\\}\in E(H^{\prime}\boxtimes M)$.
Conversely, if $\\{[v_{1},m_{1}],[v_{2},m_{2}]\\}\in E(H^{\prime}\boxtimes
M)$, then, by the definition of $\boxtimes$, $v_{1}v_{2}\in E(H^{\prime})$ or
$v_{1}=v_{2}$, meaning $v_{1}v_{2}\in E(H^{\circ})$, and $m_{1}m_{2}\in E(M)$.
So, the edge $\\{[v_{1},m_{1}],[v_{2},m_{2}]\\}$ has been created by $\sigma$.

In the ‘$\Rightarrow$’ direction, let $\sigma$ be an
$(H^{\circ},\ell)$-expression valued $G$, for some $H^{\circ}\in{\cal H}$. Let
$H^{\prime}\in{\cal H}^{\prime}$ be the corresponding simple graph. We are
going to construct an $\ell$-expression $\varphi$ valued $M$ on the vertex
$V(M)=V(G)$, such that $G\subseteq_{i}H^{\prime}\boxtimes M$. The expression
$\varphi$ simply discards parameter vertices (cf. Definition 2.1) from the
labels in $\sigma$. In particular, $M\supseteq G$. To prove that this is
enough, consider vertices $x,y\in V(G)$ labelled $(i,v)$ and $(j,w)$ by
$\sigma$ (for here, indefinite $i$ and $j$ are irrelevant, and $v$ and $w$ are
uniquely determined by $\sigma$). In $G\subseteq_{i}H^{\prime}\boxtimes M$,
the vertices $x$ and $y$ are represented by $[v,x]$ and $[w,y]$ of the
product. If $xy\in E(G)$, then $xy\in E(M)$ by the previous, and $vw\in
E(H^{\circ})$ by Definition 2.1. Consequently, $\\{[v,x],[w,y]\\}\in
E(H^{\prime}\boxtimes M)$ by $\boxtimes$. The converse direction is analogous.

Theorem 4.1 can be used also to bound the twin-width of graphs of bounded
${\cal H}$-clique-width. To show this, we first prove the following ad-hoc
upper bound.

######  Proposition 4.3.

Let $P$ be a reflexive path and $G$ a simple graph. Then the twin-width of $G$
is at most $5\cdot\mathop{\text{${\\{P\\}}$\rm-cw}}(G)-2$. Consequently,
denoting by ${\cal P}^{\circ}$ the class of all reflexive paths, the twin-
width of any simple graph $G$ is at most $5\cdot\mathop{\text{${{\cal
P}^{\circ}\\!}$\rm-cw}}(G)-2$.

######  Proof 4.4.

Let $G$ be the value of a $(P,\ell)$-expression $\varphi$, where
$\ell=\mathop{\text{${\\{P\\}}$\rm-cw}}(G)$. When constructing a contraction
sequence for $G$, we proceed recursively (bottom-up) along the expression tree
of $\varphi$; processing only the union and recolouring nodes, and at each
node contracting together all vertices of the same label.

Consider a situation at a node with a subexpression $\varphi_{0}$ of
$\varphi$, where $X_{0}\subseteq V(G)$ is the vertex set generated by
$\varphi_{0}$, and let $x^{0}_{(i,v)}$ denote the vertex resulting from the
contractions of all vertices of $X_{0}$ that are of label $(i,v)$ by
$\varphi_{0}$. The core observation is that every vertex of $V(G)\setminus
X_{0}$ has the same adjacency to all vertices forming $x^{0}_{(i,v)}$ by
Definition 2.1, and so the only possible red neighbours of $x^{0}_{(i,v)}$ in
a contraction of $G$ are those that stem from $X_{0}$.

The only possible neighbours of $x^{0}_{(i,v)}$ in the described contraction
of the induced subgraph $G[X_{0}]$ are $x^{0}_{(j,w)}$ where
$j\in\\{1,\ldots,\ell\\}$ and $vw\in E(P)$ – altogether at most $3\ell-1$
choices of potential red neighbours of $x^{0}_{(i,v)}$ in the contraction of
$G[X_{0}]$. If a recolouring operation $i$ to $j$ is encountered after the
node of $\varphi_{0}$, we simply contract each former $x^{0}_{(i,v)}$ with
$x^{0}_{(j,v)}$ over all $v\in X_{0}$, not increasing the previous bound on
the red degree.

Consider now a union node making $X_{2}:=X_{0}\dot{\cup}X_{1}$, where $X_{1}$
has been generated by a sibling subexpression $\varphi_{1}$ of $\varphi$, and
let $x^{1}_{(i,v)}$ analogously denote the vertices resulting from
contractions of $X_{1}$. Let the vertices of $P$ be
$V(P)=(v_{1},\ldots,v_{a})$ in the natural order along the path. For
$k=1,\ldots,a$, and subsequently for $i=1,\ldots,\ell$, we make
$x^{2}_{(i,v_{k})}$ by contracting $x^{0}_{(i,v_{k})}$ with
$x^{1}_{(i,v_{k})}$. Considering the corresponding successive contractions of
the induced subgraph $G[X_{2}]$, the only possible red neighbours of
$x^{2}_{(i,v_{k})}$ are the $\ell$ vertices $x^{2}_{(i^{\prime},v_{k-1})}$,
the up to $2(\ell-1)$ vertices $x^{2}_{(j,v_{k})}$ for $j<i$, or
$x^{0}_{(j,v_{k})}$, $x^{1}_{(j,v_{k})}$ for $j>i$, and the $2\ell$ vertices
$x^{2}_{(i^{\prime\prime},v_{k+1})}$, $x^{2}_{(i^{\prime\prime},v_{k+1})}$.
The maximum possible encountered red degree is thus
$\ell+2(\ell-1)+2\ell=5\ell-2$.

######  Corollary 4.5.

Let ${\cal H}$ be a family of reflexive loop graphs of maximum degree $\Delta$
and twin-width at most $t$. Then the twin-width of any simple graph $G$ is at
most ${\cal O}(t+\Delta\cdot{\mathop{\text{${{\cal H}}$\rm-cw}}(G)})$.

######  Proof 4.6.

By Theorem 4.1, we have $G\subseteq_{i}H^{\prime}\boxtimes M$, where
$H^{\prime}$ is of maximum degree at most $\Delta$ and twin-width at most $t$
and $M$ is of clique-width at most $\ell:=\mathop{\text{${{\cal H}}$\rm-
cw}}(G)$. Since twin-width is monotone under taking induced subgraphs, it is
enough to bound it for the graph $H^{\prime}\boxtimes M$.

By Proposition 4.3 applied to $P$ being a single reflexive vertex, and 1 a),
$M$ is of twin-width at most $k:=5\ell-2$. Then, by Bonnet et al.
[DBLP:conf/soda/BonnetGKTW21] (bounding twin-width of a strong product),
$H^{\prime}\boxtimes M$ is of twin-width at most
$\max\big{\\{}t+\Delta,\,k(\Delta+1)+2\Delta\big{\\}}={\cal O}(t+\Delta\ell)$.

Notice that, for constant $\Delta$, the bound ${\cal
O}(t+\Delta\cdot{\mathop{\text{${{\cal H}}$\rm-cw}}(G)})$ in Corollary 4.5 is
asymptotically best possible; a linear dependence on $t$ (the maximum twin-
width of ${\cal H}$) is necessary due to 1 c), and a linear dependence on
$\mathop{\text{${{\cal H}}$\rm-cw}}(G)$ is, on the other hand, required
already by the subcase of ordinary clique-width. It is however not clear
whether the dependence on $\Delta$ in Corollary 4.5 is necessary at all (it
might be only an artifact of the proof method).

###  4.1 Relations to classical product structure

In regard of the Planar product structure theorem, as introduced in Section 2,
we are especially interested in ${\cal H}$-clique-width for ${\cal H}={\cal
P}^{\circ}$ where ${\cal P}^{\circ}$ is the class of reflexive paths. We get
the following as another immediate consequence of Theorem 4.1:

######  Corollary 4.7.

For every integer $\ell\geq 2$ the following holds. A graph $G$ is isomorphic
to an induced subgraph of the strong product $P\boxtimes M$ where $P$ is a
path and $M$ is a simple graph of clique-width at most $\ell$, if and only if
$\mathop{\text{${{\cal P}^{\circ}\\!}$\rm-cw}}(G)\leq\ell$. ∎

There is, however, a more direct connection between our concept and the
original Planar product structure theorem, formulated in the following:

######  Theorem 4.8.

If a graph $G$ is a subgraph (not necessarily induced) of the strong product
$G\subseteq P\boxtimes M$ where $P$ is a path and $M$ is a simple graph of
tree-width at most $k$, then $\mathop{\text{${{\cal P}^{\circ}\\!}$\rm-
cw}}(G)\leq 6(k+1)\cdot 8^{k+1}$. Moreover, there exists a graph $M_{1}$ of
tree-width at most $6(k+1)\cdot 8^{k+1}$ such that $G$ is isomorphic to an
induced subgraph of the strong product $P\boxtimes M_{1}$.

######  Proof 4.9.

We assume a rooted tree decomposition $(T,{\cal X})$ of width $k$ of the graph
$M$, such that every node of $T$ has at most two children. For a node $t\in
V(T)$, let $X^{+}_{t}\subseteq V(M)$ denote the union of $X_{s}$ where $s$
ranges over $t$ and all descendants of $t$. Let $p(t)$ denote the parent node
of $t$ in $T$, and let $Y_{t}=X^{+}_{t}\setminus X_{p(t)}$ denote the vertices
of $M$ which occur only in the bags of $t$ and its descendants. For the root
$r$ of $T$, let specially $Y_{r}=X^{+}_{r}=V(M)$. Observe that all neighbours
of a vertex $m\in Y_{t}$ in $V(M)\setminus Y_{t}$ must belong to the set
$X_{t}\setminus Y_{t}$, by the interpolation property of a tree decomposition.
Let $q:V(M)\to\\{0,1,\ldots,k\\}$ be a function such that $q$ is injective on
each of the bags $X_{t}$ over $t\in V(T)$ — such $q$ is easily constructed
along the tree $T$ in the root-to-leaves order (in fact, $q$ can be seen as a
monotone cop search strategy on the decomposition of $M$).

Analogously to the treatment in the proof of Theorem 4.1, we refer to the
vertices of $G\subseteq P\boxtimes M$ as to the pairs $[p,m]$ where $p\in
V(P)$ and $m\in V(M)$ in the natural correspondence. When constructing an
expression for the graph $G$, we follow on a high level the tree $T$; at a
node $t\in V(T)$, we will construct precisely the subgraph $G^{t}$ of $G$
induced on the vertex set $(V(P)\times Y_{t})\cap V(G)$. By the previous, all
neighbours of $V(G^{t})$ in the rest of $G$ belong to the set
$W_{t}:=\big{(}V(P)\times(X_{t}\setminus Y_{t})\big{)}\cap V(G)$ where
$|X_{t}\setminus Y_{t}|\leq|X_{t}|\leq k+1$. It will thus be enough to encode
in the colour of each $x\in V(G^{t})$ information about which vertices of
$W_{t}$ are actual neighbours of $x$ in $G$ and, moreover, the colours used
can be “recycled modulo $3$” along the path $P$. This way we will prove that
$\mathop{\text{${{\cal P}^{\circ}\\!}$\rm-cw}}(G)$ is bounded in terms of $k$;
more precisely, that $\mathop{\text{${\\{P^{\circ}\\!\\}}$\rm-cw}}(G)$ is
bounded for $P^{\circ}$ being the reflexive closure of $P$.

Let the vertices of $P$ be $V(P)=(p_{1},\ldots,p_{n})$ in the natural order
along the path, and let $t_{m}\in V(T)$ for $m\in V(M)$ denote the node
closest to the root such that $m\in X_{t_{m}}$ (so, $m\in Y_{t_{m}}$). In more
detail, for each $m\in V(M)$ we create, in a trivial way, a subexpression for
the subgraph $G_{m}$ of $G$ induced by $\big{(}V(P)\times\\{m\\}\big{)}\cap
V(G)$ (which is a copy of a subgraph $P_{0}\subseteq P$). For each vertex
$x\in V(G_{m})$ such that $x=[p_{i},m]$, we give $x$ the label $(c_{x},p_{i})$
where the colour of $x$ is $c_{x}=(0,i\\!\\!\mod
3,\>b_{0},b_{1},\ldots,b_{k},\>d)$ and $b_{j}\in\\{0,1\\}^{3}$,
$d\in\\{0,\ldots,k\\}$ as follows. If $j=q(m^{\prime})$ where $m^{\prime}\in
X_{t_{m}}$ (and recall that $q$ is injective on each bag), then
$b_{j}=(b^{1},b^{2},b^{3})$ where; $b^{1}=1$ if and only if
$\\{x,[p_{i-1},m^{\prime}]\\}\in E(G)$, $b^{2}=1$ if and only if
$\\{x,[p_{i},m^{\prime}]\\}\in E(G)$, and $b^{3}=1$ if and only if
$\\{x,[p_{i+1},m^{\prime}]\\}\in E(G)$. If $j\in\\{0,\ldots,k\\}\setminus
q(X_{t_{m}})$, then let $b_{j}=(0,0,0)$. Finally, $d=q(m^{\prime\prime})$
where $m^{\prime\prime}\in V(M)$ is a neighbour of $m$ in $M$ such that all
neighbours of $m$ belong to $Y_{t_{m^{\prime\prime}}}$– informally,
$m^{\prime\prime}$ is any topmost w.r.t. $T$ neighbour of $m$ in $M$.

For an informal explanation, concerning the above “sketch of encoding”, the
colour $c_{x}$ in the label of $x$ covers all desired information about the
neighbours of $x$ in the set $W_{t_{m}}$ in $G$, for which adjacencies will
created later in the coming expression for $G$. And again on an informal
level, the purpose of the component $d$ of the colour $c_{x}$ is to encode the
moment when all edges of $m$ in $M$ are already created going bottom-up along
the tree $T$.

Let
$\Gamma_{k}:=\\{0,1\\}\times\\{0,1,2\\}\times\\{0,1\\}^{3\cdot(k+1)}\times\\{0,1,\ldots,k\\}$
be a set of colours (where, as above, we have $c_{x}\in\Gamma_{k}$ for every
$x$, and “a half” of the colour space – with the first component equal to $1$,
remains unused so far), and let $\ell=|\Gamma_{k}|=2\cdot 3\cdot
2^{3(k+1)}\cdot(k+1)=6(k+1)\cdot 8^{k+1}$. We construct a
$(P^{\circ}\\!,\ell)$-expression $\varphi=\varphi^{r}$ valued $G$ recursively,
making subexpressions $\varphi^{t}$ valued $G^{t}$ along the nodes $t\in
V(T)$, as follows:

  1. I.

For a node $t\in V(T)$ (including leaves), in the leaf-to-root tree order, we
start with an empty expression $\varphi_{0}$ and $G_{0}^{t}=\emptyset$ if $t$
is a leaf. If $t$ has one child $s$, then we take the expression $\varphi_{0}$
already constructed at $s$, and $G_{0}^{t}=G^{s}$. If $t$ has two children
$s,s^{\prime}$, then we let $\varphi_{0}$ be the union operation over the
expressions constructed at $s$ and $s^{\prime}$, and
$G_{0}^{t}=G^{s}\,\dot{\cup}\,G^{s^{\prime}}$. Note that, in the latter case,
$M$ has no edges between the sets $Y_{s}$ and $Y_{s^{\prime}}$ by the
interpolation property, and so there are no edges between the (disjoint)
subgraphs $G^{s}$ and $G^{s^{\prime}}$ in $G$.

  2. II.

Subsequently, for $Y^{\prime}_{t}:=Y_{t}\cap X_{t}$ (informally,
$Y^{\prime}_{t}$ are the vertices of $M$ whose last bag in $T$ is right at
$t$) we choose an arbitrary order $Y^{\prime}_{t}=(m_{1},\ldots,m_{a})$,
$a=|Y^{\prime}_{t}|$, of these vertices – possibly $a=0$ if
$Y^{\prime}_{t}=\emptyset$. For $i=1,\ldots,a$, we repeat the following:

    1. a)

We start the expression $\varphi_{i}$ by making a union of previous
$\varphi_{i-1}$ (if nonempty) and of the above subexpression constructing
$G_{m_{i}}$.

    2. b)

Now we add in $\varphi_{i}$ all required edges between $G_{m_{i}}$ and
$\big{(}G_{0}^{t}\cup G_{m_{1}}\cup\dots\cup G_{m_{i-1}}\big{)}$. Using
information stored in the labels of $\varphi_{i-1}$ and the labels of vertices
of $G_{m_{i}}$, this is a routine task as follows. For simplicity, we write
$*$ for an arbitrary value.

       * •

Let $j=q(m_{i})$. For $(\alpha,\beta)\in\\{(0,2),(1,0),(2,1)\\}$, we add edges
between each colour $(1,\alpha,\>*,\ldots,b_{j},\ldots,*,\>*)$ where
$b_{j}=(1,*,*)$, and each colour $(0,\beta,\>*,\ldots,*,\>*)$. (Note that only
vertices of $G_{m_{i}}$ may currently hold colours starting with $0$.)

       * •

Similarly, for $(\alpha,\beta)\in\\{(0,0),(1,1),(2,2)\\}$, we add edges
between each colour $(1,\alpha,\>*,\ldots,b_{j},\ldots,*,\>*)$ where
$b_{j}=(*,1,*)$, and each colour $(0,\beta,\>*,\ldots,*,\>*)$.

       * •

And again, for $(\alpha,\beta)\in\\{(0,1),(1,2),(2,0)\\}$, we add edges
between each colour $(1,\alpha,\>*,\ldots,b_{j},\ldots,*,\>*)$ where
$b_{j}=(*,*,1)$, and each colour $(0,\beta,\>*,\ldots,*,\>*)$.

    3. c)

Then we recolour every colour $c=(0,\beta,\>b_{0},\ldots,b_{k},\>d)$ in the
previous, where $\beta\in\\{0,1,2\\}$ and $b_{0},\ldots,b_{k},\>d$ are
arbitrary, to colour $c^{\prime}=(1,\beta,\>b_{0},\ldots,b_{k},\>d)$. This
finishes the expression $\varphi_{i}$ constructing a subgraph on
$V(G_{0}^{t}\cup G_{m_{1}}\cup\dots\cup G_{m_{i}})$.

  3. III.

Continuing on the expression $\varphi_{a}$ from the previous point, we for all
$i\in\\{1,\ldots,a\\}$ do the following. We recolour every colour
$c=\big{(}1,\beta,\>b_{0},\ldots,b_{k},\>q(m_{i})\big{)}$ in $\varphi_{a}$,
where $\beta\in\\{0,1,2\\}$ and $b_{0},\ldots,b_{k}$ are arbitrary, to colour
$c^{\prime}=\big{(}1,\beta,\>(0,0,0)^{k+1}\\!,\>q(m_{i})\big{)}$. (The purpose
is, informally, to prevent creation of further edges from the recoloured
vertices.) This finishes the sought expression $\varphi^{t}$ with intended
value $G^{t}$ at the node $t$.

Now, the constructed $(P^{\circ}\\!,\ell)$-expression $\varphi=\varphi^{r}$
clearly creates (precisely) all vertices and (at least) all edges of $G$, and
uses at most $\ell=6(k+1)\cdot 8^{k+1}$ colours. The proof will be finished
once we prove that no other edges than those of $G$ have been created by
$\varphi$ in $G^{r}$.

There are three points in verification of the last task. First, colouring in
the process of construction of $\varphi$ ensures that no additional edges are
created within each of the graphs $G_{m}$ above, and no edges are ever created
between $G_{m}$ and $G_{m^{\prime}}$ if $mm^{\prime}\not\in E(M)$. The only
operation adding edges in $\varphi$, besides the subexpressions making each
$G_{m}$, is as defined in item IIb) above, and so it always adds only edges
from $V(G_{m_{i}})$ to the rest of the current subgraph. Second, the
operations in IIb) indeed add precisely those edges between $G_{m_{i}}$ and
$\big{(}G_{0}^{t}\cup G_{m_{1}}\cup\dots\cup G_{m_{i-1}}\big{)}$ which exist
in $G$. And third (which relates to both previous points), the “hash” function
$q:V(M)\to\\{0,1,\ldots,k\\}$ used in the construction of our colours indeed
unambiguously identifies neighbours we want to make adjacent as in $G$ thanks
to assumed injectivity of $q$ on each bag of $(T,{\cal X})$ and the
recolouring performed in item III.

Regarding the second part of the claim, we cannot directly employ Theorem 4.1
since that would give us only a factor (of the strong product) of bounded
clique-width, but containing unbounded bipartite cliques. We instead provide
an ad-hoc construction of the desired factor $M_{1}$ which is closely related
to fine details of the $(P^{\circ}\\!,\ell)$-expression $\varphi^{r}$ of $G$
described above.

Let
$\Gamma^{\prime}_{k}:=\\{0,1\\}\times\\{0,1,2\\}\times\\{0,1\\}^{3\cdot(k+1)}$,
i.e., we have got $\Gamma^{\prime}_{k}\times\\{0,1,\ldots,k\\}=\Gamma_{k}$ as
above. Recall also that $Y^{\prime}_{t}:=Y_{t}\cap X_{t}$ for $t\in V(T)$
denotes the vertices of $M$ whose last bag in $T$ (going bottom-up) is right
at $t$, and that we have ordered the members of $Y^{\prime}_{t}$ as
$Y^{\prime}_{t}=(m_{1},\ldots,m_{a})$ where $a=|Y^{\prime}_{t}|$.

We define the sought graph $M_{1}$ such that
$V(M_{1}):=V(M)\times\Gamma^{\prime}_{k}$, and $E(M_{1})\subseteq F$ where
$F=\\{\\{(m,c),(m^{\prime},c^{\prime})\\}:m=m^{\prime}\vee mm^{\prime}\in
E(M)\\}$. This setting clearly implies that tree-width of $M_{1}$ is going to
be at most $(k+1)\cdot|\Gamma^{\prime}_{k}|<6(k+1)\cdot 8^{k+1}$, regardless
of the detailed definition of its edges. We finish the definition of $M_{1}$
as follows:

  1. i.

For each $m\in V(M)$ and $\alpha\in\\{0,1\\}$, we have
$\\{(m,c),(m,c^{\prime})\\}\in E(M_{1})$ if and only if
$c=(\alpha,*,\>*,\ldots,*)$ and $c^{\prime}=(\alpha,*,\>*,\ldots,*)\not=c$.

  2. ii.

For each $m\not=m^{\prime}\in V(M)$ such that $mm^{\prime}\in E(M)$, we may
assume that either $m\in Y^{\prime}_{t}$ and $m^{\prime}\in Y^{\prime}_{u}$
where $u$ is closer to the root of $T$ than $t$, or that $m,m^{\prime}\in
Y^{\prime}_{t}$ and $m$ precedes $m^{\prime}$ in the internal ordering of
$Y^{\prime}_{t}$ as above. Now, we define
$\\{(m,c),(m^{\prime},c^{\prime})\\}\in E(M_{1})$ if and only if, for
$j=q(m^{\prime})$ and some $\alpha\in\\{0,1,2\\}$, one of the following holds:

     * •

$c=(*,\alpha,\>*,\ldots,b_{j},\ldots,*)$, $c^{\prime}=(*,(\alpha+2)\\!\\!\mod
3,\>*,\ldots,*)$ and $b_{j}=(1,*,*)$, or

     * •

$c=(*,\alpha,\>*,\ldots,b_{j},\ldots,*)$, $c^{\prime}=(*,\alpha,\>*,\ldots,*)$
and $b_{j}=(*,1,*)$, or

     * •

$c=(*,\alpha,\>*,\ldots,b_{j},\ldots,*)$, $c^{\prime}=(*,(\alpha+1)\\!\\!\mod
3,\>*,\ldots,*)$ and $b_{j}=(*,*,1)$.

  3. iii.

No other edges exist in $M_{1}$.

Observe that every pair of vertices $(m,c)$ and $(m,c^{\prime})$ such that
$c=(0,\alpha,b_{0},\ldots,b_{k})$ and
$c^{\prime}=(1,\alpha,b_{0},\ldots,b_{k})$ are twins (actually, false twins as
$\\{(m,c),(m,c^{\prime})\\}\not\in E(M_{1})$).

It remains to identify an isomorphism of $G\subseteq P\boxtimes M$ to an
induced subgraph of the product $P\boxtimes M_{1}$. For each vertex $x\in
V(G)$ such that $x=[p_{i},m]$ in $P\boxtimes M$, we assign
$x\mapsto[p_{i},(m,c)]$ in $P\boxtimes M_{1}$ where $c=(a,\>i\\!\\!\mod
3,\>b_{0},\ldots,b_{k})$ is determined as follows:

  * •

The first component $a$ of $c$ is defined inductively for each fixed $m$ as
follows; $a=1$ if there exists $y=[p_{i-1},m]\in V(G)$ such that $xy\not\in
E(G)$ and we have already assigned $y\mapsto[p_{i-1},(m,c^{\prime})]$ where
the first component of $c^{\prime}$ is $0$, and $a=0$ otherwise.

  * •

For each $j\in\\{0,1,\ldots,k\\}$ where $j=q(m^{\prime})$ for some
$m^{\prime}\in X_{t_{m}}$ (and recall that there is at most one such
$m^{\prime}$ for $j$ since $q$ is injective on each bag), we have
$b_{j}=(b^{1},b^{2},b^{3})$ where $b^{1}=1$ if and only if
$\\{x,[p_{i-1},m^{\prime}]\\}\in E(G)$, $b^{2}=1$ if and only if
$\\{x,[p_{i},m^{\prime}]\\}\in E(G)$, and $b^{3}=1$ if and only if
$\\{x,[p_{i+1},m^{\prime}]\\}\in E(G)$.

  * •

If undetermined by the previous point, $b_{j}$ may be chosen arbitrarily.

Analogously to the first part of the proof, it is routine to verify that the
induced subgraph of $P\boxtimes M_{1}$ identified by the defined assignment of
vertices of $G$ is indeed isomorphic to $G$.

######  Remark 4.10.

Theorem 4.8 has a natural and straightforward extension to graphs $P\in{\cal
H}$ where ${\cal H}$ is any class of bounded maximum degree (instead of the
class of paths). We skip details due to their additional technical difficulty.

##  5 Concluding Remarks

The primary focus of our paper is an introduction of a new concept of
potential interest, and as such it naturally brings many questions and open
problems, (some of) which we briefly survey in this last section.

From the TCS perspective, the probably most important question is about the
complexity of computation of ${\cal H}$-clique-width. Computing traditional
clique-width exactly is NP-hard [DBLP:journals/siamdm/FellowsRRS09], and hence
the same holds for computing ${\cal H}$-clique-width exactly in general.
However, a question is whether for some special classes ${\cal H}$ one could
compute exact ${\cal H}$-clique-width faster. This is trivially possible, by 1
c), when ${\cal H}$ is the class of all graphs – which is uninteresting. Is it
true that computing ${\cal H}$-clique-width exactly is NP-hard for every fixed
family ${\cal H}$ except in “similarly trivial” cases?

On the other hand, traditional clique-width can be approximated in FPT time
with respect to the solution value [DBLP:journals/jct/OumS06,
DBLP:journals/siamcomp/HlinenyO08]. A big goal would be to extend this
approximation result to ${\cal H}$-clique-width, perhaps with an additional
parameter capturing some properties of ${\cal H}$. In particular, with respect
to Section 4, we emphasize:

######  Problem 5.1.

Let ${\cal P}^{\circ}$ denote the class of reflexive paths. Can one, for input
graph $G$, approximate $\mathop{\text{${{\cal P}^{\circ}\\!}$\rm-cw}}(G)$ in
FPT time with respect to the solution value?

Next group of questions concerns combinatorial properties proved in this
paper. In regard of Section 3, we bring the following one:

######  Problem 5.2 (cf. Theorem 3.5).

Can we characterize families ${\cal H}$ of loop graphs such that, for all
graphs, bounded ${\cal H}$-clique-width implies bounded local clique-width?
This question may be interesting even when restricted to particular graph
classes which are of unbounded local clique-width.

In regard of Section 4, we ask:

######  Problem 5.3 (cf. Theorem 4.8).

Is it true that for each integer $t$ and every graph $G$ such that
$\mathop{\text{${{\cal P}^{\circ}}$\rm-cw}}(G)\leq t$ and $G$ has no $K_{t,t}$
subgraph, we have $G\subseteq P\boxtimes M$ where $P$ is a path and $M$ is of
tree-width bounded in terms of $t$?

######  Problem 5.4 (cf. Corollary 4.5).

Is it true that for each integer $t$ and every family ${\cal H}$ of reflexive
loop graphs of twin-width at most $t$, the twin-width of any simple graph $G$
is bounded in terms of $t$ and $\mathop{\text{${{\cal H}}$\rm-cw}}(G)$?

Another question, already mentioned in Section 2, is whether ${\cal
H}$-clique-width is (at least asymptotically) closed under taking graph
complement. This is a prominent and desired property of ordinary clique-width.
In more detail, we ask whether, having any simple graph $G$ and its complement
$\bar{G}$, we can bound $\mathop{\text{${{\cal H}}$\rm-cw}}(G)$ in terms of
$\mathop{\text{${{\cal H}}$\rm-cw}}(\bar{G})$. Although we do not have a
simple concrete counterexample at hand, we conjecture this is not possible
with arbitrary ${\cal H}$. One can thus, when being closed under complements
is a desirable property, consider only classes ${\cal H}$ which are closed
under complements themselves (but even that subcase is not trivial), or enrich
Definition 2.1 with an operation of adding edges between labels $(i,v)$ and
$(j,w)$ over all pairs $(v,w)\in V(H)^{2}$ such that $vw\not\in E(H)$ (note
that the latter is much stronger than simply requiring ${\cal H}$ to be
complement-closed).

We also suggest to study the special case of ${\cal H}$-clique-width when
${\cal H}$ is the family of (all) reflexive trees. This subcase might be
interesting already for the traditional product structure, but we have not
seen any particular results in this direction yet. We, however, do not have
any progress in this case so far.

Our last batch of questions concerns possible relations of ${\cal H}$-clique-
width to the currently hot trend of studying structural graph properties
through the lens of FO logic on graphs and of FO transductions –
transformations of one graph into another defined by FO formulas. In this we
use some logic-oriented terms which are not formally defined here (such as, in
particular, of FO transductions) and we refer for their definitions, e.g., to
[DBLP:conf/stacs/Mendez21].

First, one may ask for which families ${\cal H}$, classes of bounded ${\cal
H}$-clique-width are monadically dependent, i.e., such that one cannot FO-
transduce all finite graphs from graphs of bounded ${\cal H}$-clique-width. A
partial answer is provided by Theorem 3.5, but a full characterization of such
classes ${\cal H}$ is currently out of our reach.

Second, it is interesting to investigate whether and when, having a graph
class ${\cal G}$ obtained as an FO transduction of a class of bounded ${\cal
H}$-clique-width, one can find a class ${\cal H}^{+}$ depending on ${\cal H}$
(e.g., ${\cal H}^{+}$ an FO transduction of ${\cal H}$), such that the ${\cal
H}^{+}$-clique-width of ${\cal G}$ is bounded. In relation to our results with
paths and product structure, we formulate the following two specific questions
in this direction:

######  Problem 5.5.

Assume that a graph class ${\cal G}$ is obtained from the class of planar
graphs by an FO transduction $\tau$. Is it true that one can give an FO
transduction $\sigma$, depending on $\tau$, such that the ${\cal
P}^{\sigma}$-clique-width of ${\cal G}$ is bounded where ${\cal P}^{\sigma}$
is the class of loop graphs obtained from the class of all paths by $\sigma$?

5.5 seems to be much easier if we, instead of requiring bounded ${\cal
P}^{\sigma}$-clique-width of every member of ${\cal G}$, require only that
every graph from ${\cal G}$ has a bounded perturbation of bounded ${\cal
P}^{\sigma}$-clique-width.

######  Problem 5.6.

Let ${\cal P}^{\sigma}$ be the class of loop graphs obtained from the class of
all paths by an FO transduction $\sigma$. Assume that ${\cal G}$ is a graph
class of bounded ${\cal P}^{\sigma}$-clique-width and ${\cal G}$ is
monadically stable, meaning that one cannot define on graphs of ${\cal G}$ an
arbitrarily long linear order using FO formulas. Is it then true that there
exists an FO transduction $\tau$, such that ${\cal G}$ is obtained, by $\tau$,
from a graph class that admits the traditional product structure?

Third, Theorem 3.5 and Corollary 3.7 can be read as that if a class ${\cal H}$
is of bounded degree, then the FO model checking problem is FPT on all classes
of bounded ${\cal H}$-clique-width. Classes of bounded degree are a prime
example of those having FO model checking in FPT [see96], and so the following
bold conjecture comes in mind at the end:

######  Problem 5.7.

Let ${\cal H}$ be a class of loop graphs having complexity of the FO model
checking problem in FPT. Is it then true that complexity of the FO model
checking problem is in FPT for every class of bounded ${\cal H}$-clique-width?

## References

  * [1] Marthe Bonamy, Cyril Gavoille, and Michal Pilipczuk.  Shorter labeling schemes for planar graphs.  SIAM J. Discret. Math., 36(3):2082–2099, 2022.
  * [2] Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant.  Twin-width II: small classes.  In SODA, pages 1977–1996. SIAM, 2021.
  * [3] Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant.  Twin-width I: tractable FO model checking.  J. ACM, 69(1):3:1–3:46, 2022.
  * [4] Édouard Bonnet, O-joung Kwon, and David R. Wood.  Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond).  CoRR, abs/2202.11858, 2022.
  * [5] Anuj Dawar, Martin Grohe, and Stephan Kreutzer.  Locally excluding a minor.  In LICS, pages 270–279. IEEE Computer Society, 2007.
  * [6] Patrice Ossona de Mendez.  First-order transductions of graphs (invited talk).  In STACS, volume 187 of LIPIcs, pages 2:1–2:7. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
  * [7] Guoli Ding, Bogdan Oporowski, James G. Oxley, and Dirk Vertigan.  Unavoidable minors of large 3-connected binary matroids.  J. Comb. Theory, Ser. B, 66(2):334–360, 1996.
  * [8] Vida Dujmovic, Louis Esperet, Cyril Gavoille, Gwenaël Joret, Piotr Micek, and Pat Morin.  Adjacency labelling for planar graphs (and beyond).  J. ACM, 68(6):42:1–42:33, 2021.
  * [9] Vida Dujmovic, Louis Esperet, Gwenaël Joret, Bartosz Walczak, and David R. Wood.  Planar graphs have bounded nonrepetitive chromatic number.  Advances in Combinatorics, 3 2020.  doi:10.19086/aic.12100.
  * [10] Vida Dujmovic, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, and David R. Wood.  Planar graphs have bounded queue-number.  J. ACM, 67(4):22:1–22:38, 2020.
  * [11] Vida Dujmovic, Pat Morin, and David R. Wood.  Graph product structure for non-minor-closed classes.  J. Comb. Theory, Ser. B, 162:34–67, 2023.
  * [12] Zdenek Dvořák, Tony Huynh, Gwenaël Joret, Chun-Hung Liu, and David R. Wood.  Notes on graph product structure theory.  In 2019-20 MATRIX Annals, pages 513–533, Cham, 2021. Springer International Publishing.
  * [13] Michael R. Fellows, Frances A. Rosamond, Udi Rotics, and Stefan Szeider.  Clique-width is NP-complete.  SIAM J. Discret. Math., 23(2):909–939, 2009.
  * [14] Markus Frick and Martin Grohe.  Deciding first-order properties of locally tree-decomposable structures.  J. ACM, 48(6):1184–1206, 2001.
  * [15] Petr Hlinený and Jan Jedelský.  Twin-width of planar graphs is at most 8, and at most 6 when bipartite planar.  In ICALP, volume 261 of LIPIcs, pages 75:1–75:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023.
  * [16] Petr Hliněný and Sang-il Oum.  Finding branch-decompositions and rank-decompositions.  SIAM J. Comput., 38(3):1012–1032, 2008.
  * [17] Hugo Jacob and Marcin Pilipczuk.  Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs.  In WG, volume 13453 of Lecture Notes in Computer Science, pages 287–299. Springer, 2022.
  * [18] Michael Lampis.  Algorithmic meta-theorems for restrictions of treewidth.  Algorithmica, 64(1):19–37, 2012.
  * [19] Sang-il Oum and Paul Seymour.  Approximating clique-width and branch-width.  J. Comb. Theory, Ser. B, 96(4):514–528, 2006.
  * [20] D. Seese.  Linear time computable problems and first-order descriptions.  Math. Structures Comput. Sci., 6(6):505–526, 1996.
  * [21] Torsten Ueckerdt, David R. Wood, and Wendy Yi.  An improved planar graph product structure theorem.  Electron. J. Comb., 29(2), 2022.