# On rank-width of even-hole-free graphs

Isolde Adler, Ngoc Khang Le, Haiko Müller, Marko Radovanovic, Nicolas Trotignon, Kristina Vuskovic

<figure><img src="image_1.png" /></figure>

► To cite this version:

Isolde Adler, Ngoc Khang Le, Haiko Müller, Marko Radovanovic, Nicolas Trotignon, et al. On rank-width of even-hole-free graphs. Discrete Mathematics and Theoretical Computer Science, 2017, 19 (1). hal-01719181

HAL Id: hal-01719181

https://hal.science/hal-01719181v1

Submitted on 12 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>
# On rank-width of (diamond, even hole)-free graphs

Isolde Adler<fnref n="1" />

Ngoc Khang Le<fnref n="2" />,<fnref n="3" />*

Haiko Müller<fnref n="1" />

Marko Radovanović<fnref n="4" />†

Nicolas Trotignon<fnref n="2" />

Kristina Vušković<fnref n="1" />,<fnref n="5" />‡

received 5th Dec. 2016, revised 1st Aug. 2017, accepted 3rd Aug. 2017.

We present a class of (diamond, even hole)-free graphs with no clique cutset that has unbounded rank-width.

In general, even-hole-free graphs have unbounded rank-width, because chordal graphs are even-hole-free. A. A. da Silva, A. Silva and C. Linhares-Sales (2010) showed that planar even-hole-free graphs have bounded rank-width, and N. K. Le (2016) showed that even-hole-free graphs with no star cutset have bounded rank-width. A natural question is to ask, whether even-hole-free graphs with no clique cutsets have bounded rank-width. Our result gives a negative answer. Hence we cannot apply the meta-theorem by Courcelle, Makowsky and Rotics, which would provide efficient algorithms for a large number of problems, including the maximum independent set problem, whose complexity remains open for (diamond, even hole)-free graphs.

**Keywords:** even-hole-free graph, (diamond, even hole)-free graph, clique cutset, clique-width, rank-width

## 1 Introduction

In a graph $G$ a *hole* is a chordless cycle of length at least four. A hole is *even* or *odd* depending on the parity of the size of its vertex set. An $n$-hole is a hole on $n$ vertices. A graph $G$ contains a graph $F$, if $F$ is isomorphic to an induced subgraph of $G$. $G$ is *$F$-free* if it does not contain $F$, and for a family of graphs $\mathcal{F}$, $G$ is *$\mathcal{F}$-free* if for every $F \in \mathcal{F}$, $G$ does not contain $F$. A *diamond* is the graph obtained by removing one edge from a complete graph on four vertices. In this paper we study (diamond, even hole)-free graphs.

<footnote n="1">¹ School of Computing, University of Leeds, United Kingdom</footnote>

<footnote n="2">² CNRS, ENS de Lyon, LIP, France</footnote>

<footnote n="3">³ Université de Lyon, France</footnote>

<footnote n="4">⁴ Faculty of Mathematics, University of Belgrade, Serbia</footnote>

<footnote n="5">⁵ Faculty of Computer Science (RAF), Union University, Serbia</footnote>

<footnote>* Partially supported by ANR project Stint under reference ANR-13-BS02-0007 and by the LABEX MILYON (ANR-10-LABX-0070) of Université de Lyon, within the program "Investissements d'Avenir" (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR).</footnote>

<footnote>† Partially supported by Serbian Ministry of Education, Science and Technological Development project 174033.</footnote>

<footnote>‡ Partially supported by EPSRC grant EP/N019660/1, by Serbian Ministry of Education, Science and Technological Development projects 174033 and III44006.</footnote>
2 Isolde Adler, Ngoc Khang Le, Haiko Müller, Marko Radovanović, Nicolas Trotignon, Kristina Vušković

Even-hole-free graphs have been studied considerably in the last two decades (see surveys [22, 23]), and yet some of the key algorithmic questions remain open for this class. Finding a largest (weighted) clique in an even-hole-free graph can be done in polynomial time. As observed by Farber [14], 4-hole-free graphs have $O(n^2)$ maximal cliques, so one can list them all in polynomial time. One can do better for even-hole-free graphs, by exploiting structural properties of the class. In [12] it is shown that every even-hole-free graph has a vertex whose neighbourhood is chordal (i.e. hole-free), and in [1] it is shown that an ordering of such vertices can be found using LexBFS, resulting in an $O(nm)$-time algorithm for maximum weighted clique problem for even-hole-free graphs. This algorithm is in fact robust: for any input graph $G$, it either outputs a maximum weighted clique of $G$ or a certificate that $G$ is not even-hole-free. Even-hole-free graphs can be recognized in polynomial time, as first shown in [6], with currently best complexity of $O(n^{11})$ [4]. This result is based on a decomposition theorem for even-hole-free graphs from [13] that states that every even-hole-free graph is either simple in some sense, or has a star cutset or a 2-join. In [2] it is shown that every even-hole-free graph $G$ has a vertex whose neighborhood is a union of two (possibly empty) cliques, implying that $\chi(G) \le 2\omega(G) - 1$. Despite all these attempts to understand the structure of even-hole-free graphs, the complexity of the stable set and coloring problems remains open for this class.

For several subclasses of even-hole-free graphs these problems are solved in polynomial time. Of particular interest is the class of (diamond, even hole)-free graphs. The class was first studied in [18] where it was shown that (diamond, even hole)-free graphs can be decomposed by bisimplicial cutsets (a special type of a star cutset that consists of two, possibly empty, cliques) and 2-joins. One of the consequences of this decomposition theorem is the existence of a vertex that is either of degree 2 or is simplicial (i.e., its neighborhood is a clique), implying that the class is $\beta$-perfect, and for every graph $G$ in the class $\chi(G) \le \omega(G) + 1$. The $\beta$-perfection implies that the class can be colored in polynomial time by coloring greedily on a particular, easily constructible, ordering of vertices. The complexity of the stable set problem remains open for this class.

