Struggle with equivalence relation definition in graph theory paper regarding clique-width

Question

I'm trying to get more involved in graph theory and understanding harder concepts. I stumbled upon a paper that proves the clique-width of split graphs to be unbounded. They define a split graph as splt(G) if it is a clique $G$ with leaves for every edge in the clique (6.1). I'm having trouble understanding their definition 5.1 and 5.2 and consequently the proof in 6.2. How do they define the equivalence relation $R_{red}$? I tried to use their example proof in proposition 5.5 to get a better understanding for their equivalence relation, but this confused me even more.

I thought they color a fixed set of vertices $V_{red}$ and the remaining set $V_{blue}$. But then how could there, in general, be different equivalence classes, since every subset of vertices in $V_{red}$ is in the same equivalence class as $V_{red}$. This part confuses me.

The previous definitions and results on (q,t)-graphs are unnecessary. The only important information in the paper is: 5.1, 5.2, 5.5 and the definition of distinguishes given in 2.12.

Edit: How I understood the different equivalence classes of $R_{red}$, I would assume that given a fixed set of $V_{red}$ and $V_{blue}$ we determine the different classes depending on their blue neighbours. But even then, I'm still struggling to grasp how they determine the numbers for 2colw(G)$\geq\frac{n}{72}$ and e.g. $S_1 <\frac{10n}{18}$. Any help is much appreciated, thanks.

Edit2: Big Thanks to Misha Lavrov for taking time out of his day to explain this in great detail to me! :)

The paper: On the clique-width of graphs with few P_4s

Answer 1

The equivalence classes of $R_{\text{red}}$ partition $V_{\text{red}}$ into subsets that are not distinguishable by any blue vertex. Consider the following example:

Here, $V_{\text{red}} = \{1,2,3\}$. The equivalence classes of $R_{\text{red}}$ are $\{1,2\}$ and $\{3\}$. Vertices $1$ and $2$ are not distinguished by any blue vertices: $4$ is adjacent to neither, and $5$ is adjacent to both. On the other hand, vertex $4$ distinguishes vertex $3$ from both $1$ and $2$: it is only adjacent to $3$.

Another way to write the definition of $R_{\text{red}}$ is that two red vertices are equivalent if they have the same set of blue neighbors.

Proposition 5.5 specifically constructs an example where the relation does not do anything exciting. If $V_{\text{red}}$ and $V_{\text{blue}}$ have no edges between them, then no blue vertex can distinguish any two red vertices! Therefore for any pair $(u,v)$ with $u,v \in V_{\text{red}}$, it is true that "$u$ and $v$ are not distinguishable by any blue vertex", and so there is only one equivalence class. To use our second definition, if no red vertices ever have blue neighbors, then any two red vertices have the same set of blue neighbors: the empty set!

As for the proof of Lemma 6.2, let's take a look at one of the split graphs it considers:

We have a central clique (here, it has vertices $\{1,2,3,4\}$) and a bunch of outer vertices (here, $\{12,13,14,23,24,34\}$) each of which has two neighbors in the central clique.

It is in case 2 of the proof that we really interact with the equivalence relation at all. Here, we have a large set $S_3$ of central vertices with the following property: they each have a blue outer neighbor and a red outer neighbor. Now, we argue that:

• If $S_{3,\text{red}} = S_3 \cap V_{\text{red}}$ is large, then the vertices of $S_{3,\text{red}}$ are in many equivalence classes. Every vertex $u \in S_{3,\text{red}}$ is adjacent to a blue outer vertex $uv$. But then, $uv$ distinguishes $u$ from every other vertex in $S_3$ except possibly $v$ (if $v \in S_{3,\text{red}}$ as well). Therefore every equivalence class of $R_{\text{red}}$ has at most two elements in $S_{3,\text{red}}$.
• If $S_{3,\text{blue}} = S_3 \cap V_{\text{blue}}$ is large, then the red outer neighbors of $S_{3,\text{blue}}$ are all in different equivalence classes. As long as $|S_{3,\text{blue}}| \ge 3$, if there is a red vertex $uv$ with a neighbor $u \in S_{3,\text{blue}}$, then $uv$ also has a non-neighbor $w \in S_{3,\text{blue}}$ (just pick $w$ to be any element of $S_{3,\text{blue}}$ other than $u$ and $v$), and then $u$ and $w$ distinguish $uv$.

When $S_{3,\text{red}}$ is large, since each equivalence class contains at most $2$ elements of $S_{3,\text{red}}$, we get at least $|S_{3,\text{red}}|/2$ equivalence classes. When $S_{3,\text{blue}}$ is large, it has at least $|S_{3,\text{blue}}|/2$ red outer neighbors, so we get at least $|S_{3,\text{blue}}|/2$ equivalence classes. Overall, we are guaranteed at least $|S_3|/4$ equivalence classes no matter what.