Efficient Algorithms for Clique-Colouring and Biclique-Colouring Unichord-Free Graphs

Abstract

The class of unichord-free graphs was recently investigated in the context of vertex-colouring (Trotignon and Vušković in J Graph Theory 63(1): 31–67, 2010), edge-colouring (Machado et al. in Theor Comput Sci 411(7–9): 1221–1234, 2010) and total-colouring (Machado and de Figueiredo in Discrete Appl Math 159(16): 1851–1864, 2011). Unichord-free graphs proved to have a rich structure that can be used to obtain interesting results with respect to the study of the complexity of colouring problems. In particular, several surprising complexity dichotomies of colouring problems are found in subclasses of unichord-free graphs. In the present work, we investigate clique-colouring and biclique-colouring problems restricted to unichord-free graphs. We show that the clique-chromatic number of a unichord-free graph is at most 3, and that the 2-clique-colourable unichord-free graphs are precisely those that are perfect. Moreover, we describe an O(nm)-time algorithm that returns an optimal clique-colouring of a unichord-free graph input. We prove that the biclique-chromatic number of a unichord-free graph is either equal to or one greater than the size of a largest twin set. Moreover, we describe an $O(n^2m)$-time algorithm that returns an optimal biclique-colouring of a unichord-free graph input. The clique-chromatic and the biclique-chromatic numbers are not monotone with respect to induced subgraphs. The biclique-chromatic number presents an extra unexpected difficulty, as it is not the maximum over the biconnected components, which we overcome by considering additionally the star-biclique-chromatic number.

1 Introduction

Let $G=(V,E)$ be a simple graph with $n=|V|$ vertices and $m=|E|$ edges. A clique of G is a maximal set of vertices that induces a complete subgraph of G with at least one edge. A biclique of G is a maximal set of vertices that induces a complete bipartite subgraph of G with at least one edge. A clique-colouring of G is a colouring of the vertices such that no clique is monochromatic. If the colouring uses at most k colours, then we say that it is a k -clique-colouring. A biclique-colouring of G is colouring of the vertices such that no biclique is monochromatic. If the colouring uses at most k colours, then we say that it is a k -biclique-colouring. The clique-chromatic number of G, denoted by $\kappa (G)$, is the least k for which G has a k-clique-colouring. The biclique-chromatic number of G, denoted by $\kappa _B(G)$, is the least k for which G has a k-biclique-colouring.

Both clique-colouring and biclique-colouring have a “hypergraph colouring version”. Recall that a hypergraph ${\mathcal {H}}=(V,{\mathcal {E}})$ is an ordered pair where V is a set of vertices and ${\mathcal {E}}$ is a set of hyperedges, each of which is a set of vertices. A colouring of a hypergraph ${\mathcal {H}}=(V,{\mathcal {E}})$ is a colouring of the vertices such that no hyperedge is monochromatic. Let $G=(V,E)$ be a graph and let ${\mathcal {H}}_C(G)=(V,{\mathcal {E}}_C)$ and ${\mathcal {H}}_B(G)=(V,{\mathcal {E}}_B)$ be the hypergraphs whose hyperedges are, respectively, ${\mathcal {E}}_C=\{K\subseteq V\mid K \text{ is } \text{ a } \text{ clique } \text{ of } G\}$ and ${\mathcal {E}}_B=\{K\subseteq V\mid K \text{ is } \text{ a } \text{ biclique } \text{ of } G\}$—${\mathcal {H}}_C(G)$ and ${\mathcal {H}}_B(G)$ are called, resp., the clique-hypergraph and the biclique-hypergraph of G. A clique-colouring of G is a colouring of its clique-hypergraph ${\mathcal {H}}_C(G)$; a biclique-colouring of G is a colouring of its biclique-hypergraph ${\mathcal {H}}_B(G)$.

Clique-colouring and biclique-colouring are analogous problems in the sense that they refer to the colouring of hypergraphs arising from graphs. In particular, the hyperedges are subsets of vertices that are cliques (resp. bicliques). The clique is a classical important structure in graphs, hence it is natural that the clique-colouring problem has been studied for a long time—see, for example, [1, 4, 15, 20]. Bicliques, on the other hand, only recently started to be more extensively studied. Although complexity results for complete bipartite subgraph problems are mentioned in [8] and the (maximum) biclique problem is shown to be ${\mathcal {NP}}$-hard in [27], only in the last decade the (maximal) bicliques were rediscovered in the context of counting problems [9, 24], enumeration problems [5, 6, 22, 23], and intersection graphs [11]. For that reason, only recently the biclique-colouring problem started to be investigated [10] and this problem can be seen as “the state of the art” regarding the colouring of biclique-hypergraphs.

Clique-colouring and biclique-colouring have some similarities with usual vertex-colouring; in particular, any vertex-colouring is also a clique-colouring and a biclique-colouring. In other words, both the clique-chromatic number $\kappa$ and the biclique-chromatic number $\kappa _B$ are bounded above by the vertex-chromatic number $\chi$. Optimal vertex-colourings and clique-colourings coincide in the case of $K_3$-free graphs, while optimal vertex-colourings and biclique-colourings coincide in the (much more restricted) case of $K_{1,2}$-free graphs ($K_{1,2}$-free graphs are precisely the disjoint unions of complete graphs). Notice that the triangle $K_3$ is the minimal complete graph that contains, as a proper induced subgraph, the graph induced by one edge ($K_2$), while the $K_{1,2}$ is the minimal complete bipartite graph that contains, as a proper induced subgraph, the graph induced by one edge ($K_{1,1}$).

Clique-colouring and biclique-colouring share essential differences with respect to usual vertex-colouring. A clique-colouring (resp. biclique-colouring) may not be clique-colouring (resp. biclique-colouring) when restricted to a subgraph. Subgraphs may even have a larger clique-chromatic number (resp. larger biclique-chromatic number). Indeed, an odd hole with five vertices $C_5$ and a wheel graph with six vertices $W_6$ are examples (resp. a triangle $K_3$ and a diamond $K_4 \setminus e$). See Fig. 1 (resp. see Fig. 2). Most remarkably, although $\kappa (G)$ is the maximum of the clique-chromatic numbers of the biconnected components, the parameter $\kappa _B(G)$, may not behave well under 1-cutset decomposition.

Fig. 1

Subgraphs may even have a larger clique-chromatic number

Fig. 2

Subgraphs may even have a larger biclique-chromatic number

In the present work, we consider clique-colouring and biclique-colouring problems restricted to unichord-free graphs, which are graphs that do not contain a cycle with a unique chord as an induced subgraph. The class of unichord-free graphs has been investigated in the context of colouring problems—namely vertex-colouring [26], edge-colouring [18], and total-colouring [17], as the results in Table 1 show. Regarding the clique-colouring problem, we show that every unichord-free graph is 3-clique-colourable, and that the 2-clique-colourable unichord-free graphs are precisely those that are perfect. Moreover, we obtain an O(nm)-time algorithm that returns an optimal clique-colouring of a unichord-free graph input. The former result is interesting because perfect unichord-free graphs are a natural subclass of diamond-free perfect graphs, a class that attracted much attention in the context of clique-colouring—clique-colouring diamond-free perfect graphs is notably recognized as a difficult open problem [1, 3, 4]. As a remark, unichord-free and diamond-free graphs have a number of cliques linear in the number of vertices and edges, respectively. Every biconnected component of a unichord-free graph is a complete graph or a triangle-free graph (see Theorem 1), and every edge of a diamond-free graph is in exactly one clique (otherwise we have a diamond). It is also known that the problem of 2-clique-colouring is ${\varSigma }_2^p$-complete for perfect graphs and it is ${\mathcal {NP}}$-complete for $\{K_4$, diamond$\}$-free perfect graphs [4].

Table 1 Computational complexity of colouring problems restricted to unichord-free and special subclasses

Regarding the biclique-colouring problem, we prove that the biclique-chromatic number of a unichord-free graph is either equal to or one greater than the size of a largest set of mutually true twin vertices. Moreover, we describe an $O(n^2m)$-time algorithm that returns an optimal biclique-colouring by returning an optimal biclique-colouring of a unichord-free graph input. Notice that even highly restricted unichord-free graphs have a number of bicliques exponential in the number of vertices, e.g. every graph obtained by taking $t \ge 1$ copies of the complete graph $K_3$ with a vertex in common has $2^t + t$ bicliques (see Fig. 3).

Fig. 3

Unichord-free graph with an exponential number of bicliques

Both clique-colouring and biclique-colouring algorithms developed in the present work follow the same general strategy that is frequently used to obtain vertex-colouring algorithms in classes defined by forbidden subgraphs: a specific structure F is chosen in such a way that one of the following cases holds.

• 1. a graph in the class does not contain F and so belongs to a more restricted subclass for which the solution is already known; or

• 2. a graph contains F and the presence of such structure entails a decomposition into smaller subgraphs in the same class.

The chosen structure for the clique-colouring algorithm is the triangle. If there exists a triangle in the unichord-free graph, we have a decomposition into two smaller graphs with a single vertex in common [26]. Otherwise, the graph is triangle-free and clique-colouring reduces to vertex-colouring. Based on an efficient algorithm for vertex-colouring unichord-free graphs [26], the construction of an efficient algorithm for clique-colouring unichord-free graphs is straightforward. Notice that vertex-colouring is ${\mathcal {NP}}$-hard when restricted to triangle-free graphs [19].

The biclique-colouring algorithm makes a deeper use of the decomposition results of Trotignon and Vušković [26]. The first chosen structure for the biclique-colouring algorithm is the triangle. The second chosen structure for the biclique-colouring algorithm is the square for $\{$triangle, unichord$\}$-free graphs. The third chosen structure is the 2-cutset in a particular setting (to be defined in the next section as a proper 2-cutset) for $\{$square, triangle, unichord$\}$-free graphs. Finally, an extremal decomposition—which is a decomposition whereby one of the biconnected components is undecomposable—is used to biclique-colour $\{$triangle,square,unichord$\}$-free graphs.

The composition of colourings along graphs decomposed when the triangle was the chosen structure is surprisingly difficult in the context of biclique-colouring, while it is straightforward in the context of vertex-colouring and clique-colouring. In order to make the composition more manageable, we introduce star-colouring, as follows. A star is a maximal set of vertices that induces a complete bipartite graph with a universal vertex and at least one edge. A star-colouring is a colouring of the vertices such that no star is monochromatic. If the colouring uses at most k colours, then we say that it is a k -star-colouring. The star-chromatic number of G, denoted by $\kappa _S(G)$, is the least k for which G has a k-star-colouring. A biclique-colouring which is also a star-colouring is the key to provide an $O(n^2m)$-time algorithm that returns an optimal biclique-colouring by returning an optimal star-biclique-colouring of unichord-free graphs. We prove that the biclique-chromatic number and the star-biclique-chromatic number coincide for unichord-free graphs. We remark that by definition, clique-colouring and vertex-colouring coincide for triangle-free graphs, while biclique-colouring and star-biclique-colouring coincide for square-free graphs.

Table 1 highlights the computational complexity of colouring problems restricted to classes related to unichord-free graphs. It is interesting to note that the class of $\{$square, unichord$\}$-free graphs provides: for total-colouring, the surprising example of a class for which total-colouring is Polynomial although edge-colouring is ${\mathcal {NP}}$-complete; while for biclique-colouring, since biclique-colouring and star-colouring coincide, the challenge is to colour the stars. For total-colouring, the difficult decomposition is the proper 1-join, while for biclique-colouring, as we shall see, surprisingly, it is the 1-cutset.