One of the motivations for the study of even-hole-free graphs is their connection to $\beta$-perfect graphs introduced by Markossian, Gasparian and Reed [20]. For a graph $G$, let $\delta(G)$ denote the minimum degree of a vertex of $G$. Consider the following total order on $V(G)$: order the vertices by repeatedly removing a vertex of minimum degree in the subgraph of vertices not yet chosen and placing it after all the remaining vertices but before all the vertices already removed. Coloring greedily on this order gives the upper bound: $\chi(G) \le \beta(G)$, where $\beta(G) = \max\{\delta(H) + 1 : H$ is an induced subgraph of $G\}$. A graph is $\beta$-perfect if for each induced subgraph $H$ of $G$, $\chi(H) = \beta(H)$. It is easy to see that $\beta$-perfect graphs are a proper subclass of even-hole-free graphs.

Tree-width is a well-known graph invariant, introduced by Robertson and Seymour in [21]. Many problems that are NP-hard in general become tractable on graph classes of bounded tree-width [8]. Similarly, clique-width, introduced by Courcelle, Engelfriet and Rozenberg in [9], allows for many hard problems to become tractable on graph classes of bounded clique-width [10]. This includes finding the largest clique or independent set, and deciding if a colouring with at most $k$ colors exists (for fixed $k \in \mathbb{N}$). While bounded tree-width implies bounded clique-width, the converse is not true in general. Graph classes of bounded tree-width are necessarily sparse. In contrast, there exist dense graph classes with bounded clique-width. This makes clique-width particularly interesting in the study of algorithmic properties of hereditary graph classes. The notion of rank-width was defined by Oum and Seymour in [16], where they use it for an approximation algorithm for clique-width. They also show that rank-width and clique-width are equivalent, in the sense that a graph class has bounded rank-width if, and only if, it has bounded clique-width. Mean-
while, the structure of graphs of bounded rank-width is studied widely, and it turns out that rank-width is
an elegant notion, that also provides a better understanding of graph classes of bounded clique-width.

Rank-width of subclasses of even-hole-free graphs has also been studied. In [11] it is shown that planar
even-hole-free graphs have tree-width at most 49. In [19] it is shown that even-hole-free graphs with no
star cutset have bounded rank-width. Even-hole-free graphs in general do not have bounded tree-, clique-,
rank-width, as they contain all chordal graphs. Algorithms for chordal graphs follow from their decom-
position by clique cutsets, and clique cutsets in general agree well with a number of problems, including
stable set and coloring. An example of even-hole-free graphs with no clique cutset and unbounded rank-
width is given in [19], which is a slight modification of the class of permutation graphs introduced in
[15]. In [17] Kloks claims a proof of the fact that (diamond, even hole)-free graphs can be decomposed
by clique cutsets into graphs of bounded clique-width. In this paper we exhibit a class of (diamond,
even hole)-free graphs with no clique cutset that has unbounded rank-width (and hence clique-width), so
disproving Kloks' claim.

Another interesting subclass of even-hole-free graphs is the class of (cap, even hole)-free graphs, where
a *cap* is a graph made of a hole and a vertex that has exactly two neighbors on this hole, which are
furthermore adjacent. Cap-free graphs in general are decomposed by amalgams in [5]. Recently, Conforti,
Gerards and Pashkovich [7], show how to obtain a polynomial-time algorithm for solving the maximum
weighted stable set problem on any class of graphs that is decomposable by amalgams into basic graphs
for which one can solve the maximum weighted stable set problem in polynomial time. This leads to a
polynomial-time algorithm for solving the maximum weight stable set problem for (cap, even-hole)-free
graphs. Subsequently, Cameron, da Silva, Huang and Vušković [3] give an explicit construction of (cap,
even hole)-free graphs, which is then used to show that (triangle, even hole)-free graphs have tree-width
at most 5, and that (cap, even hole)-free graphs with no clique cutset have clique-width at most 48 (and
hence bounded rank-width). This implies that a number of problems can be solved efficiently on this
class, and in particular the class can be colored in polynomial time.

## 2 Preliminaries

Graphs are finite, simple and undirected unless stated otherwise. The vertex set of a graph $G$ is denoted
by $V(G)$ and the edge set by $E(G)$. A graph $H$ is a *subgraph* of a graph $G$, denoted by $H \subseteq G$, if
$V(H) \subseteq V(G)$ and $E(H) \subseteq E(G)$. For a graph $G$ and a subset $X \subseteq V(G)$, we let $G[X]$ denote the
subgraph of $G$ induced by $X$, i.e. $G[X]$ has vertex set $X$, and $E(G[X])$ consists of the edges of $G$ that
have both ends in $X$. A graph $H \subseteq G$ is an *induced subgraph* of $G$, if $H = G[X]$ for some $X \subseteq V(G)$.
Moreover, we let $G \setminus X := \{G[V(G) \setminus X]\}$. The set $X$ is a *clique*, if $G[X]$ contains all possible edges. If
$G$ is connected, $X$ is called a *clique cutset* if $X$ is a clique and $G \setminus X$ is disconnected.

