1 Introduction

All graphs considered here are finite, simple and nonempty. Let G be a graph with vertex set V(G) and edge set E(G). The number of vertices of G is called the order of G and let n and m denote |V(G)| and |E(G)|, respectively. For a vertex \(v\in V(G)\), the open neighborhood N(v) of v is defined as the set of vertices adjacent to v, i.e., \(N(v) = \{u:\, uv\in E(G)\}\). The closed neighborhood of v is \(N[v] = N(v)\cup \{v\}\). Every vertex in N(v) is also called a neighbor of v. The degree of v is equal to |N(v)|, denoted by \(d_G(v)\) or simply d(v). For a subset \(S\subseteq V(G)\), the subgraph induced by S is denoted by G[S]. As usual, \(K_n\), \(P_n\) and \(C_n\) denote the complete graph, path and cycle on n vertices, respectively. For standard terminology not given here we refer the reader to Bondy and Murty (2008).

A hypergraph \(\mathcal {H}\) is a pair \((V, \mathcal {E})\) where V is a finite set of vertices and \(\mathcal {E}\) is a family of non-empty subsets of V called hyperedges. A k-colouring of \(\mathcal {H}\) is a mapping \(\phi : V\rightarrow \{1, 2, \ldots , k\}\) such that for each \(S\in \mathcal {E}\), with \(|S|\ge 2\), there exist \(u, v\in S\) with \(\phi (u)\ne \phi (v)\), that is, there is no monochromatic hyperedge of size at least two. If such a function exists we say that \(\mathcal {H}\) is k-colorable. The chromatic number \(\chi (\mathcal {H})\) of \(\mathcal {H}\) is the smallest k for which \(\mathcal {H}\) admits a k-colouring.

A clique C is defined as a complete subgraph of a graph G, or equivalently a subset of V(G), which induces a complete subgraph of G. A clique is said to be maximal if it is not properly contained in any other clique of G. We call clique-hypergraph of G the hypergraph \(\mathcal {H}(G)=(V,\mathcal {E})\) that has the same vertices as G and whose set of hyperedges is the set of maximal cliques of G of cardinality at least 2.

A k-coloring of the clique-hypergraph \(\mathcal {H}(G)\) is also called a k-clique-coloring of G, and the chromatic number \(\chi (\mathcal {H}(G))\) of \(\mathcal {H}(G)\) is called the clique-chromatic number of G, denoted by \(\chi _{C}(G)\). If \(\mathcal {H}(G)\) is k-colorable we say that G is k-clique-colorable. The k-clique coloring problem consists in deciding, for a given graph, if it admits a k-clique coloring.

Note that what we call k-clique-coloration here is also called weak k-coloring by Andreae et al. (1991), Bacsó and Zs (2009) or strong k-division by Hoàng and McDiarmid (2002). Clique-coloring has some similarities with usual vertex coloring, for example, any (vertex) k-coloring of G is also a k-clique-coloring of G, and optimal (vertex) colorings and clique-colorings coincide in the case of triangle-free graphs. But there are also essential differences, for example, a clique-coloring of a graph may not be a clique-coloring for its induced subgraphs. Induced subgraphs may even have a greater clique-chromatic number than the original graph. Let G be a graph with \(\chi _C(G)>2\) and \(G'\) be obtained from G by adding a vertex of full degree. Clearly, \(\chi (G')=2\) while \(\chi _C(G)>2\).

The clique-hypergraph coloring problem was posed by Duffus et al. (1991). Clique-coloring is harder than ordinary vertex coloring. Bacsó et al. (2004) proved that the decision problem of clique-coloring on general graphs is coNP-complete and it is NP-complete on graphs with maximum degree 3. Kratochvíl and Zs (2002) proved that testing \(\chi _{C}=2\) is still NP-hard for perfect graph and it is NP-complete on 3-chromatic perfect graphs. Défossez (2009) proved that testing \(\chi _{C}=2\) is \(\Sigma _{2}^{p}\)-complete on odd-hole-free graphs. In 2011, Marx (2011) proved that testing \(\chi _{C}=k\) is \(\Sigma _{2}^{p}\)-complete on general graphs.