Section 2 reviews the structure of unichord-free graphs according to the decomposition defined by Trotignon and Vušković [26], which is very useful for clique-colouring and biclique-colouring unichord-free graphs throughout this paper. Section 3 contains the clique-colouring results for unichord-free graphs. Section 4 contains the biclique-colouring results for unichord-free graphs. Finally, Sect. 5 contains our concluding remarks.

2 Preliminary Results

In the present section we review the structure of unichord-free graphs according to the decomposition defined by Trotignon and Vušković [26].

Given a graph F, we say that a graph G contains F if F is isomorphic to an induced subgraph of G. A graph G is F -free if it does not contain F. A chordless cycle on n vertices is denoted by $C_n$, $n \ge 3$. A hole is a chordless cycle of length at least 4 and an $\ell$ -hole is a hole of length $\ell$. A triangle is a cycle $C_3$ of length 3 and is a complete graph $K_3$ of order 3. A square is a chordless cycle $C_4$ of length 4 and a 4-hole.

The Petersen graph is the cubic graph on vertices $\{a_1, \ldots , a_5, b_1, \dots , b_5\}$ such that both $a_1a_2a_3a_4a_5a_1$ and $b_1b_2b_3b_4b_5b_1$ are chordless cycles, and such that the only edges between some $a_i$ and some $b_j$ are $a_1b_1$, $a_2b_4$, $a_3b_2$, $a_4b_5$, $a_5b_3$. Note that the Petersen graph contains a 5-hole. The Heawood graph is the cubic bipartite graph on vertices $\{a_1, \ldots , a_{14}\}$ such that $a_1a_2\ldots a_{14}a_1$ is a cycle, and such that the only other edges are $a_{1}a_{10}$, $a_{2}a_{7}$, $a_{3}a_{12}$, $a_{4}a_{9}$, $a_{5}a_{14}$, $a_{6}a_{11}$, $a_{8}a_{13}$. We refer the reader to the Fig. 7 for a picture of the Heawood graph. Note that the Heawood graph contains a 6-hole. We invite the reader to check that both the Petersen graph and the Heawood graph are unichord-free.

A graph is strongly 2-bipartite if it is square-free and bipartite with bipartition (X, Y), where every vertex in X has degree 2 and every vertex in Y has degree at least 3. A strongly 2-bipartite graph is unichord-free because any chord of a cycle is an edge between two vertices of degree at least three, so that every cycle in a strongly 2-bipartite graph is chordless.

A graph G is called basic if it is a complete graph, a hole of length at least 7, a strongly 2-bipartite graph, or an induced subgraph (not necessarily proper) of the Petersen graph or of the Heawood graph. Note that every basic graph is square-free.

A cutset S of a connected graph G is a set of vertices or edges whose removal disconnects G. A graph is biconnected if it is connected and has no cut-vertex. A biconnected component of a graph is a maximal subgraph that is biconnected.

A decomposition of a graph is the systematic removal of a cutset to obtain smaller graphs—called the blocks of decomposition—possibly adding some vertices and edges to connected components of $G \setminus S$, until obtaining a set of basic (indecomposable) graphs. The goal of decomposing a graph is to solve a problem on the original graph by combining the solutions on the blocks of decompositions. The following cutsets are used in the decomposition for unichord-free graphs.

• A 1-cutset of a connected graph $G=(V,E)$ is a vertex v such that V can be partitioned into sets X, Y, and $\{ v \}$, such that there is no edge between X and Y. We say that (X, Y, v) is a split of this 1-cutset.

• A proper 2-cutset of a connected graph $G=(V,E)$ is a pair of non-adjacent vertices a, b, both of degree at least three, such that V can be partitioned into sets X, Y, and $\{ a,b \}$ such that: $|X|\ge 2$, $|Y| \ge 2$; there is no edge between X and Y, and both $G[X \cup \{ a,b \}]$ and $G[Y \cup \{ a,b \}]$ contain a path $a \ldots b$. We say that (X, Y, a, b) is a split of this proper 2-cutset.

• A proper 1-join of a graph $G=(V,E)$ is a partition of V into sets X and Y such that there exist sets $A \subseteq X$ and $B \subseteq Y$ such that: $|A|\ge 2$, $|B| \ge 2$; A and B are stable sets; there are all possible edges between A and B; there is no other edge between X and Y. We say that (X, Y, A, B) is a split of this proper 1-join.

The blocks of decomposition w.r.t. a 1-cutset, a proper 2-cutset, and a proper 1-join are defined precisely as follows. Moreover, all blocks of decomposition of a unichord-free graph were constructed in such a way that they remain unichord-free [26].

• The block of decomposition $G_X$ (resp. $G_Y$) of a graph G w.r.t. a 1-cutset with split (X, Y, v) is $G[X\cup \{ v \} ]$ (resp. $G[Y\cup \{ v\} ]$).

• The blocks of decomposition $G_X$ and $G_Y$ of a graph G w.r.t. a proper 2-cutset with split (X, Y, a, b) are defined as follows. If there exists a vertex c of G such that $N_G(c)=\{ a,b \}$, then let $G_X=G[X \cup \{ a,b,c \}]$ and $G_Y=G[Y \cup \{ a,b,c \}]$. Otherwise, block of decomposition $G_X$ (resp. $G_Y$) is the graph obtained by taking $G[X\cup \{ a,b\}]$ (resp. $G[Y\cup \{ a,b\}]$) and adding a new vertex c adjacent to a, b. Vertex c is called the marker of the block of decomposition $G_X$ (resp. $G_Y$).

• The block of decomposition $G_X$ (resp. $G_Y$) of a graph G w.r.t. a proper 1-join with split (X, Y, A, B) is the graph obtained by taking G[X] (resp. G[Y]) and adding a vertex y adjacent to every vertex of A (resp. x adjacent to every vertex of B). Vertices x, y are called markers of their respective blocks of decomposition.

A decomposition tree of a graph is a rooted tree in which each node corresponds to either G or to a block of decomposition of its parent. We strongly use a decomposition tree defined by Trotignon and Vušković [26], as follows. A proper decomposition tree of a connected unichord-free graph G is a rooted tree $T_G$ such that the following hold:

• 1. G is the root of $T_G$.

• 2. Every node of $T_G$ is a connected graph.

• 3. Every leaf of $T_G$ is basic.

• 4. Every non-leaf node H of $T_G$ is of one of the following types:

  • Type 1 The children of H in $T_G$ are the blocks of decomposition w.r.t. a 1-cutset or a proper 1-join.

  • Type 2 H and all its descendants are {Petersen, triangle, square$\}$-free and have no 1-cutset and no proper 1-join. Moreover, the children of H in $T_G$ are the blocks of decomposition w.r.t. a proper 2-cutset and every non-leaf descendant of H is of type 2.

• 5. If a node of $T_G$ is a triangle-free graph then all its descendants are triangle-free graphs.

We require another property on the type 2 non-leaf node H of $T_G$: (at least) one block of decomposition is basic. It is always possible, since Machado, de Figueiredo, and Vušković [18] proved that every non-basic biconnected $\{$square,unichord$\}$-free graph has the so-called extremal decomposition, which is a decomposition whereby every non-leaf has (at least) one basic block of decomposition. Such decomposition is suitable to extend the colouring of a non-leaf type 2 block of decomposition to the basic block of decomposition. This approach is useful to return an optimal biclique-colouring of $\{$triangle, square, unichord$\}$-free graphs. We refer the reader to Sect. 3.1 for algorithmic and complexity aspects of the construction of the above decomposition tree.

Another decomposition result concerns the complete graphs. If a unichord-free graph G contains a triangle, then either G is a complete graph, or one vertex of the clique that contains this triangle is a 1-cutset of G [26]. Equivalently, we have the following statement, which is a useful tool for clique-colouring and biclique-colouring unichord-free graphs throughout this paper.

Theorem 1

(Trotignon and Vušković [26]) Every biconnected component of a unichord-free graph is a complete graph, or a triangle-free graph.

Finally, Theorem 2 states an algorithm that computes an optimal vertex-colouring of a unichord-free graph. This algorithm is used as a black box to solve the triangle-free case on optimal clique-colouring.

Theorem 2

(Trotignon and Vušković [26]) Let G be a unichord-free graph. The chromatic number of G is $\chi (G)\le \max \{3,\omega (G)\}$. Moreover, there exists an O(nm)-time algorithm that computes an optimal vertex-colouring of any unichord-free graph.

3 Clique-Colouring Unichord-Free Graphs

When a graph is triangle-free, clique-colouring reduces to vertex-colouring. Theorem 2 handles this case. If the unichord-free graph contains a triangle, we entail a decomposition by 1-cutsets given by Theorem 1. The following lemma states that an optimal clique-colouring of a graph can be obtained from optimal clique-colourings of its blocks of decomposition w.r.t. a 1-cutset $G_{X}$ and $G_{Y}$.

Lemma 1

Let G be a graph. An optimal clique-colouring of G can be obtained from optimal clique-colourings of its blocks of decomposition w.r.t. a 1-cutset.

Proof

Let $G_{X}$ and $G_{Y}$ be the blocks of decomposition w.r.t. a 1-cutset in a graph G. Consider optimal clique-colourings of $G_{X}$ and $G_{Y}$ such that the colours of the 1-cutset with respect to the colourings agree, and define in a natural way a colouring of G. The key observation for the proof is that a subset of vertices of a graph G is a clique in G if, and only if, it is a clique either in $G_{X}$ or in $G_{Y}$. Thus, every clique H of G is multi-colored. $\square$

A consequence of Lemma 1 and of Theorem 1 is that the clique-chromatic number of a unichord-free graph is at most 3.

Theorem 3

Every unichord-free graph is 3-clique-colourable.

Proof

We argue by induction on the blocks of decomposition $G_X$ and of $G_Y$ w.r.t. 1-cutsets. If G does not contain a 1-cutset, then G is either a complete graph or a triangle-free graph by Theorem 1. In the former case, we give one vertex colour 1, and all the other vertices colour 2. In the latter case, Theorem 2 assigns a 3-clique-colouring. If G contains a 1-cutset, we entail a decomposition by 1-cutset and apply the induction hypothesis on $G_{X}$ and on $G_{Y}$, both graphs with fewer vertices than G. Hence, both blocks of decomposition have a clique-colouring that uses at most 3 colours. The proof of Lemma 1 combines clique-colourings of $G_{X}$ and of $G_{Y}$ to obtain a clique-colouring of G using at most the maximum number of colours from each clique-colouring, i.e. at most 3 colours. $\square$

A graph is perfect if each of its induced subgraphs has chromatic number equal to its clique number. By the famous Strong Perfect Graph Theorem [2], a graph is perfect precisely if it has no odd-hole nor odd-antihole, where an odd-hole of a graph is an odd-order set of vertices that induces a cycle of size at least five, and an odd-antihole of a graph is an odd-order set of vertices that induces the complement of a cycle of size at least five. Next, we obtain a characterization that the 2-clique-colourable unichord-free graphs are exactly those that are perfect.

Theorem 4

A unichord-free graph is 2-clique-colourable if and only if it is perfect.

Proof