A *tree* is a connected, acyclic graph. A *leaf* of a tree is a node incident to exactly one edge. For a tree $T$, we let $L(T)$ denote the set of all leaves of $T$. A tree node that is not a leaf is called *internal*. A tree is a *cubic*, if it has at least two vertices and every internal node has degree 3. A *path* is a tree where every node has degree at most 2. The (at most 2) leaves of a path $P$ are called *end-vertices* of $P$. A *u, v-path* is a path with end-vertices $u$ and $v$. A graph $P$ is a *subpath* of a graph $G$, if $P$ is a path and $P \subseteq G$.

For a set $X$, let $2^X$ denote the set of all subsets of $X$. For sets $R$ and $C$, an $(R, C)$-matrix is a matrix
where the rows are indexed by elements in $R$ and columns indexed by elements in $C$. For an $(R, C)$-matrix $M$, if $X \subseteq R$ and $Y \subseteq C$, we let $M[X, Y]$ be the submatrix of $M$ where the rows and the columns
are indexed by $X$ and $Y$, respectively. For a graph $G = (V, E)$, let $A_G$ denote the adjacency matrix of $G$
4 Isolde Adler, Ngoc Khang Le, Haiko Müller, Marko Radovanović, Nicolas Trotignon, Kristina Vušković

over the binary field (i.e. $A_G$ is the $(V, V)$-matrix, where an entry is 1, if and only if, the column-vertex is adjacent to the row-vertex, and 0 otherwise). The cutrank function of $G$ is the function $\text{cutrk}_G: 2^V \to \mathbb{N}$, given by

$$ \text{cutrk}_G(X) = \text{rank}(A_G[X, V \setminus X]), $$

where the rank is taken over the binary field.

A rank decomposition of a graph $G$ is a pair $(T, \lambda)$, where $T$ is a cubic tree and $\lambda: V(G) \to L(T)$ is a bijection. If $|V(G)| \le 1$, then $G$ has no rank decomposition. For every edge $e \in E(T)$, the connected components of $T - e$ induce a partition $(A_e, B_e)$ of $L(T)$. The width of an edge $e$ is defined as $\text{cutrk}_G(\lambda^{-1}(A_e))$. The width of $(T, \lambda)$, denoted by $\text{width}(T, \lambda)$, is the maximum width over all edges of $T$. The rank-width of $G$, denoted by $\text{rw}(G)$, is the minimum integer $k$, such that there is a rank decomposition of $G$ of width $k$. (If $|V(G)| \le 1$, we let $\text{rw}(G) = 0$.)

**Remark 1.** Let $G$ be a graph and $H \subseteq G$ be an induced subgraph of $G$. Then $\text{rw}(H) \le \text{rw}(G)$.

We say that a class $\mathcal{C}$ of graphs has bounded rank-width, if there exists a constant $k \in \mathbb{N}$, such that every $G \in \mathcal{C}$ satisfies $\text{rw}(G) \le k$. If such a constant does not exist, $\mathcal{C}$ has unbounded rank-width.

We conclude the section with two lemmas that we will use in Section 4.

**Lemma 2.** Let $k \in \mathbb{N}$. Let $G$ be a graph, $P \subseteq G$ an induced path, $(T, \lambda)$ a rank decomposition of $G$ of width at most $k$, and $e \in E(T)$. Let $(X, Y)$ be the bipartition of $V(P)$ induced by the two components of $T - e$. Then the induced graph $P[X]$ has at most $k + 1$ connected components.

**Proof:** Towards a contradiction, assume that $P[X]$ has at least $k + 2$ components. Order the components (which are subpaths of $P$) according to their appearance along $P$. From each component, except for the first one, pick the first vertex. In this way we obtain a set $X' \subseteq X$ of at least $k + 1$ vertices, each with one or two neighbours in $Y$ (two neighbours only if the component is a singleton vertex). Let $Y'$ be the set of vertices in $Y$ that are adjacent to a vertex in $X'$. Then each row of $A_P[X', Y']$ has one or two non-zero entries, and no two rows are equal. Ordering the vertices of $X'$ and $Y'$ according to their appearance on $P$ yields a matrix with blocks corresponding to subpaths of $P$, such that in each row the (at most two) non-zero entries appear consecutively. By the choice of $X'$, within each block there is at most one row with precisely one non-zero entry, while all other rows in that block have two non-zero entries. With this it is easy to see that the rows of each block are linearly independent, and it follows that $A_P[X', Y']$ has rank at least $k + 1$. Since $P$ is induced, we have $A_P[X', Y'] = A_G[X', Y']$, and hence the width of $e$ is at least $k + 1$, a contradiction to the width of $(T, \lambda)$ being at most $k$. $\square$

We use the following definition, several variants of which exist in the literature.

**Definition 3.** Let $T$ be a tree. We call an edge $e \in E(T)$ balanced, if the partition $(A_e, B_e)$ of $L(T)$ satisfies $\frac{1}{3}|L(T)| \le |A_e|$ and $\frac{1}{3}|L(T)| \le |B_e|$.

The following lemma is well-known and we omit the proof.

**Lemma 4.** Every cubic tree has a balanced edge.

**Lemma 5.** For $m, k \in \mathbb{N}$ with $k > 1$, let $G$ be a graph, $P \subseteq G$ be an induced path and $|V(G)| - |V(P)| = m$. Let $(T, \lambda)$ be a rank decomposition of $G$ of width at most $k$, and let $e \in E(T)$ be a balanced edge. Let $(X, Y)$ be the bipartition of $V(P)$ induced by $e$. Then each of the two induced subgraphs $P[X]$ and $P[Y]$ contains a connected component with at least $\lfloor \frac{|V(G)| - 3m}{3(k+1)} \rfloor$ vertices.
**Proof:** Since $e$ is balanced, we have $|X| \ge \frac{1}{3}|V(G)| - m$ and $|Y| \ge \frac{1}{3}|V(G)| - m$. By Lemma 2, both $P[X]$ and $P[Y]$ have at most $k+1$ connected components, which proves the lemma. □