Many classes of special graphs have been studied and turned out to have a bounded clique-chromatic number. Bacsó et al. (2004) proved that almost all perfect graphs are 3-clique-colorable. Défossez (2006) conjectured that every odd-hole-free graph is 3-clique-colorable. For several subclasses of odd-hole-free graphs, we have a positive answer. {Odd hole, claw}-free graphs in Bacsó et al. (2004), {odd hole, co-diamond}-free graphs in Défossez (2009), {odd hole, bull}-free graphs in Défossez (2006) and {odd hole, \(P_{5}\)}-free graphs in Défossez (2006) are 2-clique-colorable, and {diamond, odd hole}-free graphs in Défossez (2006) are all 4-clique-colorable. Furthermore, all planar graphs in Mohar and S̆ krekovski (1999), Circular-arc graphs in Cerioli and Korenchendler (2009) and UEH graphs in Cerioli and Priscila (2008) have been proved to be 3-clique-colorable. Claw-free planar graphs in Shan et al. (2014), planar graphs without maximal 2-cliques in Thomassen (2008), claw-free graphs of maximum degree at most four in Bacsó and Zs (2009) and powers of cycles in Campos et al. (2013), other than odd cycles longer than three, are 2-clique-colorable.

Circular-arc graphs are natural generalizations of interval graphs to the circle. They possess interesting structures (see, Durán et al. 2014; Tucker 1970). Some of the motivations for studying circular-arc graphs are their rich structure, in addition to their applications in cyclic scheduling problems, such as those that arise in traffic light scheduling, in assignment of variables to registers in loops, and in other areas (see Golumbic 2004; Roberts 1978).

Circular-arc graphs and interval graphs are frequently studied in algorithmic graph theory (see, Golumbic 2004). For the optimal clique-coloring problem on circular-arc graphs, Cerioli and Korenchendler (2009) provided a polynomial-time algorithm and they asked whether there exists a linear-time algorithm. In this paper we present a linear-time algorithm to find an optimal clique-coloring of circular-arc graphs.

2 Preliminaries

A circular-arc graph is the intersection graph of a set of arcs on a circle C. Formally, let \({\mathcal {A}}=\{I_{1},I_{2},\ldots ,I_{n}\}\) be a set of arcs on a circle C. Then the corresponding circular-arc graph is \( G = (V, E)\) where \(V=\{I_{1},I_{2},\ldots ,I_{n}\}\) and \(I_{i}I_{j}\in E\) if and only if \(I_{i}\cap I_{j}\ne \emptyset \). The set \({\mathcal {A}}\) of arcs is called circular-arc model of G. A family of sets S is said to satisfy the Helly property if every subfamily of it, consisting of pairwise intersecting sets, has a common element (Butzer et al. 1984). A Helly circular-arc (HCA) graph is a circular-arc graph admitting a circular-arc model whose arcs satisfy the Helly property.