Assume G is 2-clique-colourable. Let B be a biconnected component of G. If B is triangle-free, then a clique-colouring of B is also a vertex-colouring, such that B is 2-vertex-colourable (equivalently bipartite), hence perfect. If B has a triangle then, by Theorem 1, graph B is a complete graph, hence perfect. As a consequence, all blocks of decomposition of G are perfect and so is G.

For the converse, we first prove that G is unichord-free and perfect if and only if G is $\{$unichord, odd-hole$\}$-free and, second, we prove that every $\{$unichord, odd-hole$\}$-free graph is 2-clique-colourable.

Clearly, graph G is perfect only if G is odd-hole-free. Conversely, we claim that a $\{$unichord, odd-hole$\}$ graph G is odd-antihole-free. Suppose G has an odd-antihole A and let $v_{1}, \ldots , v_{|A|}$ be the sequence of consecutive vertices in the odd-hole of the complement $\overline{G} [A]$. Indeed, if $|A| = 5$ then A is an odd-hole (contradiction). Otherwise, i.e. if $|A| \ge 7$, then $G[v_1, v_3, v_4, v_6]$ has a unichord $v_1v_6$ (contradiction). Therefore, G is $\{$unichord,odd-hole,odd-antihole$\}$-free which, by the Strong Perfect Graph Theorem [2], implies that G is unichord-free and perfect.

Now, we prove that a $\{$unichord, odd-hole$\}$-free graph is 2-clique-colourable. Let G be a $\{$unichord, odd-hole$\}$-free graph. Suppose G has an odd cycle. Since G is odd-hole-free, every odd cycle with order at least 5 has a chord. Hence, every biconnected component containing an odd cycle has a triangle. Since G is unichord-free, the biconnected component containing the triangle is a complete graph, and it is 2-clique-colourable. On the other hand, every triangle-free biconnected component has no odd-cycle and it is 2-vertex-colourable, hence 2-clique-colourable. Since every biconnected component is 2-clique-colourable, we conclude (with Lemma 1) that G is 2-clique-colourable. $\square$

3.1 Algorithmic Aspects

Theorem 5 states the complexity to compute an optimal clique-colouring of a unichord-free graph.

Theorem 5

There exists an O(nm)-time algorithm to compute an optimal clique-colouring of a unichord-free graph.

Proof

Let G be a unichord-free graph and (X, Y, v) be the split of a 1-cutset of G. We prove the statement by induction on the blocks of decomposition $G_X$ and $G_Y$ w.r.t. 1-cutset. If G does not contain a 1-cutset, then G is either a complete graph or a triangle-free graph. In the former case, any 2-colouring of its vertices is a clique-colouring, while in the latter case an optimal clique-colouring can be handled by Theorem 2. The given clique-colouring algorithms are respectively linear-time and O(nm)-time. If G contains a 1-cutset, we entail a decomposition by 1-cutset and apply the induction hypothesis on $G_{X}$ and on $G_{Y}$, both graphs with fewer vertices than G. The proof of Lemma 1 gives a constant time algorithm to combine optimal clique-colourings of $G_{X}$ and $G_{Y}$ to obtain an optimal clique-colouring of G. Hence, we are left to prove that the overall time-complexity to give an optimal clique-colouring of $G_{X}$ and of $G_{Y}$ is O(nm). Let $n_X = |V(G_{X})|$, $n_Y = |V(G_{Y})|$, $m_X = |E(G_{X})|$, and $m_Y = |E(G_{Y})|$.

Since blocks of decomposition w.r.t. a 1-cutset have only one vertex in common, we have $n = n_X + n_Y - 1$, $m = m_X + m_Y$. It follows that the overall time-complexity to give an optimal clique-colouring of G is $O(n_X m_X) + O(n_Y m_Y) + O(1) = O(nm)$ and we conclude our proof. $\square$

4 Biclique-Colouring Unichord-Free Graphs

We now turn our attention to the biclique-colouring problem restricted to unichord-free graphs. In contrast to the case of clique-colouring, there exists no analogue of Lemma 1, for the case of biclique-colouring, to combine colourings along 1-cutsets. Indeed, an optimal biclique-colouring of the blocks of decomposition of a graph does not necessarily determine an optimal biclique-colouring of that graph. An example is illustrated in Fig. 4. A star centered in v is a star with universal vertex v. One can check that every star centered in a 1-cutset is also a biclique. The key idea of this section follows. In order to be able to combine colourings along 1-cutsets, we require the colourings of the blocks to be both biclique-colourings and star-colourings. As a remark, notice that there are biclique-colourings that are not star-colourings and vice-versa. See Fig. 5 for instance. A star-biclique-colouring is a biclique-colouring that is also a star-colouring. If the star-biclique-colouring uses at most k colours, then we say that it is a k -star-biclique-colouring. See Fig. 6 for the corresponding star-biclique-colouring versions of the graphs of Fig. 5.

Fig. 4

Unichord-free graph whose blocks of decomposition optimal biclique-colourings do not determine a biclique-colouring. a a unichord-free graph, b one optimal biclique-colouring of its blocks of decomposition, and c shows the existence of a monochromatic star biclique highlighted with bold edges.

The star-biclique-chromatic number of G, denoted by $\kappa _{SB}(G)$, is the least k for which G has a k-star-biclique-colouring. Notice that one more restriction for biclique-colourings might impose the need for more than $\kappa _{B}(G)$ colours to biclique-colour the graph G. Fortunately, we show in Theorem 7 that the star-biclique-chromatic number and the biclique-chromatic number coincide for unichord-free graphs. It is quite interesting to notice that a further restriction makes our lives easier, since we are free to glue biclique-colourings along 1-cutsets and only $\kappa _{B}(G)$ colours are still needed.

Fig. 5

There are biclique-colourings that are not star-colourings and vice-versa. a A star-colouring which is not a biclique-colouring. b A biclique-colouring which is not a star-colouring

Fig. 6

Corresponding star-biclique-colouring versions for the graphs of Fig. 5

We divide this section into two parts. Section 4.1 starts with a 2-star-biclique-colouring algorithm for biconnected unichord-free graphs. This result is very important to start Sect. 4.2 with a constructive proof that star-biclique-chromatic number and the biclique-chromatic number coincide for unichord-free graphs. Section 4.2 then develops an optimal star-biclique-colouring algorithm for non-biconnected unichord-free graphs: Sect. 4.2.1 defines our proposed extremal decomposition tree; Sect. 4.2.2 establishes that the star-biclique-chromatic number of a unichord-free graph G is either $\beta (G)$ or $\beta (G) + 1$, where $\beta (G)$ is the maximum cardinality of a true twin set of graph G; Sect. 4.2.3 then describes the algorithm that decides between these two possible values.

4.1 Biconnected Unichord-Free Graphs

From now on, we consider the complete graphs $K_1$ and $K_2$ biconnected components as in the case where the biconnected component is a complete graph and not in the case where the biconnected component is a triangle-free graph. This assumption helps us with case analysis when we consider biconnected $\{$triangle, unichord$\}$-free graphs and cliques as two distinct cases.

In order to construct an algorithm to combine colourings along 1-cutsets, we start dealing with a biconnected unichord-free graph G, as follows. If G is a complete graph, then an optimal star-biclique-colouring uses |V(G)| colours. Hence, we consider next biconnected $\{$triangle, unichord$\}$-free graphs with at least four vertices. An optimal star-biclique-colouring algorithm of a biconnected $\{$triangle, unichord$\}$-free graph strongly relies on the proper decomposition tree defined in Sect. 2, where (at least) one block of decomposition of the type 2 non-leaf node is basic. Recall that by definition biclique-colouring and star-colouring coincide for square-free graphs. Moreover, every leaf of a proper decomposition tree, a basic graph, is square-free, and that every type 2 non-leaf is square-free.

We hereby construct such optimal star-biclique-colouring algorithm of every biconnected $\{$triangle, unichord$\}$-free graph, as follows. We show in Lemma 2 that every basic graph has a 2-star-biclique-colouring. In fact, we give a slightly stronger result: a basic graph has a 2-star-biclique-colouring even if the colours of two arbitrary vertices at distance 2 are fixed. Such result is suitable to extend the star-biclique-colouring of a biconnected unichord-free graph to any basic graph. As a consequence of this strategy, we are able to show in Lemma 3 that every biconnected $\{$triangle, square, unichord$\}$-free graph has an optimal star-biclique-colouring obtained from optimal star-biclique-colourings of its blocks of decomposition w.r.t. a proper 2-cutset, when one of the blocks is basic. We prove in Lemma 4 that every biconnected $\{$triangle, unichord$\}$-free graph has an optimal star-biclique-colouring obtained from optimal star-biclique-colourings of its blocks of decomposition w.r.t. a proper 1-join. This concludes our algorithm for biconnected $\{$triangle, unichord$\}$-free graphs. Finally, we prove in Lemma 5 that if a unichord-free graph has a square then this graph can be decomposed by a proper 1-join (indeed, there exists a proper 1-join containing this square).

Lemma 2

Let G be a non-complete basic graph. Let M be a vertex of degree 2 and let a and b be two neighbors of M. There exists a 2-star-biclique-colouring of G where a and b have the same colour (resp. have distinct colours).

Proof

Let G be a non-complete basic graph. Recall that the only basic graph that has a triangle is the complete graph, thus the hypotheses imply that vertices a and b are non-adjacent. If G is an even or an odd hole, or G is strongly 2-bipartite, or G is a proper induced subgraph of the Heawood graph, then see Fig. 7 for a 2-star-biclique-colouring of G assuming the colours of two arbitrary vertices at distance 2 are fixed. We observe that for each of the two colourings of the Heawood graph that we give in Fig. 7, the restriction of the colouring to any induced subgraph that contains M, a, and b is still a star-biclique-colouring.

Now, we are left to exhibit a 2-star-biclique-colouring for G a proper induced subgraph of the Petersen graph. Let P be the Petersen graph. There is an automorphism of the Petersen graph that maps a to $a_1$, M to $a_2$, and b to $a_3$ [12].

If a and b have same colour, then consider the following colouring of P. Assign the same colour to all vertices of $V^{\prime } = \{a_{1}, a_{3}, b_ {3}, b_{5}\}$; assign another colour to all vertices of $V(P) \backslash V^{\prime }$. Otherwise, consider the following colouring of P. Assign the same colour to all vertices of $V^{\prime } = \{a_{1}, a_{2}, a_{4}, b_ {2}, b_{3}, b_{5}\}$; assign another colour to all vertices of $V(P) \backslash V^{\prime }$.

There is no $C_4$ in P, and so all bicliques of P (and therefore of G as well) are stars. Note that $a_1$ – $a_2$ – $a_3$ is an induced path of G, and that the non-adjacent vertices $b_3$ and $b_5$ are the only vertices of P that neither belong to nor have a neighbor in $\{a_1, a_2, a_3 \}$. Thus, G has exactly one component (call it C) that contains more than one vertex. Clearly, $a_1, a_2, a_3 \in V (C)$, and furthermore, the stars of G are precisely the stars of C. Since C is connected, triangle-free, and of size at least 3, we have that every star of C contains a 3-vertex path. But by construction, no 3-vertex path of P is monochromatic. Thus, our colouring of P restricted to G is a star-biclique colouring of G. $\square$

Lemma 3