## 3 Construction

In this section we construct a class of (diamond, even-hole)-free graphs $(G_d)_{d \ge 1}$.

For $1 \le k \le d$, let

$$S_k = \{(a_1, a_2, \dots, a_{k-1}, a_k) : a_1, a_2, \dots, a_{k-1} \in \{1, 3\}, a_k \in \{1, 2, 3, 4\}\},$$

and $S^d = \bigcup_{k=1}^d S_k$. If $u \in S_k$, then we denote $l(u) = k$, and say that the length of $u$ is $k$.

In $S^d$, let $\llcorner$ denote the lexicographical order defined as follows. For $a = (a_1, a_2, \dots, a_k) \in S^d$ and $b = (b_1, b_2, \dots, b_t) \in S^d$, $a \llcorner b$ if and only if $k \le l$ and $a_i = b_i$ for $1 \le i \le k$, or $t = \min\{i : a_i \ne b_i\}$ is well-defined and $a_t < b_t$. This order is a total order on the finite set $S^d$, so we introduce the following notation:

* for $a \in S^d \setminus \{(4)\}$, $s(a)$ is the smallest element (w.r.t. $\llcorner$) of $S^d$ that is greater than $a$;

* for $a \in S^d \setminus \{(1)\}$, $p(a)$ is the greatest element (w.r.t. $\llcorner$) of $S^d$ that is smaller than $a$.