Let \({\mathcal {A}}\) be an arc model of a circular-arc graph G. We say that each arc \(A_{i}=(s_{i},t_{i})\in {\mathcal {A}}\) traverses the circle C, in clockwise direction, from the point \(s_{i}\) to the point \(t_{i}\), called the extreme points of \(A_{i}\). We may assume, without loss of generality, that no two extreme points coincide. For \({{\mathcal {A}}'}\subset {\mathcal {A}}\), the arcs in \({{\mathcal {A}}'}\) are removable (or \({{\mathcal {A}}'}\) is a removable arc set) if there exists an arc \(A_{i}\in {\mathcal {A}}\setminus {{\mathcal {A}}'}\) satisfying the following conditions:

  1. (i)

    Every arc \(A'\in {{\mathcal {A}}'}\) is properly contained in \(A_{i}\).

  2. (ii)

    For every \(A\in {\mathcal {A}}\setminus ({{\mathcal {A}}'}\cup \{A_{i}\})\) and \(A'\in {{\mathcal {A}}'}\), \(A\cap A'=\emptyset \).

  3. (iii)

    The vertices corresponding to arcs in \({{\mathcal {A}}'}\) induce a connected graph.

Specially, if \({\mathcal {A}}\setminus {{\mathcal {A}}'}=\{A_{i}\}\), then the corresponding vertex of the arc \(A_{i}\) is a vertex of full degree and the circular-arc graph G is 2-clique-colorable and 2-connected. If \({\mathcal {A}}\setminus {{\mathcal {A}}'}\ne \{A_{i}\}\) and \({{\mathcal {A}}'}\) is a removable arc set, then the vertex \(v_{i}\) corresponding to the arc \(A_{i}\) is a cut vertex of G and \({{\mathcal {A}}'}\cup \{A_{i}\}\) induce a maximal 2-connected subgraph of G. Note that, given a cut vertex \(v_{i}\) and a maximal 2-connected subgraph \(G'\) including \(v_{i}\), we can easily check that whether the arc set corresponding to \(G'-v_i\) is a removable arc set in \(O(|V(G'-v_{i})|)\) time. If an arc model \( {\mathcal {A}}\) has no removable arc set, we call \({\mathcal {A}}\) an irreducible arc model and the corresponding circular-arc graph G of \( {\mathcal {A}}\) is an irreducible circular-arc graph. Note that all the cut vertices and maximal 2-connected subgraphs of a circular-arc graph can be listed in linear time (see, Hopcroft and Tarjan 1973), so we immediately have the following result.

Lemma 2.1

Given an arc model \({\mathcal {A}}\) and the corresponding circular-arc graph G of \( {\mathcal {A}}\), we can get the irreducible arc model \({{\mathcal {A}}^{*}}\) of \({\mathcal {A}}\) in linear time.

A simplicial vertex of a graph G is a vertex whose neighbors induce a clique. A simplicial order of G is an enumeration \(v_1, v_2, \ldots , v_n\) of its vertices such that \(v_i\) is a simplicial vertex of induced subgraph \(G[\{v_i, v_{i+1}, \ldots , v_n\}]\), \(1\le i\le n\). In other words, each set \(X_{i}=\{v_{j}\in N[v_{i}]:\, j>i\}\) induce a clique. A chordal graph is a simple graph in which every cycle of length greater than three has a chord. Equivalently, the graph contains no induced cycle of length four or more. For chordal graphs, we have the following lemma.

Lemma 2.2

(Bondy and Murty 2008; Rose et al. 1976) A graph is chordal if and only if it has a simplicial order.

There is a linear-time algorithm due to Rose et al. (1976), and known as lexicographic breadth-first search, for finding a simplicial order of a graph if one exists. In this algorithm, a simplicial order of a graph G is found if G is recognized to be chordal; otherwise an induced cycle of length four or more is found. By using the algorithm, we can easily give a 2-clique-coloring of chordal graphs as follows.

Algorithm 1

Find a 2-clique-coloring of a chordal graph.

Input. A chordal graph \(G=(V,E)\).

Output. A 2-clique-coloring \(\phi : V\rightarrow \{1,2\}\) of G.

Step 1: Give a simplicial order \(\sigma =\{v_{1},v_{2},\cdots ,v_{n}\}\) of G by running the algorithm ‘lexicographic breadth-first search’.

Step 2: Set \(S:=\emptyset \), \(i:=n\).

Step 3: If \(i=0\), then turn to Step 4 directly. Otherwise, let \(X_{i}:=\{v_{j}\in N[v_{i}]:\, j\ge i\}\). If \(X_i\cap S=\emptyset \), then set \(S:=S\cup \{v_{i}\}\); if not, set \(S:=S\). Set \(i:=i-1\), turn to Step 3 again.

Step 4: For every \(v\in S\), let \(\phi (v)=1\). For every \(v\in V-S\), let \(\phi (v)=2\). Stop.

Theorem 2.1

Algorithm 1 gives a 2-clique-coloring of a chordal graph G in linear time \(O(n+m)\).

Proof

We first show, by induction on |V(G)|, that the set S in the end of Algorithm 1 is an independent set of G and it contains one vertex of every maximal clique of G. This is clearly true if \(|V(G)|\le 2\). Suppose, then, that \(|V(G)|=n\ge 3\). By Lemma 2.2, G has a simplicial order. Let \(\sigma =\{v_{1},v_{2},\ldots ,v_{n}\}\) be a simplicial order of G. Then clearly \(\sigma '=\{v_{2},\ldots ,v_{n}\}\) is also a simplicial order of \(G'=G-v_{1}\). Note that, when \(i=2\) and Step 3 is carried out, the set S is the set \(S'\) obtained by Algorithm 1 for \(G'\). By the inductive hypothesis, \(S'\) is an independent set of \(G'\) and includes one vertex of every maximal clique of \(G'\). Note that when \(i=1\) and Step 3 is carried, the set S equals either \(S'\) or \(S'\cup \{v_{1}\}\). By Step 3, it is easy to see that S is an independent set, and all maximal cliques of G except the maximal clique \(G[N[v_{1}]]\) are also maximal cliques of \(G'\). This implies that S contains exactly one vertex of every maximal clique of G.

By Step 4, we see that \(\phi \) is a 2-clique-coloring of G. In step 1 the time is \(O(n+m)\) by the algorithm ‘lexicographic breadth-first search’. Obviously, it needs O(m) in step 3 and O(n) in step 4. So the running time of Algorithm 1 is \(O(n+m)\). \(\square \)

By Theorem 2.1, we have the following result on the optimal clique-coloring of circular-arc graphs.

Lemma 2.3

Let G be a circular-arc graph with arc model \({\mathcal {A}}\) and \({{\mathcal {A}}'}\) a removable arc set of \({\mathcal {A}}\). Let \(G'\) and H be the circular-arc graphs whose arc models are \({\mathcal {A}}\setminus {{\mathcal {A}}'}\) and \({{\mathcal {A}}'}\cup \{A_i\}\), respectively, where \(A_i\) is the arc in the definition of the removable set. Then \(\chi _{C}(G)=\chi _{C}(G')\), and we can obtain an optimal clique-coloring of G in \(O(n_1+m_1)\) time from any given optimal clique-coloring of \(G'\), where \(n_1=|V(H)|\) and \(m_1=|E(H)|\).

Proof

Since \({{\mathcal {A}}'}\) is a removable arc set, the graph H is an interval graph. Note that an interval graph is also a chordal graph. By Theorem 2.1, we can give a 2-clique-coloring of H in \(O(n_1+m_1)\), where \(n_1=|V(H)|\) and \(m_1=|E(H)|\). Obviously, a maximal clique of \(G'\) is also a maximal clique of G, so \(\chi _{C}(G)\ge \chi _{C}(G')\). Let \(\phi '\) be a \(\chi _{C}(G')\)-clique-coloring of \(G'\) and \(\phi ''\) be a 2-clique-coloring of H. Let v be the vertex corresponding to the arc \(A_i\). As mentioned earlier, v is a cut vertex of G. Without loss of generality, we may assume that \(\phi ''(v)=\phi '(v)\). Hence \(\phi '\cup \phi ''\) is a \(\chi _{C}(G')\)-clique-coloring of G. Thus \(\chi _{C}(G)=\chi _{C}(G')\) and, if given an optimal clique-coloring of \(G'\), we can obtain an optimal clique-coloring of G in \(O(n_1+m_1)\) time. \(\square \)

By Lemmas 2.1 and 2.3, we have the following result on optimal clique-coloring of circular-arc graphs.

Theorem 2.2

Let \({\mathcal {A}}\) be the arc model of a circular-arc graph G and \({{{\mathcal {A}}}^*}\) be the arc model of the irreducible circular-arc graph \(G^*\) from G. Given an optimal clique-coloring of \(G^*\), we can obtain an optimal clique-coloring of G in linear time.

3 The optimal clique-coloring of circular-arc graphs

For Helly circular-arc graphs, Cerioli and Korenchendler (2009) obtained the following result.

Theorem 3.1

(Cerioli and Korenchendler 2009) For an irreducible Helly circular-arc graph G, \(\chi _{C}(G)=2 \) if and only if G is not an odd cycle of length at least 5.

By using the ideas involved in the proof of Theorem 3.1, we can get an optimal clique-coloring of an irreducible Helly circular-arc graph G in linear time.

Theorem 3.2

If G is an irreducible Helly circular-arc graph, then we can give an optimal clique-coloring of G in linear time.

Proof

First we can easily decide whether G is an odd cycle of length at least 5 in linear time. If it is, then clearly \(\chi _{C}(G)=3\) and we can give a 3-clique-coloring of G in linear time. If not, then by using the algorithm ‘lexicographic breadth-first search’ in Rose et al. (1976), we decide whether G is a chordal graph, which needs linear time. If G is a chordal graph, then \(\chi _{C}(G)=2\) and we can give an optimal clique-coloring of G by using Algorithm 1. Otherwise, we can get a hole \(C_{k}\) (\(k\ge 4\)) (see Bondy and Murty 2008; Rose et al. 1976). Since \(C_{k}\) is an induced cycle, the arcs corresponding to the vertices of \(C_{k}\) cover the whole circle. Note that, if an edge \(e=v_{i}v_{j}\) is a maximal 2-clique, this edge must be on the cycle \(C_{k}\) by the Helly-property of G. This implies that we can easily check whether G has no maximal 2-cliques in linear time. We consider the following two cases.

Case 1 G has no maximal 2-clique. In this case, every maximal clique has size at least 3. By the Helly-property of G, every maximal clique of G contains at least one vertex of \(C_{k}\) and one vertex of \(V\setminus C_{k}\). Hence we can obtain a 2-clique-coloring of G by simply coloring the vertices on \(C_{k}\) with color 1 and the others with color 2. Clearly, the running time is linear.

Case 2 G has maximal 2-cliques. As mentioned above, every maximal 2-clique of G is on \(C_{k}\). Let \(\mathcal {P}=\{P_{1},P_{2},\ldots , P_{p}\}\) be the set of all maximal paths of G such that every edge in these paths is a maximal clique of G and \(Q=\{Q_{1},Q_{2},\ldots , Q_{q}\}\) be the set of all connected components of the subgraph induced by \(E(G)-\{e: e \, \, \text{ is } \text{ a } \text{ maximal } \text{2-clique } \text{ in } G\}\). Then each \(Q_{i}\) in Q is an interval graph. Note that some component \(Q_{i}\) may consist of only one vertex. If \(Q_i\) consists of an isolated vertex, we don’t need to consider the clique-coloring of \(Q_{i}\). If \(Q_{i}\) has at least two vertices, then every maximal clique of \(Q_{i}\) is also a maximal clique of G. Moreover, every maximal clique of \(Q_{i}\) has more than two vertices, and at least one of them is a vertex of \(C_k\).

Denote by \(v_{i}'\) and \(v_{i}''\) the two vertices whose corresponding arcs have the smallest starting extreme point and maximum ending extreme point, respectively, among those arcs corresponding to vertices of \(Q_{i}\). Since G is an irreducible circular-arc graph, \(v_i'\) and \(v_i''\) are different and are vertices on \(C_k\).

Now we can give two 2-clique-colorings \(f_{1}\) and \(f_{2}\) of \(Q_{i}\) such that \(f_{1}(v_{i}')=f_{1}(v_{i}'')\) and \(f_{2}(v_{i}')\ne f_{2}(v_{i}'')\). For the first case, assign color 1 to the vertices of \(Q_{i} \cap C_{k} \) and color 2 to the others. Note that every maximal clique of \(Q_{i}\) contains at least three vertices and has at least a vertex is not on \(C_k\), so no maximal clique of \(Q_{i}\) will be monochromatic. To obtain a color \(f_{2}\), just assign the color 1 to vertices in \(V(Q_{i})\cap (V(C_{k})\setminus \{v_{i}''\})\) and to vertices in \(V(Q_{i})\setminus V(C_{k})\) whose only neighbor on \(C_{k}\) is \(v_{i}''\) (maybe there is no such a vertex); the other vertices should be colored with color 2. It is not hard to show that no maximal clique of \(Q_{i}\) is monochromatic.

Now we give a 2-clique-coloring f of G as follows. First, color the paths in \(\mathcal {P}=\{P_{1},P_{2},\ldots , P_{p}\}\) such that each maximal 2-clique has two colors. Then the two vertices \(v_{i}'\) and \(v_{i}''\) of each \(Q_{i}\) have been colored. According to the colors of \(v_{i}'\) and \(v_{i}''\), we give a 2-clique-colorings \(f_{1}\) or \(f_{2}\) of each \(Q_{i}\) as above. So we get a 2-clique-coloring of G.

Note that coloring all paths in \(\mathcal {P}\) needs at most O(n). In addition, the time of coloring each \(Q_{i}\) is \(O(|Q_{i}|)\), thus the total time of coloring all \(Q_{i}\)’s is also O(n). Hence the running time is linear. \(\square \)

By Algorithm 1 and Theorem 3.2, we get the following algorithm in linear time for the optimal clique-coloring of irreducible Helly circular-arc graphs.

Next we assume that, a circle and the set of arcs with given extreme points for circular-arc graphs are given explicitly as part of the input in the following algorithms.

Algorithm 2

The optimal clique-coloring of an irreducible Helly circular-arc graph.

Input. An irreducible Helly circular-arc graph \(G=(V,E)\) and an arc model of G.

Output. A k-clique-coloring, where \(k=\chi _{C}(G)\).

Step 1: If G is a odd cycle of order at least 5, give a 3-clique-coloring of G directly, stop. If not, turn to Step 2.

Step 2: Check whether G is a chordal graph by using ‘lexicographic breadth-first search’. If G is a chordal graph, then perform Algorithm 1 on G, stop. If not, then we get a hole \(C_{k}\) (\(k\ge 4\)), turn to Step 3.

Step 3: If every edge of \(C_{k}\) lies in a triangle of G (i.e., G has no maximal 2-clique), then give a 2-clique-coloring of G by using the method in Case 1 of Theorem 3.2, stop. If not, then find out \(\mathcal {P}=\{P_{1},P_{2},\ldots , P_{p}\}\), \(Q=\{Q_{1},Q_{2},\ldots , Q_{q}\}\) and, \(v_{i}'\) and \(v_{i}''\) for each \(Q_{i}\) (see Case 2 in Theorem 3.2), turn to Step 4.

Step 4: Give a 2-coloring of each path \(P_i\). According to the colors of \(v_{i}'\) and \(v_{i}''\), further give a 2-clique-coloring of each \(Q_{i}\), stop.

A circular-arc graph G is called a non-Helly circular-arc graph if G has no model with the Helly property.

Lemma 3.1

(Joeris et al. 2011) If G is a non-Helly circular-arc graph with arc model \({\mathcal {A}}\), then \({\mathcal {A}}\) contains two or three arcs that cover the whole circle C.

Theorem 3.3

If G is a non-Helly circular-arc graph, then we can give a 2-clique-coloring of G in linear time.

Proof

Let \({\mathcal {A}}\) be the arc model of G. By Lemma 3.1, \({\mathcal {A}}\) contains either two or three arcs that cover the whole circle C. We first check whether or not \({\mathcal {A}}\) contains two arcs that cover the whole circle C in at most O(m) time, where \(m=|E(G)|\).

If we find two arcs \(A_{i}\) and \(A_{j}\) of \({\mathcal {A}}\) that cover the whole circle C, let \(v_{i}\) and \(v_{j}\) be the vertices corresponding to \(A_{i}\) and \(A_{j}\), respectively. Clearly \(v_{i}v_{j}\in E(G)\) and \(N(v_{i})\cup N(v_{j})=V(G)\). We now give a 2-clique-coloring of G by assigning color 1 to the vertices of \(N(v_{i})\) and color 2 to all the other vertices of G in time O(n).

If there exist no such two arcs above, then \({\mathcal {A}}\) must contain three arcs \(A_{i},A_{j}, A_k\) that cover the whole circle by Lemma . Joeris et al. (2011) provided a recognition algorithm with complexity O(m) for HCA graphs. This algorithm can search directly for the existence of such three arcs in time O(m). (see p. 223). By using the algorithm, we find three arcs \(A_{i},A_{j}, A_k\in {\mathcal {A}}\) which cover the whole circle. Let \(v_{i}\), \(v_{j}\) and \(v_{k}\) be the three vertices of G corresponding to the three arcs \(A_{i},A_{j}\), and \(A_k\). Obviously, every vertex of \(V(G)\setminus \{v_{i}, v_{j}, v_{k}\}\) is adjacent to at least one of \(\{v_{i}, v_{j}, v_{k}\}\). We obtain a 2-clique-coloring of G in time O(n) as follows. Assign color 1 to v if \(v=v_{i}\), \(v=v_{j}\), \(v\in N(v_{k})\setminus (N(v_{i})\cup N(v_{j}))\) or \(v\in (N(v_{k})\cap (N(v_{i}))\setminus N(v_{j})\) and color 2 to the others. We claim that every maximal clique is not monochromatic. Let \(V_{1}=N(v_{k})\setminus (N(v_{i})\cup N(v_{j}))\), \(V_{2}=(N(v_{k})\cap (N(v_{i}))\setminus N(v_{j})\), \(V_{3}= N(v_{i})\cap N(v_{j})\), \(V_{4}= N(v_{i})\setminus (N(v_{j})\cup N(v_{k}))\) and \(V_{5}= N(v_{j})\setminus N(v_{i})\). According to our coloring, the vertices with color 2 are in \(V_3\cup V_4\cup V_5\). Suppose that S is an arbitrary monochromatic clique of G. If S has color 1, then we have that \(V(S)\subseteq V_{1}\cup V_{2}\), \(V(S)\subseteq V_{2}\cup \{v_{i}\}\) or \(V(S)=\{v_{i},v_{j}\}\). Hence \(S\cup \{v_{k}\}\) induces a bigger clique than S, but \(v_{k}\) is assigned color 2. If S has color 2, then we have that \(V(S)\subseteq V_{3}\cup V_{4}\) or \(V(S)\subseteq V_{5}\cup \{v_{k}\}\). But \(V(S)\cup \{v_{i}\}\) or \(V(S)\cup \{v_{j}\}\) will induce a bigger clique than S, while both \(v_i\) and \(v_j\) have color 1. Hence, no monochromatic clique is maximal, as claimed. \(\square \)

Finally, we obtain an algorithm for the optimal clique-coloring of circular-arc graphs.

Algorithm 3

The optimal clique-coloring of circular-arc graphs.

Input. A circular-arc graph \(G=(V,E)\) and its arc model \({\mathcal {A}}\).

Output. A k-clique-coloring, where \(k=\chi _{C}(G)\).

Step 1: Find out all the removable arc sets of \({\mathcal {A}}\) and, give the irreducible arc model \({{{\mathcal {A}}}^*}\) and irreducible circular-arc graph \(G^*\) with arc model \({{{\mathcal {A}}}^*}\).

Step 2: Recognize whether \(G^*\) is a Helly circular-arc graph (see Joeris et al. 2011). If it is, then perform Algorithm 2 for \(G^*\). If not, then give a 2-clique-coloring of G by using the method in Theorem 3.3.

Step 3: Extend the optimal clique-coloring of \(G^*\) into an optimal clique-coloring of G by using Lemma 2.3 and Theorem 2.2.

Theorem 3.4

Algorithm 3 gives an optimal clique-coloring of G in linear time.

Proof

By Theorems 2.2, 3.2 and 3.3, Algorithm 3 give an optimal clique-coloring of G. By Lemma 2.1, the time is linear in Step 1. By Theorems 3.2 and 3.3, the time of Step 2 is linear. By Theorem 2.2, the time of Step 3 is also linear. Thus Algorithm 3 runs in linear time. \(\square \)