Let G be a biconnected $\{$triangle, square, unichord$\}$-free graph and let $G_X$ and $G_Y$ be the blocks of decomposition w.r.t. a proper 2-cutset in such a way that $G_X$ is basic. If $G_Y$ is 2-star-biclique-colourable then G is 2-star-biclique-colourable.

Proof

A 2-star-biclique-colouring of $G_Y$ can be such that vertices a and b have the same colour or have distinct colours. In any case, by Lemma 2, we have a 2-star-biclique-colouring of $G_{X}$ where the cutset vertices a and b and the marker vertex c of $G_{X}$ have the same colours of a, b, and c of $G_{Y}$. (Actually, the lemma does not explicitly mention the marker. However, since a and b are the only neighbors of c in $G_X$ and in $G_Y$, any valid colour of c in $G_X$ is a valid colour of c in $G_Y$.) The 2-star-biclique colourings of $G_X$ and $G_Y$ determine a 2-colouring of the vertices of G. In what follows, we show that such 2-colouring is indeed a 2-star-biclique colourings of G, except, possibly, for a monochromatic star centered in a or in b, which can be easily multi-coloured.

Recall that there is no $C_4$ in G, which implies that all bicliques are stars. If a star in G is centered in $X\setminus \{a,b\}$ (resp. centered in $Y\setminus \{a,b\}$) then this star is also a star in $G_X$ (resp. in $G_Y$), because the subgraph induced by N[v], $v\in X\setminus \{a,b\}$ (resp. $v\in Y\setminus \{a,b\}$) is the same in G and in $G_X$ (resp. $G_Y$). By assumption, such star is multi-coloured by the colouring of $G_X$ (resp. $G_Y$). If a star S in G is centered in a then there are two possible cases. In the first case, the marker c of $G_Y$ is a real vertex of G. In this case, S contains a star of $G_Y$ which, by assumption, was already multi-coloured by the colouring of $G_Y$, hence S is multi-coloured in the colouring of G as well (the same reasoning could be done by considering that S contains a multi-coloured star of $G_X$). In the second case, the marker c of $G_Y$ is a not real vertex of G. If S is 2-coloured we are done. If S is monochromatic, we simply swap the colour of a. We claim that this swapping does not create a monochromatic star. Indeed, since G is triangle-free, S is the only star of G that is centered in a. Moreover, since the colour of a becomes distinct of the unique colour of its neighborhood, a cannot be a pendant vertex of a monochromatic star. The same reasoning can be applied for a star centered in b. $\square$

Lemma 4

Let G be a biconnected $\{$triangle, unichord$\}$-free graph and let $G_X$ and $G_Y$ be the blocks of decomposition w.r.t. a proper 1-join. If $G_X$ and $G_Y$ are 2-star-biclique-colourable then G is 2-star-biclique-colourable.

Proof

Let vertices y, x be the markers of $G_{X}$ and $G_{Y}$, respectively. By assumption $G_{X}$ and $G_{Y}$ have 2-star-biclique-colourings w.l.o.g. using colours red and blue, where y is blue and x is red, respectively.

Note that $G_X$ has a vertex $p\in A$ coloured red (respectively $G_Y$ has a vertex $q\in B$ coloured blue), for otherwise, there would be a monochromatic star in $G_X$ centered in y (respectively monochromatic star in $G_Y$ centered in x).

From now on, we assume that $x=p$ and $y=q$. This is just a convenience so that we can realize that $G_X = G[X\cup \{q\}]$ and $G_Y=G[Y\cup \{p\}]$, respectively. And this allows to define a natural colouring of G, namely, the one where each vertex of G inherits the colour of $G_X$ or of $G_Y$—in particular, $x=p$ and $y=q$ inherit their colours from both $G_X$ and $G_Y$.

Let H be a star or biclique of G. We consider the following cases (note that no star or biclique could have vertices in $X\setminus A$ and in $Y\setminus B$).

Case 1: $H\subset X$ is a star (resp. is a biclique). In this case, H is a star (resp. is a biclique) of $G_X$. Analogous for $H\subset Y$.

Case 2: H is a star (resp. is a biclique) that contains vertices of $X\setminus A$, of A, and of B. In this case, $H\subset G[X\cup B]$ which implies $H\supset B$, because each vertex in B is adjacent to every vertex of A. Hence $(H\setminus B) \cup \{q\}\subset H$ is a star (resp. is a biclique) of $G_X$. Analogous for H containing vertices of $Y\setminus B$, of B, and of A.

Case 3: $H\subset A\cup B$.

Case 3.1: H is a biclique which implies $H=A\cup B$ and is multi-coloured.