Let $P'_d$ denote the path on vertex set $S^d$ connecting the vertices according to the lexicographic order, and let $P_d$ be the path obtained from $P'_d$ by subdividing every edge $uv \in E(P'_d)$ twice if $l(u) = l(v)$, and once, otherwise. Finally, let $W_d = \{v_1, v_2, \dots, v_d\}$ be a set of (new) vertices, such that $v_k$, for $1 \le k \le d$, is adjacent to all vertices of $S_k$ and all other vertices of $W_d$. Then, $G_d$ is the graph induced by the set $W_d \cup V(P_d)$. For vertices of $W_d$ we say that they are centers of $G_d$. Figure 1 shows $G_4$.

**Remark 6.** For $d \ge 1$, the following hold:

$$(i) \quad |S^d| = \sum_{k=1}^{d} 4 \cdot 2^{k-1} = 4(2^d - 1) \ge 2^{d+1}, \text{ and}$$

$$(ii) \quad 3|S^d| + d \ge |V(G_d)| \ge 2|S^d| \ge 2^{d+2}.$$

**Proof:** Part (i) follows from the fact that for $k=1$, the set $S_k$ contains 4 vertices, and that the number of vertices in the set doubles whenever $k$ increases by one. Part (ii) follows from Part (i) and the number of subdivision vertices added in the construction of $P_d$. □

**Remark 7.** For $d \ge 1$, every $u \in S^d$, with $u \ne (4)$, satisfies $|l(u) - l(s(u))| \le 1$.

Let us introduce some additional notation for the elements of $S^d$. For $a, b \in S^d$, interval $[a, b]$ is the set $\{c \in S^d : a \llcorner c \llcorner b\}$. We say that an interval $[a, b]$ is proper if for all $c \in [a, b] \setminus \{a, b\}$, $l(c) \notin \{l(a), l(b)\}$. Note that $[a, b] = \bigcup_{a \llcorner c \llcorner b} [c, s(c)]$. For an interval $[c, s(c)]$, $a \llcorner c \llcorner b$, we say that it is a step of $[a, b]$, and if additionally $l(c) = l(s(c))$, we say that this step is flat.

**Lemma 8.** Let $a, b \in S^d$. If $[a, b]$ is a proper interval such that $l(a) = l(b)$, then it contains an odd number of flat steps.

**Proof:** Our proof is by induction on the number of elements of $[a, b]$. If $[a, b]$ has only 2 elements, that is if $b = s(a)$, then the lemma trivially holds. Let $a = (a_1, a_2, \dots, a_k)$.
<figure><img src="image_3.png" /><figcaption>Figure 1: The graph $G_4$</figcaption></figure>
Case 1. $a_k = 2$.

In this case $b = (a_1, a_2, \dots, a_{k-1}, 3)$ and $[a, b] = \{a, b\}$, so the conclusion trivially follows.

Case 2. $a_k \in \{1, 3\}$.

In this case $b = (a_1, a_2, \dots, a_{k-1}, a_k + 1)$. If $k = d$, then $[a, b] = \{a, b\}$, and the conclusion follows. So, let $k < d$. Then

$$[a, b] = [a, a^{(1)}] \cup [a^{(1)}, a^{(2)}] \cup [a^{(2)}, a^{(3)}] \cup [a^{(3)}, a^{(4)}] \cup [a^{(4)}, b],$$

where $a^{(i)} = (a_1, a_2, \dots, a_k, i)$, for $1 \le i \le 4$. Since $s(a) = a^{(1)}$ and $s(a^{(4)}) = b$, the number of flat steps of $[a, b]$ is the sum of the numbers of flat steps of $[a^{(i)}, a^{(i+1)}]$, for $1 \le i \le 3$. Note that $a^{(i)}$ and $a^{(i+1)}$, for $1 \le i \le 3$, are consecutive $(k+1)$-tuples of $S^d$, i.e. the interval $[a^{(i)}, a^{(i+1)}]$ is proper. Therefore, by induction, each of the intervals $[a^{(i)}, a^{(i+1)}]$, for $1 \le i \le 3$, has an odd number of flat steps, and hence so does the interval $[a, b]$.

Case 3. $a_k = 4$.

In this case $a_{k-1} \in \{1, 3\}$, so

$$a = (a_1, \dots, a_{i-1}, 1, \underbrace{3, \dots, 3, 4}_{k-i-1}),$$

where $1 \le i \le k-1$ ($a$ has at least one coordinate equal to 1, since there does not exist a $k$-tuple in $S^d$ which is larger than the $k$-tuple $(3, \dots, 3, 4)$).

If $i = k-1$, then $s(a) = (a_1, \dots, a_{i-1}, 2)$, $s(s(a)) = (a_1, \dots, a_{i-1}, 3)$ and $s(s(s(a))) = (a_1, \dots, a_{i-1}, 3, 1) = b$, and hence the interval $[a, b]$ has one flat step.

So, let $i < k-1$. Then

$$s(a) = (a_1, \dots, a_{i-1}, 1, \underbrace{3, \dots, 3, 4}_{k-i-2}),$$

$$p(b) = (a_1, \dots, a_{i-1}, 3, \underbrace{1, \dots, 1}_{k-i-1}),$$

$$b = (a_1, \dots, a_{i-1}, 3, \underbrace{1, \dots, 1}_{k-i}).$$

So, the number of flat steps of the interval $[a, b]$ is the same as the number of flat steps of the interval $[s(a), p(b)]$. Since $s(a)$ and $p(b)$ are consecutive $(k-1)$-tuples of $S^d$, the interval $[s(a), p(b)]$ is proper, and the conclusion follows by induction.

□

**Lemma 9.** Let $a, b \in S^d$. If $[a, b]$ is a proper interval such that $l(a) \neq l(b)$, then it does not contain a flat step.
8 Isolde Adler, Ngoc Khang Le, Haiko Müller, Marko Radovanović, Nicolas Trotignon, Kristina Vušković

**Proof:** Note that the set $S^d$ is symmetric, so we may assume that $l(a) > l(b)$. Let $a = (a_1, \dots, a_{k-1}, a_k)$. If $a_k < 4$, then $a \prec (a_1, \dots, a_{k-1}, a_k+1)$, and hence $[a, b]$ is not proper, since there does not exist $c \in S^d$ such that $(a_1, \dots, a_{k-1}, a_k) \prec c \prec (a_1, \dots, a_{k-1}, a_k+1)$ and $l(c) < k$. So, $a_k = 4$. If $a = (\underbrace{3, \dots, 3}_{k-1}, 4)$, then $b = (\underbrace{3, \dots, 3}_{l-1}, 4)$, where $l = l(b)$, and the conclusion follows. So, let

$$a = (a_1, \dots, a_{i-1}, 1, \underbrace{3, \dots, 3}_{k-i-1}, 4),$$

where $1 \le i \le k-1$, and

$$a' = (a_1, \dots, a_{i-1}, 3, \underbrace{1, \dots, 1}_{k-i}).$$

The elements of the interval $[a, a']$ are the following (given in increasing order):

$$(a_1, \dots, a_{i-1}, 1, \underbrace{3, \dots, 3}_{k-i-1}, 4), (a_1, \dots, a_{i-1}, 1, \underbrace{3, \dots, 3}_{k-i-2}, 4), \dots, (a_1, \dots, a_{i-1}, 2),$$

$$(a_1, \dots, a_{i-1}, 3), (a_1, \dots, a_{i-1}, 3, 1), \dots, (a_1, \dots, a_{i-1}, 3, \underbrace{1, \dots, 1}_{k-i}).$$

Since $[a, b]$ is proper, it holds $b \prec a'$. Additionally, since $[a, b]$ does not contain an element of length equal to $l(b)$, $b$ is an element of $[a, a']$ from the first row of the given list. Now it is clear that $[a, b]$ contains zero flat steps. □

For an interval $[a, b]$ in $S^d$, let $P_{[a,b]}$ be the path of $G_d$ induced by $\bigcup_{a \le c < b} V(P_c)$. Since path $P_c$ is of odd length if and only if $l(c) = l(s(c))$, path $P_{[a,b]}$ is of odd length if and only if $[a, b]$ contains an odd number of flat steps.

**Theorem 10.** The graph $G_d$ is (diamond, even hole)-free for all $d \ge 1$ and $G_d$ has no clique cutset for all $d \ge 2$.

**Proof:** First, suppose that $G_d$ contains a diamond $D$ for some $d \ge 1$. Since $P_d$ is a path, $V(D) \not\subseteq V(P_d)$, and since $D$ is not a clique $V(D) \not\subseteq W_d$. The neighborhood in $P_d$ of every vertex of $W_d$ is a stable set, so $|V(D) \cap V(P_d)| \le 2$. On the other hand, every vertex of $P_d$ is adjacent to at most one vertex of $W_d$, so $|V(D) \cap V(W_d)| \le 2$. Hence, $|V(D) \cap V(P_d)| = |V(D) \cap W_d| = 2$. But then $D$ has at most 4 edges, a contradiction.

Now, suppose that $G_d$ contains an even hole $H$ for some $d \ge 1$. Since $P_d$ is a path, $V(H) \cap W_d \ne \emptyset$, and since $W_d$ is a clique $|V(H) \cap V(W_d)| \le 2$. First suppose that $V(H) \cap V(W_d) = \{v_k\}$, for some $1 \le k \le d$. Since $v_k$ has exactly two neighbors in $H$, $V(H) = \{v_k\} \cup V(P_{[a,b]})$, where $a, b \in S^d$ are such that $l(a) = l(b) = k$ and the interval $[a, b]$ is proper. Then, by Lemma 8, interval $[a, b]$ contains an odd number of flat steps, and hence path $P_{[a,b]}$ and hole $H$ are of odd length, a contradiction. So, $V(H) \cap V(W_d) = \{v_k, v_l\}$, for some $1 \le k < l \le d$. Then $V(H) = \{v_k, v_l\} \cup V(P_{[a,b]})$, where $a, b \in S^d$ are such that $\{l(a), l(b)\} = \{k, l\}$ and the interval $[a, b]$ is proper. Then, by Lemma 9, interval $[a, b]$ does not contain a flat step, and hence path $P_{[a,b]}$ is of even length, i.e. the hole $H$ is of odd length (since the length of $H$ is by 3 larger than the length of $P_{[a,b]}$), a contradiction.
Let $d \ge 2$ and suppose that $G_d$ has a clique cutset $K$. We distinguish between three cases. First, if $K \subseteq W_d$ then $K$ does not separate since $P_d$ is a path and every vertex in $W_d \setminus K$ has a neighbor in $P_d$. Second, if $K \subseteq V(P_d)$ then $P_d - K$ has two components. In $G_d - K$ these are connected via $W_d$ since $d \ge 2$. Hence we are in the third case and may assume $K \cap W_d \ne \emptyset$ and $K \cap V(P_d) \ne \emptyset$. By construction, no vertex of $P_d$ is contained in a triangle, and hence $|K| \le 2$. Consequently $K = \{u, v_i\}$ for $u \in V(P_d)$ and $1 \le i \le d$. The vertex $u$ is neither (1) nor (4) since both are adjacent to $v_1 \in W_d$ and neither $\{(1), v_1\}$ nor $\{(4), v_1\}$ are cutsets of $G_d$. It follows that (1) and (4) are separated by $K$. Since $v_1$ is adjacent to both (1) and (4) we have $i = 1$, and hence $u$ is (2) or (3). But then $v_2$ has a neighbor in both components of $P_d - u$, a contradiction. $\square$

# 4 Lower bound

In this section we prove that the rank-width of the class $(G_d)_{d \ge 1}$ constructed in the previous section is unbounded.

**Lemma 11.** If $d \ge 1$ and $P$ is a subpath of $P_d$ such that $|V(P) \cap S_i| \ge 3$ for some $i$ ($1 \le i \le d$), then $V(P) \cap S_j \ne \emptyset$ for every $j$ satisfying $i \le j \le d$.

**Proof:** Since $|V(P) \cap S_i| \ge 3$, there exist two vertices of the form $(a_1, \dots, a_{i-1}, 1)$ and $(a_1, \dots, a_{i-1}, 2)$, or two vertices of the form $(a_1, \dots, a_{i-1}, 3)$ and $(a_1, \dots, a_{i-1}, 4)$ in $P$, where $a_k \in \{1, 3\}$ for $1 \le k < i$. But then, by the definition of the order $\prec$ for $S^d$, $P$ must contain some vertex of length $j$ for every $j$ satisfying $i \le j \le d$. $\square$

**Lemma 12.** If $P$ is a subpath of $P_d$ such that $|V(P)| \ge c|V(G_d)|$, where $0 < c < 1$ and $d > 2\lfloor\log_2 \frac{1}{c}\rfloor + 4$, then $V(P) \cap S_j \ne \emptyset$ for every $j$ satisfying $\lfloor\log_2 \frac{1}{c}\rfloor + 3 \le j \le d$.

**Proof:** If $V(P) \cap S_j \ne \emptyset$ for every $j \in \{1, \dots, d\}$, then the conclusion trivially holds. Hence, we may assume that $V(P) \cap S_j = \emptyset$ for some $j \in \{1, \dots, d\}$.

**Claim 1.** $|V(P)| > 6d$.

*Proof of Claim 1:* Suppose that $|V(P)| \le 6d$. Since $|V(P)| \ge c|V(G_d)| \ge c \cdot 2^{d+2}$ (the first inequality is by the assumption, and the second by Remark 6), it follows that $6d \ge c \cdot 2^{d+2}$, which is equivalent to $\log_2 \frac{1}{c} \ge d - \log_2 d + 2 - \log_2 6$. Since $d - \log_2 d \ge \frac{d}{2}$, for all $d \ge 4$ (which is the case by assumption), and $2 - \log_2 6 > -1$, we have that $\log_2 \frac{1}{c} > \frac{d}{2} - 1$, which is equivalent to $d < 2 \log_2 \frac{1}{c} + 2$, a contradiction. This completes the proof of Claim 1.

**Claim 2.** For some $t \in \{1, \dots, d\}$, $|V(P) \cap S_t| \ge 3$.

*Proof of Claim 2:* Suppose that for all $t \in \{1, \dots, d\}$, $|V(P) \cap S_t| \le 2$. Let $a'$ and $b'$ be the endnodes of $P$, and let $a$ (resp. $b$) be the first (resp. last) vertex of $S^d$ encountered when traversing $P$ from $a'$ to $b'$. Since for some $j$, $V(P) \cap S_j = \emptyset$, the interval $[a, b]$ contains at most $d - 2 + 1 + d - 2 = 2d - 3$ steps (note that this bound can be achieved when $[a, b]$ contains vertices (2) and (3), the $d-2$ elements of $S^d$ that precede (2), and the $d-2$ elements of $S^d$ that succeed (3)). For each step $[u, s(u)]$, the $u, s(u)$-subpath of $P$ is of length at most three. The $a, a'$-subpath of $P$ and the $b, b'$-subpath of $P$ are each of length at most two. It follows that
10 Isolde Adler, Ngoc Khang Le, Haiko Müller, Marko Radovanović, Nicolas Trotignon, Kristina Vušković

the length of $P$ is at most $3(2d - 3) + 2 \cdot 2 = 6d - 5$, and hence $|V(P)| \le 6d$, contradicting Claim 1. This completes the proof of Claim 2.

By Claim 2 and Lemma 11, for some $i < d$, $V(P) \cap S_i = \emptyset$ and $V(P) \cap S_j \neq \emptyset$ for $j \in \{i+1, \dots, d\}$. By Remark 7, $V(P) \cap S_j = \emptyset$ for $j \in \{1, \dots, i\}$. Therefore, there exist two vertices $u, v \in S_i$, $u \prec v$, such that $P$ is contained in the subpath $P'$ of $P_d$ from $u$ to $v$ and $V(P') \cap S_i = \{u, v\}$. Let $u = (a_1, \dots, a_i)$.