Case 3.2: H is a star centered in $p'\in A$ such that $N(p')\cap (X\setminus A)=\emptyset$ and $N(p')\cap Y = B$. If H is monochromatic, then we may recolour $p'$ red. Analogous for H a star centered in $q'\in B$. $\square$

Lemma 5

Let G be a biconnected unichord-free graph. If G has a square then G has a proper 1-join.

Proof

Let $S=\{v_1,v_2,v_3,v_4\}$ be a square with stable sets $\{v_1,v_3\}$ and $\{v_2,v_4\}$. Let J be a maximal induced complete bipartite subgraph of G such that $S \subseteq V(J)$ and denote the vertices of the two stable sets as $\{x_1=v_1,x_2=v_3,x_3,\ldots ,x_p\}$ and $\{y_1=v_2,y_2=v_4,y_3,\ldots ,y_q\}$. We claim that J determines a proper 1-join of G. We need to show that for every component C of $G \setminus V(J)$, either $N_G(C) \subseteq \{x_1,x_2,x_3,\ldots ,x_p\}$ or $N_G(C) \subseteq \{y_1,y_2,y_3,\ldots ,y_q\}$. First, we remark that no vertex of C has a neighbour in both $\{x_1,x_2,x_3,\ldots ,x_p\}$ and $\{y_1,y_2,y_3,\ldots ,y_q\}$, for otherwise we get an induced diamond or an induced house. Second, we remark that no vertex of C is adjacent to all vertices of either $\{x_1,x_2,x_3,\ldots ,x_p\}$ or $\{y_1,y_2,y_3,\ldots ,y_q\}$, for otherwise we contradict the maximality of J. Now, assume that $N_G(C)$ intersects both $\{x_1,x_2,x_3,\ldots ,x_p\}$ and $\{y_1,y_2,y_3,\ldots ,y_q\}$, and take a minimum-length path $c_1, \ldots , c_k$ in C such that $c_1$ has a neighbour in $\{x_1,x_2,x_3,\ldots ,x_p\}$ and $c_k$ has a neighbour in $\{y_1,y_2,y_3,\ldots ,y_q\}$. Let $i_1, i_2 \in \{1,\ldots , p\}$ and $j_1, j_2 \in \{1,\ldots , q\}$ be such that $c_1$ is adjacent to $x_{i_1}$ and non-adjacent to $x_{i_2}$, and $c_k$ is adjacent to $y_{i_1}$ and non-adjacent to $y_{i_2}$. Now $c_1, \ldots , c_k, x_{i_1}, x_{i_2}, y_{i_1}, y_{i_2}$ induce a unichord, a contradiction. $\square$

A consequence of Lemmas 2, 3, 4, and 5 is that the star-biclique-chromatic number of a $\{$triangle, unichord$\}$-free biconnected component is 2, stated next.

Fig. 7

2-star-biclique-colouring of basic graphs. On the top left two colourings of an even hole, and on the top right two colourings of an odd hole. On the bottom left, two colourings of a strongly 2-bipartite graph. On the bottom right, two colourings of a proper induced subgraph of a Heawood graph (obtained from the Heawood graph by removing the crossed out vertices)

Theorem 6

There exists a 2-star-biclique-colouring of a biconnected $\{$triangle, unichord$\}$-free graph.

Proof

We prove the statement by induction on the number of blocks of decomposition $G_X$ and $G_Y$ w.r.t. proper 1-joins and proper 2-cutsets. If G does not contain a proper 1-join and a proper 2-cutset, then G is a basic graph. The proof of Lemma 2 gives us a recipe to assign a suitable 2-star-biclique-colouring to G. If G contains a proper 1-join, then we entail an extremal decomposition by proper 1-join and apply the induction hypothesis on $G_{X}$ and on $G_{Y}$, both graphs with fewer vertices than G. The proof of Lemma 4 gives us a recipe to combine the 2-star-biclique-colourings of $G_{X}$ and of $G_{Y}$ to obtain a 2-star-biclique-colouring of G. If G does not contain a proper 1-join and contains a proper 2-cutset, then we entail a decomposition by proper 2-cutset and apply the induction hypothesis on basic $G_{X}$ and on $G_{Y}$, both graphs with fewer vertices than G. Note that the hypothesis that G does not contain a proper 1-join implies that G is square-free, by Lemma 5. The proof of Lemma 3 gives us a recipe to combine 2-star-biclique-colourings of basic $G_{X}$ and of $G_{Y}$ to obtain a 2-star-biclique-colouring of G. This concludes our induction. $\square$

4.2 Non-biconnected Unichord-Free Graphs

The given 2-star-biclique-colouring for $\{$triangle, unichord$\}$-free biconnected components is the basis to provide a way to glue biclique-colourings along 1-cutsets. We show below that the star-biclique-colouring strategy also determines an optimal biclique-colouring of a unichord-free graph.

Theorem 7

The biclique-chromatic number and the star-biclique-chromatic number coincide for unichord-free graphs.

Proof

We prove the statement by induction on the number of biconnected components. Suppose that G is a biconnected unichord-free graph. If G is a complete graph, then the bicliques of G are precisely the edges of G and the bicliques of G are precisely the stars of G. Both optimal biclique-colouring and optimal star-biclique-colouring are actually optimal vertex-colouring and have |V(G)| colours. Otherwise G is $\{$triangle, unichord$\}$-free and Theorem 6 states that the star-biclique-chromatic number is 2.

Now, suppose that G is a non-biconnected graph. Suppose that G has an optimal biclique-colouring that is not a star-biclique-colouring, i.e. there is a monochromatic star, say S. Notice that S is not a biclique—because G was given a biclique-colouring—and S is a proper induced subgraph of a biclique that is not a star—and therefore this biclique is biconnected. Hence S is a subset of the vertex-set of a triangle-free biconnected component, say B. We give a new biclique-colouring to G with the same number of colours as before, such that (i) S is polychromatic and (ii) every biclique or star of G polychromatic before the new colouring of B is still polychromatic in the new biclique-colouring of G.

Assign a 2-star-biclique-colouring to B according to Theorem 6, so that S is polychromatic.

For each 1-cutset v of G that is contained in B, proceed as follows. Let $c_1$ (resp. $c_2$) be the colour of v before (resp. after) the new 2-colouring of B. If $c_1 = c_2$, we are done. Let $G^\prime$ be the connected component obtained by all vertices of paths starting from v and not containing vertices of $B \setminus \{v\}$. Clearly, $G^{\prime }$ is a block of decomposition for some split (X, Y, v) of G. Assign colour $c_2$ to v and swap colours $c_1$ and $c_2$ in the block of decomposition $G^{\prime }$. Clearly, since B has a 2-star-biclique-colouring, every star centered in v and every biclique or star properly contained in B are polychromatic. Moreover, clearly, every biclique or star properly contained in the block of decomposition $G^{\prime }$ is polychromatic (before and after the swap), and we are done.

Finally, if we repeat this process for all possible triangle-free biconnected components, we end with a star-biclique-colouring with the same number of colours of an optimal biclique-colouring. This concludes our proof. $\square$

From now on, we are interested in determining an optimal star-biclique-colouring for unichord-free graphs.

4.2.1 Extremal Decomposition Tree for Non-biconnected Graphs

Let B be a biconnected component of a (not necessarily unichord-free) graph G. Let ${\mathcal {C}}(B)$ be the set of 1-cutsets of a graph G that are in a biconnected component B of G. Let $\overline{{\mathcal {C}}}(B) = V(B) \setminus {\mathcal {C}}(B)$. If $|{\mathcal {C}}(B)| = 1$, then B is type ${\mathcal {F}}$. Now, denote by ${\varGamma }_{G}(B, v)$ the set of biconnected components of G that share only vertex v with B, and remark that $B \not \in {\varGamma }_{G}(B, v)$. If every biconnected component in ${\varGamma }_{G}(B, v)$ is type ${\mathcal {F}}$, then ${\varGamma }_{G}(B, v)$ is a type ${\mathcal {F}}$ set. Let ${\mathcal {C}}_{{\mathcal {F}}}(B)$ be the set of all vertices $v \in {\mathcal {C}}(B)$ such that ${\varGamma }_{G}(B, v)$ is a type ${\mathcal {F}}$ set. If $|{\mathcal {C}}_{{\mathcal {F}}}(B)| \ge 1$, then B is type ${\mathcal {S}}$. Now, let ${\mathcal {C}}_{\overline{{\mathcal {F}}}}(B) = {\mathcal {C}}(B) \setminus {\mathcal {C}}_{{\mathcal {F}}}(B)$. If B is type ${\mathcal {S}}$ and $|{\mathcal {C}}_{\overline{{\mathcal {F}}}}(B)| \le 1$, then B is type ${\mathcal {S}}^{*}$. Figure 8 shows examples of the terminology introduced, where the biconnected components not highlighted are not type ${\mathcal {F}}$, ${\mathcal {S}}$, nor ${\mathcal {S}}^*$.

Consider a connected graph G and let ${\varLambda }$ and ${\varXi }$ be the collections of biconnected components of a connected graph that are type ${\mathcal {F}}$ and type ${\mathcal {S}}$. Notice that ${\varLambda }={\varXi }$ if, and only if, G has at most one 1-cutset. In addition, notice that a type ${\mathcal {S}}^*$ is type ${\mathcal {S}}$, but the converse is not always true.

Fig. 8

Unichord-free graph enhancing the biconnected component types

For any connected non-biconnected graph, we prove next that there always exists at least one type ${\mathcal {S}}^{*}$ biconnected component.

Lemma 6

Every connected non-biconnected graph has at least one type ${\mathcal {S}}^{*}$ biconnected component.

Proof

If all biconnected components of G are of type ${\mathcal {F}}$, then they are of type ${\mathcal {S}}^{*}$ as well. So we assume that G contains at least one biconnected component that is not of type ${\mathcal {F}}$. Let $B_0, \ldots , B_k$ (with $k \ge 0$) be a maximal sequence of pairwise distinct biconnected components of G such that none of $B_0, \ldots , B_k$ is of type ${\mathcal {F}}$, and such that for all distinct $i,j \in \{0,\ldots , k\}$, $B_i$ and $B_j$ share a vertex if and only if $|i - j| = 1$. We now show that $B_k$ is of type ${\mathcal {S}}^{*}$. First, $|{\mathcal {C}}_{\overline{{\mathcal {F}}}}(B_k)| \le 1$, for otherwise, the sequence $B_0, \ldots , B_k$ could be extended. Second, since $B_k$ is not of type ${\mathcal {F}}$ (and G is connected but not biconnected), we know that $|{\mathcal {C}}(B_k)| \ge 2$, and so $|{\mathcal {C}}_{\mathcal {F}}(B_k)| = |{\mathcal {C}}(B_k) \setminus {\mathcal {C}}_{\overline{{\mathcal {F}}}}(B_k)| \ge 1$. Thus, $B_k$ is of type ${\mathcal {S}}^{*}$. $\square$

Now, we introduce an extremal decomposition for non-biconnected graphs via a type ${\mathcal {S}}^*$ biconnected component, as follows. Consider a graph G with a type ${\mathcal {S}}^*$ biconnected component $B^*$. Graph G can be decomposed into subgraphs $G_1$ and $G_2$, such that $G_1 = B^* \cup \displaystyle \left( \bigcup _{v \in {\mathcal {C}}_{{\mathcal {F}}}(B^*)} {\varGamma }_{G}(B^*, v)\right)$ (please refer to Fig. 10 for an example of the construction of $G_1$) and $G_2 = G[V(G \setminus G_1) \cup V(B^*)]$. The decomposition algorithms of this section have the following general strategy. We first examine $G_1$ and based on it, we determine possible values for the number of colours needed in the vertices of $B^*$ for a star-biclique-colouring of G. If $G = B^* \cup \displaystyle \left( \bigcup _{v \in {\mathcal {C}}_{{\mathcal {F}}}(B^*)} {\varGamma }_{G}(B^*, v)\right)$, for a type ${\mathcal {S}}^*$ biconnected component $B^*$, then we call G a prime graph, a basic graph for the proposed extremal decomposition. Note that, if G is a prime graph, then $|{\mathcal {C}}_{\overline{{\mathcal {F}}}}(B^*)|=0$. On the other hand, if G is non-prime, then $|{\mathcal {C}}_{\overline{{\mathcal {F}}}}(B^*)|= 1$, and we shall denote by $v^*$ the unique vertex of set ${\mathcal {C}}_{\overline{{\mathcal {F}}}}(B^*)$.

4.2.2 Bounds for Star-Biclique-Chromatic Number of Unichord-Free Graphs

Let u be a vertex of a graph G. The open neighbourhood of u is $N(u) = \{v \in V (G) \mid uv \in E(G)\}$, and the closed neighbourhood of u is $N[u] = N(u) \cup \{u\}$. Two distinct vertices u, v are true twins if $N[u] = N[v]$. This equivalence relation on the vertex set V(G) of a graph defines a partition of V(G) into twin sets. Note that a twin set induces a complete subgraph but a twin set is not necessarily a clique of G.

Let $\beta (G)$ be the size of a largest twin set. Clearly, any twin set—in particular, a largest one—requires distinct colours for each of its vertices in order to give a biclique-colouring.

Lemma 7

The star-biclique-chromatic number of a graph G is at least $\beta (G)$.

Proof

Consider a biclique-colouring for a graph G. Each edge of a twin set defines a biclique. Then, every edge of a twin set requires distinct colours for its extremities and every twin set T requires |T| colours. In particular, a largest twin set requires $\beta (G)$ colours. Therefore, any biclique-colouring (and in particular, any star-biclique-colouring) of G requires at least $\beta (G)$ colours. $\square$

We determine precisely all twin sets of a unichord-free graph in the following lemma. The result is based on the structure of unichord-free graphs as characterized by Theorem 1.

Lemma 8

If G is a unichord-free graph then the twin sets are precisely

• $\overline{{\mathcal {C}}}(B)$, for every complete biconnected component B;

• $\{v\}$, if v is a 1-cutset of G or a vertex of a triangle-free biconnected component.

An example of the twin sets of a unichord-free graphs is illustrated in Fig. 9. The size of the largest twin sets of Fig. 9 is 2.

Fig. 9

Twin sets of a unichord-free graph G, with $\beta (G) = 2$ and $\kappa _B(G) = 2$

We prove that the star-biclique-chromatic number of a unichord-free graph G is at most $\beta (G) + 1$. We first show that every non-biconnected unichord-free prime graph G has a $(\beta (G) + 1)$-star-biclique-colouring. Second, we consider that G has a decomposition via a type ${\mathcal {S}}^*$ biconnected component $B^*$. We assign a $(\beta (G) + 1)$-star-biclique-colouring to the prime graph $G_1$. We modify $G_2$ to $\widetilde{G_2}$ by possibly removing some vertices of $B^*$ so as to obtain $\widetilde{B}$ isomorphic to a $K_{|\overline{{\mathcal {C}}}(B^*)| +1}$, if $B^*$ is complete, or to a $K_2$, if $B^*$ is triangle-free—$\widetilde{B}$ still attaches to the rest of the graph via the same single vertex $v^*$. Note that $v^*$, the unique vertex in ${\mathcal {C}}_{\overline{{\mathcal {F}}}}(B^*)$, belongs to $\widetilde{B}$. We assign recursively a $(\beta (\widetilde{G_2}) + 1)$-star-biclique-colouring to $\widetilde{G_2}$. Finally, we combine the colourings of $G_1$ and of $\widetilde{G_2}$ to obtain a $(\beta (G) + 1)$-star-biclique-colouring for G. This concludes the general idea of the proof of Theorem 8.

Theorem 8

The star-biclique-chromatic number of a connected unichord-free graph G is at most $\beta (G) + 1$.

Proof

Suppose that G is a biconnected unichord-free graph. By Theorem 1, G is complete or triangle-free. If G is complete then $\kappa _{SB}(G) = |V(G)| = \beta (G)$, because every pair of vertices is a star. If G is triangle-free then, by Theorem 6 and Lemma 8, $\kappa _{SB}(G) = 2 = \beta (G) + 1$.

Now, suppose that G is a non-biconnected unichord-free graph and let $B^*$ be a type ${\mathcal {S}}^*$ biconnected component of G.

Suppose that G is a prime graph. Hence, ${\mathcal {C}}(B^*) = {\mathcal {C}}_{\mathcal {F}}(B^*)$, i.e., every component attached to $B^*$ is a type-${\mathcal {F}}$ biconnected component. We start colouring biconnected component $B^*$. If $B^*$ is complete, then we assign colours $1,\ldots ,|\overline{{\mathcal {C}}}(B^*)|$ to the vertices of $\overline{{\mathcal {C}}}(B^*)$, and we assign colour 1 to the vertices of ${\mathcal {C}}(B^*)$. If $B^*$ is triangle-free, we assign a 2-star-biclique-colouring (see Theorem 6) with colours 1 and 2. Now, we colour the type-${\mathcal {F}}$ biconnected components attached to $B^*$. Let $F \in \displaystyle \bigcup _{v \in {\mathcal {C}}(B^*)}{\varGamma }_{G}(B^*, v)$. If F is complete, then we give colours $2, \ldots , |V(F)|$ to the vertices in $\overline{{\mathcal {C}}}(F)$. If F is triangle-free, we assign a 2-star-biclique-colouring (see Theorem 6) with colours 1 and 2 in such a way that the unique vertex in ${\mathcal {C}}(F)$ remains coloured with the same colour assigned by the colouring of $B^*$ (colour 1 if $B^*$ is complete, and colour 1 or 2 if $B^*$ is triangle-free).

Now, suppose that G is not a prime graph and consider graph $\widetilde{G_2}$ constructed as previously defined (just before the statement of the present theorem). Notice that $\widetilde{G_2}$ is smaller than G—indeed, $\widetilde{G_2}$ is a subgraph of $G_2$ which in turn is a proper subgraph of G—so that we can apply induction and assume that $\widetilde{G_2}$ has a $(\beta (\widetilde{G_2})+1)$-star-biclique-colouring. In addition, since every twin set of $\widetilde{G_2}$ is a twin set of G, we have $\beta (\widetilde{G_2})\le \beta (G)$, so that $\widetilde{G_2}$ has a $(\beta (G)+1)$-star-biclique-colouring. We claim that the $(\beta (G)+1)$-star-biclique-colouring of $\widetilde{G_2}$ determines a $(\beta (G)+1)$-star-biclique-colouring of G constructed as follows. Assume, w.l.o.g., that the unique vertex $v^*$ of ${\mathcal {C}}_{\overline{{\mathcal {F}}}}(B^*)$ was coloured $\beta (G)+1$. First, we colour the vertices in $(G\setminus \displaystyle \bigcup _{v \in {\mathcal {C}}_{{\mathcal {F}}}(B^*)} {\varGamma }_{G}(B^*, v))\setminus B^*$ as in the colouring of $\widetilde{G_2}$. Second, we colour the vertices of $B^*$. If $B^*$ is complete, then we assign colours $1, 2, \ldots , |\overline{{\mathcal {C}}}(B^*)|$ to the vertices of $\overline{{\mathcal {C}}}(B^*)$ and colour 1 to the vertices of ${\mathcal {C}}(B^*)\setminus \{v^*\} = {\mathcal {C}}_{{\mathcal {F}}}(B^*)$. If $B^*$ is triangle-free, we assign a 2-star-biclique-colouring (see Theorem 6) with colours $\beta (G)$ and $\beta (G)+1$, such that $v^*$ is coloured $\beta (G)+1$. Finally, let $F \in \displaystyle \bigcup _{v \in {\mathcal {C}}_{{\mathcal {F}}}(B^*)} {\varGamma }_{G}(B^*, v)$ and denote by i the colour received by the unique vertex of ${\mathcal {C}}(F)$ in the above colouring procedure. If F is complete then we assign colours $\{1,2, \ldots , |V(F)|\}\setminus \{i\}$ to the vertices in $\overline{{\mathcal {C}}}(F)$. If F is triangle-free, we assign a 2-star-biclique-colouring (see Theorem 6) such that colour i is assigned to the unique vertex of ${\mathcal {C}}(F)$. $\square$

See Fig. 10 for an example of the $(\beta (G) + 1)$-star-biclique-colouring algorithm given by the constructive proof of Theorem 8.

Fig. 10

An illustration of the $(\beta (G) + 1)$-star-biclique-colouring algorithm for a unichord-free graph G. a Graph decomposition. b Colouring compositions

Notice that Theorem 8 yields an optimal star-biclique-colouring algorithm for any unichord-free graph G that is not $\beta (G)$-star-biclique-colourable—in particular, when $\beta (G) = 1$. From now on, we consider $\beta (G) \ge 2$.

4.2.3 Optimal Star-Biclique-Colouring Algorithm

In the previous section, we showed how to star-biclique-colour a unichord-free graph G using $\beta (G) + 1$ colours. The star-biclique-chromatic number of any graph that contains at least one edge is at least 2, so that a graph has $\kappa _{SB}(G)=\beta (G)$ only if $\beta (G)\ge 2$ or G is edgeless. The goal of the present section is to give an optimal star-biclique-colouring to a unichord-free graph G with $\beta (G)\ge 2$. In the present section, we show how to optimally star-biclique-colour a unichord-free graph G—in some cases, using only $\beta (G)$ colours, instead of the at most $\beta (G)+1$ colours that we used in the previous section. Our strategy to optimally star-biclique-colour a graph G is to determine bounds on the number of colours needed in each biconnected component of G, based only on the local structure of the biconnected component. More precisely, we consider each type ${\mathcal {S}}^*$ biconnected component, looking for a certificate that the input graph G is not $\beta (G)$-star-biclique-colourable—otherwise, we decompose G and continue the search in its decomposition blocks. The decomposition blocks are defined in such a way that, if no obstruction is found in any block of the decomposition tree, then the input graph G is $\beta (G)$-star-biclique-colourable. If a biconnected component is triangle-free, then it can be star-biclique-coloured with 2 colours and is not an obstruction for a star-biclique-colouring of G using $\beta (G) \ge 2$ colours. The case of complete biconnected components is more difficult. As we shall see, a complete type ${\mathcal {S}}^*$ biconnected component may demand $\beta (G) + 1$ colours even if its twin classes are all unitary.

Let G be a connected non-biconnected unichord-free graph and $B^*$ be a complete type ${\mathcal {S}}^*$ biconnected component. Consider the following partition of ${\mathcal {C}}_{{\mathcal {F}}}(B^*)$ into two disjoint sets.

• ${\mathcal {T}}(B^*) = \{v \in {\mathcal {C}}_{{\mathcal {F}}}(B^*) \mid \forall B \in {\varGamma }_{G}(B^*,v), B \simeq K_{\beta (G) + 1}\}$;

• $\overline{{\mathcal {T}}}(B^*) = {\mathcal {C}}_{{\mathcal {F}}}(B^*) \setminus {\mathcal {T}}(B^*)$.

We have the following property about ${\mathcal {T}}(B^*)$.

Lemma 9

Let G be a connected non-biconnected unichord-free graph, $B^*$ be a complete type ${\mathcal {S}}^*$ biconnected component, and $\pi$ be a $\beta (G)$-star-biclique-colouring of G. If $v \in {\mathcal {T}}(B^*)$, then $\pi (v) \ne \pi (u)$ for every $u \in B^*$, $u \ne v$.

Proof

Let B be a complete biconnected component in ${\varGamma }_{G}(B^*,w)$, $w \in {\mathcal {C}}_{{\mathcal {F}}}(B^*)$, with order $\beta (G) + 1$. Let $\pi$ be a $\beta (G)$-star-biclique-colouring of G. $B \setminus \{w\}$ needs $\beta (G)$ colours because it is a twin set of size $\beta (G)$. So, one colour should be repeated at w. Clearly, if every biconnected component in ${\varGamma }_{G}(B^*,w)$ is isomorphic to $K_{\beta (G) + 1}$, there exists a monochromatic star in $G[\cup _{B\in {\varGamma }_{G}(B^*,w)}V(B)]$ with the colour of w, and with the addition of any $u \in B^*$, $u \not = w$, this monochromatic star of $G[\cup _{B\in {\varGamma }_{G}(B^*,w)}V(B)]$ defines a star of G. Hence, $\pi (u) \ne \pi (w)$, for every $u \in B^*$, $u \ne w$, and for every $\beta (G)$-star-biclique-colouring $\pi$ of G. $\square$

Note that the set of vertices of a complete type-${\mathcal {S}}^*$ biconnected component $B^*$ can be partitioned into four subsets of vertices, each one playing a particular role in the structure of $B^*$:

• The set $\overline{{\mathcal {C}}}(B^*)$ contains the vertices of $B^*$ that belong to only one biconnected component. Its key property is that by Lemma 8 the set $\overline{{\mathcal {C}}}(B^*)$ defines a twin set and so by Lemma 7 if $\pi$ is a $\beta$-star-biclique-colouring, then no two vertices in the set $\overline{{\mathcal {C}}}(B^*)$ may have the same colour.

• The set ${\mathcal {T}}(B^*)$ contains the vertices of $B^*$ that belong to one or more type-${\mathcal {F}}$ biconnected components, all of which are complete graphs on $\beta +1$ vertices. Its key property, established in Lemma 9, is that, if $\pi$ is a $\beta$-star-biclique-colouring, then each vertex must have a colour that is distinct from any other colour used in $B^*$.

• The set $\overline{{\mathcal {T}}}(B^*)$ contains the vertices of $B^*$ that belong to one or more type-${\mathcal {F}}$ biconnected components, at least one of which is not a complete graph on $\beta +1$ vertices. The vertices of $\overline{{\mathcal {T}}}(B^*)$ do not impose particular colouring restrictions to $B^*$. If $\pi$ is a $\beta$-star-biclique-colouring, then the vertices of the set $\overline{{\mathcal {T}}}(B^*)$ can all receive the same colour, and a colour used $\overline{{\mathcal {C}}}(B^*)$ can be used in $\overline{{\mathcal {T}}}(B^*)$.

• ${\mathcal {C}}_{\overline{{\mathcal {F}}}}(B^*)=\{v^*\}$ is the “connection” between $B^*$ and the “rest of the graph”. The only restriction on the colour of $v^*$ is that it must be distinct of any colour used in ${\mathcal {T}}(B^*)$. The colour of $v^*$ might be the same as some colour used in $\overline{{\mathcal {C}}}(B^*)$ or in $\overline{{\mathcal {T}}}(B^*)$, as long as this does not force a monocromatic star centered in $v^*$, but this cannot be determined by looking only at the local structure of $B^*$, because the stars centered in $v^*$ contain vertices that do not belong to $B^*$.

We may determine that a graph is not $\beta$-star-biclique-colourable by looking only at the local structure of $B^*$. However, if such NO certificate is not found, we need to continue and analyse the rest of the graph. What we do is to contract $B^*$—but, this new contraction must capture the number of colours demanded by $B^*$. In order to define a suitable contraction, we determine bounds on the number of colours demanded by $B^*$.

Let G be a connected non-biconnected unichord-free graph with $\kappa _{SB}(G)=\beta (G)\ge 2$ and $B^*$ be a type ${\mathcal {S}}^*$ biconnected component. We denote by $f(B^*)$ the minimum number of colours used in $B^*$ in any $\beta (G)$-star-biclique-colouring of G. The partition of the vertices of a complete $B^*$ into sets ${\mathcal {C}}_{\overline{{\mathcal {F}}}}(B^*)$, ${\mathcal {T}}(B^*)$, $\overline{{\mathcal {T}}}(B^*)$, and $\overline{{\mathcal {C}}}(B^*)$ allows us to determine in Lemma 10 bounds for the possible values of $f(B^*)$.

Lemma 10

Let G be a non-prime $\beta (G)$-star-biclique-colourable connected non-biconnected unichord-free graph, and $B^*$ be a type ${\mathcal {S}}^*$ biconnected component.

• If $B^*$ is triangle-free, then $f(B^*) \le 2$;

• If $B^*$ is complete, $\overline{{\mathcal {T}}}(B^*) = \emptyset$, and $\overline{{\mathcal {C}}}(B^*) = \emptyset$ (implying ${\mathcal {T}}(B^*) \ne \emptyset$), then

  $$\begin{aligned} f(B^*) = |{\mathcal {T}}(B^*)| + 1; \end{aligned}$$

• If $B^*$ is complete, $\overline{{\mathcal {T}}}(B^*) \ne \emptyset$, and $\overline{{\mathcal {C}}}(B^*) = \emptyset$, then

  $$\begin{aligned} |{\mathcal {T}}(B^*)| + 1 \le f(B^*) \le |{\mathcal {T}}(B^*)| + 2; \end{aligned}$$

• If $B^*$ is complete and $\overline{{\mathcal {C}}}(B^*) \ne \emptyset$, then

  $$\begin{aligned} |{\mathcal {T}}(B^*)| + |\overline{{\mathcal {C}}}(B^*)| \le f(B^*) \le |{\mathcal {T}}(B^*)| + |\overline{{\mathcal {C}}}(B^*)| + 1. \end{aligned}$$

Proof

If G is $\beta (G)$-star-biclique-colourable, then G admits a $\beta (G)$-star-biclique-colouring such that every triangle-free biconnected component $B^*$ is 2-star-biclique-coloured, which implies $f(B^*) \le 2$. Hence we suppose that $B^*$ is complete. Consider a $\beta (G)$-star-biclique-colouring of G. Let v be a vertex of $B^*$. If $v \in \overline{{\mathcal {T}}}(B^*)$, then we can colour all biconnected components in ${\varGamma }_{G}(B^*,v)$ in order to make all stars and bicliques in $G[\cup _{B\in {\varGamma }_{G}(B^*,v)}V(B)]$ polychromatic. Hence, every $u \ne v$ in $\overline{{\mathcal {T}}}(B^*)$ can have the same colour as the colour assigned to v. In particular, we may assume that all vertices of $\overline{{\mathcal {T}}}(B^*)$ have the same colour. By Lemma 9, $f(B^*) \ge |{\mathcal {T}}(B^*)| + 1$ if $B^*$ is complete. Note that the unique vertex $v^*$ of ${\mathcal {C}}_{\overline{{\mathcal {F}}}}(B^*)$ must have a distinct colour from those colours assigned to the vertices of ${\mathcal {T}}(B^*)$. Hence, $f(B^*) = |{\mathcal {T}}(B^*)| + 1$ if $B^*$ is complete, $\overline{{\mathcal {T}}}(B^*) = \emptyset$, and $\overline{{\mathcal {C}}}(B^*) = \emptyset$. On the other hand, note that $v^*$ may require a colour different from the colour assigned to all vertices in $\overline{{\mathcal {T}}}(B^*)$. Hence, $f(B^*) \le |{\mathcal {T}}(B^*)| + 2$ if $B^*$ is complete, $\overline{{\mathcal {T}}}(B^*) \ne \emptyset$, and $\overline{{\mathcal {C}}}(B^*) = \emptyset$. Now, note that every pair of vertices in $\overline{{\mathcal {C}}}(B^*)$ is a twin set and induces a biclique of G. Hence, all vertices in $\overline{{\mathcal {C}}}(B^*)$ must have distinct colours. On the other hand, all vertices of $\overline{{\mathcal {T}}}(B^*)$ can have the same colour of a vertex in $\overline{{\mathcal {C}}}(B^*)$. Hence, $f(B^*) \ge |{\mathcal {T}}(B^*)| + |\overline{{\mathcal {C}}}(B^*)|$ if $B^*$ is complete and $\overline{{\mathcal {C}}}(B^*) \ne \emptyset$. Finally, note that $v^*$ may require a colour different from the colours assigned to the vertices in $\overline{{\mathcal {C}}}(B^*)$. Hence, $f(B^*) \le |{\mathcal {T}}(B^*)| + |\overline{{\mathcal {C}}}(B^*)| + 1$ if $B^*$ is complete and $\overline{{\mathcal {C}}}(B^*) \ne \emptyset$. $\square$

Lemma 10 provides a necessary condition for a graph G to be $\beta (G)$-star-biclique-colourable, namely, that for any type ${\mathcal {S}}^*$ biconnected component $B^*$, the lower bound given by Lemma 10 for $f(B^*)$ does not exceed $\beta (G)$. For that reason, it is useful to define a new function $g(\cdot )$ that returns a lower bound for $f(B^*)$ in terms of ${\mathcal {T}}(B^*)$, $\overline{{\mathcal {T}}}(B^*)$, and $\overline{{\mathcal {C}}}(B^*)$:

• $g(B^*) = 1$, if $B^*$ is triangle-free.

• $g(B^*) = |{\mathcal {T}}(B^*)| + 1$, if $B^*$ is complete and $\overline{{\mathcal {C}}}(B^*) = \emptyset$.

• $g(B^*) = |{\mathcal {T}}(B^*)| + |\overline{{\mathcal {C}}}(B^*)|$, if $B^*$ is complete and $\overline{{\mathcal {C}}}(B^*) \ne \emptyset$.

Note that if $B^*$ is complete, then $g(B^*)$ describes the exact number of colours that is needed in the vertices of $B^*\setminus v^*$, where $v^*$ denotes the unique vertex in ${\mathcal {C}}_{\overline{{\mathcal {F}}}}(B^*)$. The range of two possible values for $f(B^*)$ in some of the cases of Lemma 10 is due to the fact that one cannot determine, only by looking at $B^*$, whether the vertex $v^*$ demands a new colour not used in $B^*\setminus v^*$. In other words, vertex $v^*$ could possibly have the same colour as some vertex in $\overline{{\mathcal {C}}}(B^*)$ or in $\overline{{\mathcal {T}}}(B^*)$, as long as this does not create in G any monochromatic star centered in $v^*$—and this information will be given as soon as the recursion call returns.

In the case of prime graphs, the inexistence of $v^*\in {\mathcal {C}}_{\overline{{\mathcal {F}}}}(B^*)$ allows the precise determination of $f(B^*)$ and the characterization of $\beta (G)$-star-biclique-colourable graphs. The proof is omitted due to its similarity with the proof of Lemma 10.

Lemma 11

Let G be a prime connected non-biconnected unichord-free graph with $\beta (G) \ge 2$ and let $B^*$ be a type ${\mathcal {S}}^*$ biconnected component of G. Graph G is $\beta (G)$-star-biclique-colourable if, and only if, (at least) one of the following condition holds.

• $B^*$ is triangle-free;

• $B^*$ is complete, $\overline{{\mathcal {T}}}(B^*) = \emptyset$, and $\overline{{\mathcal {C}}}(B^*) = \emptyset$ (implying ${\mathcal {T}}(B^*) \ne \emptyset$), and

  $$\begin{aligned} |{\mathcal {T}}(B^*)|\le \beta (G); \end{aligned}$$

• If $B^*$ is complete, $\overline{{\mathcal {T}}}(B^*) \ne \emptyset$, and $\overline{{\mathcal {C}}}(B^*) = \emptyset$, and

  $$\begin{aligned} |{\mathcal {T}}(B^*)| + 1\le \beta (G); \end{aligned}$$

• If $B^*$ is complete and $\overline{{\mathcal {C}}}(B^*) \ne \emptyset$, and

  $$\begin{aligned} |{\mathcal {T}}(B^*)| + |\overline{{\mathcal {C}}}(B^*)|\le \beta (G). \end{aligned}$$

Suppose that G has a decomposition via type ${\mathcal {S}}^*$ biconnected component $B^*$. In the light of Lemma 10, we modify $G_2$ to $\widehat{G_2}$ by possibly removing some vertices of $B^*$ so as to obtain $\widehat{B}$ isomorphic to

• $K_2$ if $B^*$ is triangle-free,

• $K_{|{\mathcal {T}}(B^*)| + 1} = B^*$ if $B^*$ is complete, $\overline{{\mathcal {T}}}(B^*) = \emptyset$, and $\overline{{\mathcal {C}}}(B^*) = \emptyset$,

• $K_{|{\mathcal {T}}(B^*)| + 2}$ if $B^*$ is complete, $\overline{{\mathcal {T}}}(B^*) \ne \emptyset$, and $\overline{{\mathcal {C}}}(B^*) = \emptyset$, or

• $K_{|{\mathcal {T}}(B^*)| + |\overline{{\mathcal {C}}}(B^*)| + 1}$ if $B^*$ is complete and $\overline{{\mathcal {C}}}(B^*) \ne \emptyset$.

$\widehat{B}$ still attaches to the rest of the graph via the same single vertex $v^*$.

Note that $v^*$, the unique vertex in ${\mathcal {C}}_{\overline{{\mathcal {F}}}}(B^*)$, belongs to $\widehat{B}$, and note that $\kappa _{SB}(\widehat{G_2}) \le \kappa _{SB}(G)$. The following characterization of non-prime non-biconnected unichord-free graphs that are $\beta (G)$-star-biclique-colourable is the missing step in the proposed optimal star-biclique-colouring algorithm.

Theorem 9

Let G be a non-prime non-biconnected unichord-free graph with $\beta (G) \ge 2$, $B^*$ be a type ${\mathcal {S}}^*$ biconnected component and $G_1$ and $\widehat{G_2}$ obtained by the decomposition via $B^*$. Graph G is $\beta (G)$-star-biclique-colourable if, and only if, $g(B^*) \le \beta (G)$ and $\kappa _{SB}(\widehat{G_2}) \le \beta (G)$.

Proof

First we prove the necessary condition. Note that $g(B^*)$ determines a lower bound for the number of colours that appear in $B^*$ in any $\beta (G)$-star-biclique-colouring of G. Then, G cannot be $\beta (G)$-star-biclique-colourable if $g(B^*) > \beta (G)$. Moreover, note that a $\beta (G)$-star-biclique-colouring of G easily determines a $\beta (G)$-star-biclique-colouring of $\widehat{G_2}$. Assign to the vertices of $(V(\widehat{G_2})\setminus V(\widehat{B}))\cup \{v^*\}$ the same colour they receive in G. Finally, assign $|V(\widehat{B})| - 1$ distinct colours not used in $v^*$ to the vertices in $\widehat{B}\setminus v^*$.

For the converse, assume that $g(B^*) \le \beta (G)$ and $\kappa _{SB}(\widehat{G_2}) \le \beta (G)$. Consider a $\beta (G)$-star-biclique-colouring of $\widehat{G_2}$. We show how to extend this colouring to G. We claim that the $\beta (G)$-star-biclique-colouring of $\widehat{G_2}$ determines a $\beta (G)$-star-biclique-colouring of G constructed as follows. Assume, w.l.o.g., that the unique vertex $v^*$ of ${\mathcal {C}}_{\overline{{\mathcal {F}}}}(B^*)$ was coloured $\beta (G)$. First, we colour the vertices in $(G\setminus \displaystyle \bigcup _{v \in {\mathcal {C}}_{{\mathcal {F}}}(B^*)} {\varGamma }_{G}(B^*, v))\setminus B^*$ as in the colouring of $\widehat{G_2}$. Second, we colour the vertices of $B^*$. If $B^*$ is complete, then consider the following colouring.

• Assign colours $1,\ldots ,|{\mathcal {T}}(B^*)|$ to vertices of ${\mathcal {T}}(B^*)$;

• Assign colour $|{\mathcal {T}}(B^*)|+1$ to every vertex in $\overline{{\mathcal {T}}}(B^*)$;

• Assign colours $|{\mathcal {T}}(B^*)| + 1, \ldots , |{\mathcal {T}}(B^*)| + |\overline{{\mathcal {C}}}(B^*)|$ to vertices of $\overline{{\mathcal {C}}}(B^*)$.

If $B^*$ is triangle-free, we assign a 2-star-biclique-colouring (see Theorem 6) with colours $\beta (G)- 1$ and $\beta (G)$.

Finally, let $F \in \displaystyle \bigcup _{v \in {\mathcal {C}}_{{\mathcal {F}}}(B^*)} {\varGamma }_{G}(B^*, v)$ and denote by i the colour received by the unique vertex of ${\mathcal {C}}(F)$ in the above colouring procedure. If F is triangle-free, then we assign a 2-star-biclique-colouring (see Theorem 6) such that colour i is assigned to the unique vertex of ${\mathcal {C}}(F)$. If F is complete, then we need to distinguish two cases: if $|V(F)|=\beta +1$, then we assign colours $\{1,\ldots ,\beta \}$ to the vertices in $\overline{{\mathcal {C}}}(F)$, otherwise $|V(F)|\le \beta$ and we assign colours $\{1,2, \ldots , |V(F)|\}\setminus \{i\}$ to the vertices in $\overline{{\mathcal {C}}}(F)$. $\square$

See Fig. 11 for an example of the $\beta (G)$-star-biclique-colouring algorithm given by the constructive proof of Theorem 9, where $\kappa _{SB}(G) = \beta (G) = 3$. Note that the recursion can stop as soon as $\beta (\widehat{G_2}) < \beta (G)$ or $\widehat{G_2}$ is prime.

Fig. 11

An illustration of the $\beta (G)$-star-biclique-colouring algorithm for a $\beta (G)$-star-biclique-colourable unichord-free graph G. a Graph decomposition. b Colouring compositions

4.3 Algorithmic Aspects

Let G be a biconnected unichord-free graph. If G is a complete graph, then an optimal star-biclique-colouring uses |V(G)| colours. Now, we consider G as a biconnected $\{$triangle, unichord$\}$-free graph. An optimal star-biclique-colouring algorithm of G strongly relies on the proper decomposition tree defined in Sect. 2, where (at least) one block of decomposition of the type 2 non-leaf node is basic.

We construct a proper decomposition tree $T_G$ of the input graph G in time $O(n^2m)$. It is shown by Trotignon and Vušković [26] an O(nm)-time algorithm to output a proper decomposition tree of a unichord-free graph. In their algorithm, we replace the $O(n + m)$-time algorithm to find a proper 2-cutset (if any) in a unichord-free graph with no 1-cutset and no proper 1-join by the following O(nm)-time algorithm. Consider all possible 2-cutset decompositions of G and pick a proper 2-cutset S that has a block of decomposition B whose size is smallest possible. Machado, de Figueiredo, and Vušković [18] showed that B must be basic. All proper 2-cutsets (and its blocks of decomposition orders) can be found in O(nm)-time. Indeed, for any vertex v, find all 1-cutsets and all blocks of decomposition of $G \setminus \{v\}$ with depth-first search. For any such block of decomposition, check whether the corresponding 1-cutset u is such that $\{u, v\}$ is a proper 2-cutset. Keep in memory the size of its blocks of decomposition and choose a proper 2-cutset with a block of decomposition of minimum size among them. We now have an algorithm to output a proper decomposition tree such that every proper 2-cutset subtree decomposition is extremal. On the other hand, it raised to $O(n^2m)$ the time-complexity of the algorithm to output such proper decomposition tree, because we replaced an $O(n + m)$-time algorithm to find a proper 2-cutset by an O(nm)-time algorithm.

Now, we discuss the time-complexity to combine solutions of the blocks of decomposition of a given node of $T_G$. We have three cases.

• Non-leaf node H of type 1 of $T_G$. Lemma 4 shows how to proceed (in constant time) to find a star-biclique-colouring of H by asking recursively for appropriately chosen star-biclique-colouring of its children.

• Non-leaf node H of type 2 of $T_G$. Lemma 3 shows how to proceed (in constant time) to find a star-biclique-colouring of H in two steps. First, by asking recursively for appropriately chosen star-biclique-colouring of its non-basic child, if exists such non-basic child, or one basic child, otherwise. Second, the given star-biclique-colouring is extended to the other block of decomposition by asking recursively for an appropriately chosen star-biclique-colouring of the non-basic child. Note that since H is of type 2, every non-leaf descendant of H is of type 2. Hence, all leaves under H will have a 2-star-biclique-colouring computed by Lemma 2.

• Leaf node H of $T_G$. Lemma 2 shows how to proceed in linear-time to find a 2-star-biclique-colouring of H.

So the time-complexity to combine solutions of the blocks of decomposition at each non-leaf node of $T_G$ is O(1). It is proved that $T_G$ is O(n) [26] and the sum of time-complexity to give a 2-star-biclique-colouring at the leaves of $T_G$ is $O(n+m)$, which means that the time-complexity to process the tree is $O(n+m)$.

Notice that the bottleneck of this algorithm is to construct the proper decomposition tree, i.e. the time-complexity is $O(n^2m)$.

Lemma 12

There exists an $O(n^2m)$-time algorithm to compute a 2-star-biclique-colouring of a $\{$triangle, unichord$\}$-free graph.

Now, we determine the largest size of a twin set and how to find a ${\mathcal {S}}^*$ biconnected component. This will be useful to compute the optimal star-biclique-colouring for unichord-free graphs. The proposed algorithms rely on Tarjan’s linear-time algorithm to determine all biconnected components of a graph [25]. We add two integers for each vertex v of the input graph. Integer $i_1$ stores the number $|{\varGamma }_G(B, v) \cup B|$ of biconnected components containing v and we can easily modify Tarjan’s linear-time algorithm to compute it. Integer $i_2$ stores the number of biconnected components containing v that are type ${\mathcal {F}}$. We identify every biconnected component that is type ${\mathcal {F}}$ in the graph searching for those biconnected components that contain exactly one vertex with $i_1 \ge 2$.

We identify every biconnected component that is type ${\mathcal {S}}^*$ in a unichord-free graph, as follows. Search for the biconnected components that contain exactly one vertex with $i_1 = i_2 \ge 2$, for the biconnected components that are type ${\mathcal {F}}$, or contain at least one vertex with $i_1 = i_2 + 1 \ge 2$ and at most one vertex with $i_1 \ge i_2 + 2$, for biconnected components that are non-type ${\mathcal {F}}$.

Lemma 13

Let $G=(V,E)$ be a biconnected unichord-free graph with $n=|V|$ and $m=|E|$. There exists an $O(n+m)$ algorithm to find all ${\mathcal {S}}^*$ biconnected components of a unichord-free graph.

We compute the largest size of a twin set of a graph G, as follows. By Lemma 8, we have the following twin sets: each vertex of a triangle-free biconnected component, each vertex with $i_1 \ge 2$, and each maximal subset of vertices with $i_1 = 1$ belonging to the same complete biconnected component. Keep in memory the size of each twin set and choose a largest one. Clearly, it is a linear-time algorithm.

Lemma 14

There exists a linear-time algorithm to compute the largest size of a twin set of a graph.

Now, we discuss the constructive proof of Theorem 8, which yields an $O(n^2m)$-time algorithm to compute a $(\beta (G) + 1)$-star-biclique-colouring of a unichord-free graph. We already discussed in Lemma 12 when G is a biconnected component. Now, suppose that G is a connected non-biconnected unichord-free graph. Suppose that G is a prime graph. Theorem 8 yields a linear-time algorithm, if G does not contain a triangle-free biconnected component, or an $O(n^2m)$-time algorithm, otherwise, to compute a $(\beta (G) + 1)$-star-biclique-colouring of G. Now, suppose that G is not a prime graph. We entail a decomposition via type ${\mathcal {S}}^*$ biconnected components, say $B^*$. Theorem 8 applies recursion on $\widetilde{G_{2}}$ to assign a $(\beta (\widetilde{G_{2}}) + 1)$-star-biclique-colouring, where $\beta (\widetilde{G_{2}}) \le \beta (G)$. The proof of Theorem 8 gives an algorithm to extend the star-biclique-colouring of $\widetilde{G_{2}}$ to G, which is a $(\beta (G) + 1)$-star-biclique-colouring of $G_1$. Graphs $G_1$ and $\widetilde{G_{2}}$ have at least $K_2$ and at most $B^*$ in common. Hence, we have

• $|V(G_{1})| + |V(\widetilde{G_{2}})| - |V(B^*)| \le n \le |V(G_{1})| + |V(\widetilde{G_{2}})| - 2$ and

• $|E(G_{1})| + |E(\widetilde{G_{2}})| - 1 \le m \le |E(G_{1})| + |E(\widetilde{G_{2}})| - |E(B^*)|$.

It follows that the overall time-complexity to give a $(\beta (G) + 1)$-star-biclique-colouring of $G_{1}$ and of $G_{2}$ is $O(n^2m)$.

Lemma 15

There exists an $O(n^2m)$-time algorithm to compute a $(\beta (G) + 1)$-star-biclique-colouring of a given unichord-free graph G.

The constructive proof of Theorem 9 yields an $O(n^2m)$-time algorithm to compute a $(\beta (G))$-star-biclique-colouring of a unichord-free graph, if such colouring is possible. The time-complexity case analysis is very similar to that of Lemma 15.

Lemma 16

There exists an $O(n^2m)$-time algorithm to compute a $\beta (G)$-star-biclique-colouring of a given unichord-free graph G, if such colouring exists.

In order to check if the unichord-free graph input is indeed $\beta (G)$-star-biclique-colourable, we need to check if $g(B^*)$ is at most $\beta (G)$ and $\widehat{G_{2}}$ is $\beta (G)$-star-biclique-colourable. If it is not the case, Lemma 15 yields the optimal star-biclique-colouring to G. Otherwise, Lemma 16 yields the optimal star-biclique-colouring to G.

Theorem 10

There exists an $O(n^2m)$-time algorithm to assign an optimal star-biclique-colouring to a unichord-free graph G.

5 Conclusion

In our extended abstract [7] presented at LATIN 2012, we showed that the biclique-chromatic number of a unichord-free graph is at most its clique-number. Unfortunately, this upper bound may be very large compared to the actual biclique-chromatic number. Let $H_n$ be the graph on vertices $\{a_1, \ldots , a_{\frac{n}{2}}, b_1, \ldots , b_{\frac{n}{2}}\}$ such that $\{a_1, \ldots , a_{\frac{n}{2}}\}$ is a complete set, $\{b_1, \ldots , b_{\frac{n}{2}}\}$ is a stable set, and such that the only edges between some $a_i$ and some $b_j$ are $a_{i}b_{i}$, for each $1 \le i \le {\frac{n}{2}}$. Since $H_n$ is square-free, every biclique is a star, and H is clearly 2-biclique-colourable, but the clique-number of $H_n$ is $\frac{n}{2}$. In the present work, we strengthen the bounds by showing that the biclique-chromatic number of a unichord-free graph is the increment of or exactly the size of a largest twin set. Note that $\beta (H_n) = 1$.

The graph $H_6$ is called a net. A block graph is a graph in which every biconnected component is a clique. Groshaus, Soulignac, and Terlisky [10] gave an optimal star-biclique-colouring algorithm for net-free block graphs. A cactus graph is a graph in which every nontrivial biconnected component is a cycle. In our previous extended abstract, we gave an optimal biclique-colouring algorithm for cacti graphs. The class of net-free block graphs is incomparable to the class of cacti graphs. Indeed, a complete graph with four vertices $K_4$ and a chordless cycle with four vertices $C_4$ are examples. Nevertheless, both classes are unichord-free subclasses. In the present work, we give an optimal biclique-colouring algorithm for unichord-free graphs.

Finally, we show that $\{K_3, unichord\}$-free graphs are polynomial-time 2-star-biclique-colourable. On one hand, the obtained 2-star-biclique-colouring leads to an optimal biclique-colouring polynomial-time algorithm for unichord-free graphs. On the other hand, it is an open problem to determine the biclique-colouring complexity for $K_3$-free graphs [10]. We remark that Groshaus, Soulignac, and Terlisky [10] gave a polynomial-time 2-star-colouring algorithm for $K_3$-free graphs.