Claim 3. $a_i \in \{1, 3\}$.

*Proof of Claim 3:* We consider the following cases:

* If $a_i = 2$ then $v = s(u)$. Hence, $|V(P')| = 4$.

* If $a_i = 4$, then $u = (a_1, \dots, a_{i'-1}, 1, 3, \dots, 3, 4)$, where $1 \le i' \le i - 1$ ($u$ has at least one coordinate equal to 1, otherwise there does not exist a tuple in $S_i$ which is larger than $u$). Since $v$ is the next element in $S_i$ which is larger than $u$, $v = (a_1, \dots, a_{i'-1}, 3, 1, \dots, 1)$. By the discussion in the proof of Lemma 9, the number of elements of $S^d$ in the interval $[u, v]$ is $2(i - i' + 1)$ and we have that $2(i - i' + 1) \le 2i \le 2d$. Since there are at most two vertices of $P'$ between any two consecutive elements in $S_d$, $|V(P')| \le 3 \cdot 2d = 6d$.

Both cases contradict Claim 1. This completes the proof of Claim 3.

Since there are at most two vertices of $P'$ between any two consecutive elements in $S_d$ and by Claim 3, $|V(P')| \le 3|\{u, v\}| = 3(\sum_{j=0}^{d-i-1} 4 \cdot 2^j + 2) < 12(\sum_{j=0}^{d-i-1} 2^j + 1) = 12 \cdot 2^{d-i} < 2^{d-i+4}$. So by Remark 6, we have that

$$2^{d-i+4} > |V(P')| \ge |V(P)| \ge c|V(G_d)| \ge c \cdot 2^{d+2}.$$

Hence $2^{2-i} > c$, or equivalently $i < 2 + \log_2 \frac{1}{c}$, proving the lemma. $\square$

**Lemma 13.** For any $d \ge 22$ we have $\mathrm{rw}(G_d) > d/3$.

**Proof:** Suppose that $\mathrm{rw}(G_d) \le k = d/3$. Let $(T, \lambda)$ be a rank decomposition of $G_d$ of width at most $k$. Let $e \in E(T)$ be a balanced edge (it exists by Lemma 4), and let $M$ be the adjacency matrix of $G_d$. Let $(X, Y)$ be the bipartition of $V(G_d)$ induced by $e$. Applying Lemma 5 for $G_d$ and the path $P_d$ ($|V(G_d)| - |V(P_d)| = d$), there exist two subpaths $P_X, P_Y$ of $P_d$ in $G_d[X]$ and $G_d[Y]$, respectively, such that $|V(P_X)|, |V(P_Y)| \ge \lfloor \frac{|V(G_d)|-3d}{3(k+1)} \rfloor \ge \frac{|V(G_d)|}{4(k+1)}$ (note that the second inequality holds by Remark 6 and the fact that $d \ge 22$). Applying Lemma 12 (using the fact that $d \ge 22$) with $c = \frac{1}{4(k+1)}$ and letting $c' = \lfloor \log_2(\frac{1}{c}) \rfloor + 3 = \lfloor \log_2(k+1) \rfloor + 5$, we have $V(P_X) \cap S_j \neq \emptyset$ and $V(P_Y) \cap S_j \neq \emptyset$ for every $j$ satisfying $c' \le j \le d$. W.l.o.g. let $X$ be the set containing at least half of the center vertices in $\{v_{c'}, \dots, v_d\}$. Let $I = \{i \in \{c', \dots, d\} \mid v_i \in X\}$ (the set of indices of center vertices in $X$), and fix a vertex $a_i \in Y \cap S_i$ for every $i \in I$, which exists because $V(P_Y) \cap S_i \neq \emptyset$. We have $|I| \ge \frac{d-c'+1}{2}$. Let $S_X = \{v_i \mid i \in I\}$ and $S_Y = \{a_i \mid i \in I\}$. Note that $S_X \subseteq X$ and $S_Y \subseteq Y$. Because each vertex $v_i$ in $S_X$ has exactly one neighbor in $S_Y$ (namely $a_i$), we have that $M[S_X, S_Y] = \mathbf{1}_{|I|}$ (identity matrix). Therefore, $\mathrm{rank}(M[S_X, S_Y]) = |I|$. We have

$$k \ge \mathrm{width}(T, \lambda) \ge \mathrm{cutrk}_G(X) = \mathrm{rank}(M[X, Y]) \ge \mathrm{rank}(M[S_X, S_Y]) = |I| \ge \frac{d-c'+1}{2},$$
which is equivalent to $d \le 2k + c' - 1 = 2k + \lfloor\log_2(k+1)\rfloor + 4 = 2d/3 + \lfloor\log_2(d/3+1)\rfloor + 4$, a contradiction since $d \ge 22$. □

From Lemma 13 and Remark 6 we obtain that the rankwidth of $G_d$ grows at least logarithmically with $|V(G_d)|$, since if $d \ge 22$ then $\text{rw}(G_d) > d/3 \ge (\log_2|V(G_d)| - 4)/3$. From Theorem 10 and Lemma 13 we have the following theorem.

**Theorem 14.** The family of (diamond, even hole)-free graphs $G_d$, $d \ge 2$, without clique cutsets has unbounded rank-width.

For completeness, observe that $\text{rw}(G_d) \le d+1$ for all $d \in \mathbb{N}$. To see this, take a cubic tree $T$ with $|V(G_d)|$ leaves, where the internal nodes form a path. Via the bijection $\lambda: V(G_d) \to L(T)$, pick the linear ordering on $W_d \cup V(P_d)$, which starts with $v_1, v_2, v_3, \dots, v_d$, followed by the vertices of $P_d$ in their canonical order (see Figure 2).

<figure><img src="image_4.png" /><figcaption>**Figure 2:** A rank decomposition of $G_d$ of width at most $d+1$.</figcaption></figure>

Let $e$ be an edge of $T$ and let $(X, Y)$ be the bipartition of $V(G_d)$ induced by $e$. Since $\text{rank}(M[X, Y]) \le \min(|X|, |Y|)$ we may assume $|X|, |Y| > d$ and $\{v_1, v_2, \dots, v_d\} \subseteq X$. Now the vertices in $Y$ have at most $d+1$ different neighbours in $X$. Hence the width of $e$ is at most $d+1$, proving that $\text{rw}(G_d) \le d+1$.

## References

[1] P. Aboulker, P. Charbit, N. Trotignon, and K. Vušković, Vertex elimination orderings for hereditary graph classes, Discrete Mathematics **338** (2015), no. 5, 825–834.

[2] L. Addario-Berry, M. Chudnovsky, F. Havet, B. A. Reed, and P. D. Seymour, Bisimplicial vertices in even-hole-free graphs, Journal of Combinatorial Theory Series B **98** (2008), 1119–1164.

[3] K. Cameron, M. V. G. da Silva, S. Huang, and K. Vušković, Structure and algorithms for (cap, even hole)-free graphs, submitted, 2016.

[4] H.-C. Chang and H.-I. Lu, A faster algorithm for recognising even-hole-free graphs, Journal of Combinatorial Theory Series B **113** (2015), 141–161.

[5] M. Conforti, G. Cornuéjols, A. Kapoor, and K. Vušković, Even and odd holes in cap-free graphs, Journal of Graph Theory **30** (1999).

[6] __________, Even-hole-free graphs, part II: Recognition algorithm, Journal of Graph Theory **40** (2002), 238–266.

[7] M. Conforti, B. Gerards, and K. Pashkovich, Stable sets and graphs with no even hole, Mathematical Programming Series B **153** (2015), 13–39.
12 Isolde Adler, Ngoc Khang Le, Haiko Müller, Marko Radovanović, Nicolas Trotignon, Kristina Vušković

[8] B. Courcelle, *Graph rewriting: An algebraic and logic approach*, Handbook of Theoretical Computer Science vol. B (Jan van Leeuwen, ed.), Elsevier/MIT Press, 1990, pp. 194–242.

[9] B. Courcelle, J. Engelfriet, and G. Rozenberg, *Handle-rewriting hypergraph grammars*, Journal of Computer and System Sciences **46** (1993), 218–270.

[10] B. Courcelle, J. A. Makowsky, and U. Rotics, *Linear time solvable optimization problems on graphs of bounded clique width*, Theory of Computing Systems **33** (2000), 125–150.

[11] A. A. da Silva, A. Silva, and C. Linhares-Sales, *A bound on the treewidth of planar even-hole-free graphs*, Discrete Applied Mathematics **158** (2010), 1229–1239.

[12] M. V. G. da Silva and K. Vušković, *Triangulated neighborhoods in even-hole-free graphs*, Discrete Mathematics **307** (2007), 1065–1073.

[13] __________, *Decomposition of even-hole-free graphs with star cutsets and 2-joins*, Journal of Combinatorial Theory Series B **103** (2013), 144–183.

[14] M. Farber, *On diameters and radii of bridged graphs*, Discrete Mathematics (1989).

[15] M. C. Golumbic and U. Rotics, *On the clique-width of some perfect graph classes*, International Journal of Foundations of Computer Science **11** (2000), 423–443.

[16] S. i. Oum and P. D. Seymour, *Approximating clique-width and branch-width*, Journal of Combinatorial Theory Series B **96** (2006).

[17] T. Kloks, *Graphs without even holes or diamonds*, arXiv:1104.3920v1[math.CO], 2011.

[18] T. Kloks, H. Müller, and K. Vušković, *Even-hole-free graphs that do not contain diamonds: a structure theorem and its consequences*, Journal of Combinatorial Theory Series B **99** (2009), 733–800.

[19] N. K. Le, in preparation.

[20] S. E. Markossian, G. S. Gasparian, and B. A. Reed, *β-perfect graphs*, Journal of Combinatorial Theory Series B **67** (1996).

[21] N. Robertson and P. D. Seymour, *Graph minors II: Algorithmic aspects of tree-width*, Journal of Algorithms **7** (1986), 309–322.

[22] K. Vušković, *Even-hole-free graphs: A survey*, Applicable Analysis and Discrete Mathematics **4** (2010), 219–240.

[23] __________, *The world of hereditary graph classes viewed through Truemper configurations*, London Mathematical Society Lecture Note Series, vol. 409, Cambridge University Press, 2013, pp. 265–325.