1 Introduction

All graphs considered here are finite, simple and nonempty. Let \(G=(V,E)\) be a graph with vertex set V and edge set E. For a vertex \(v\in V\), the open neighborhood N(v) of v is defined as the set of vertices adjacent to v, i.e., \(N(v) = \{u\mid uv\in E\}\). The degree of v is equal to |N(v)|, denoted by \(d_G(v)\) or simply d(v). By \(\delta (G)\) and \(\varDelta (G)\), we denote the minimum degree and the maximum degree of the graph G respectively. For a subset \(S\subseteq V\), the subgraph of G induced by S is denoted by G[S].

A clique of a graph G is a set of pairwise adjacent vertices of G. A clique on m vertices is called an m-clique of G. To simplify notation, we often denote a clique \(\{v_{1},v_{2},..., v_{m}\}\) simply by \([v_{1}v_{2}...v_{m}]\). A clique-coloring, also called weak coloring in the literature, of G is an assignment of colors to the vertices of G in such a way that no inclusion-wise maximal clique of size at least two of G is monochromatic. A k-clique-coloring of G is a clique-coloring \(\varphi\): \(V \rightarrow \{1,2,\ldots ,k\}\) of G. If G has a k-clique-coloring, we say that G is k-clique-colorable. The clique-chromatic number of G, denoted by \(\chi _{C}(G)\), is the smallest integer k such that G is k-clique-colorable. Clearly, every proper vertex coloring of G is also a clique-coloring, and so \(\chi _{C}(G)\le \chi (G)\). Furthermore, if a graph G is triangle-free, then clique-colorings of G coincide with proper vertex colorings of G. This implies that there are triangle-free graphs of arbitrarily large clique-chromatic number since there are triangle-free graphs of arbitrarily large chromatic number [12]. In general, clique-coloring can be a very different problem from ordinary vertex coloring. The most notable difference is that clique-coloring is not a hereditary property: it is possible that a graph is k-clique-colorable, but has an induced subgraph that is not [1]. For example, let G be a graph with \(\chi _C(G)>2\) and \(G'\) be obtained from G by adding a vertex adjacent to all vertices of G. Clearly, \(\chi (G')=2\) while \(\chi _C(G)>2\). Another difference is that a large clique is not an obstruction for k-clique-colorability: even 2-clique-colorable graphs can contain arbitrarily large cliques. For example, a complete graph is 2-clique-colorable. Determining \(\chi _{C}(G)\) is hard: to decide if \(\chi _{C}=2\) is NP-complete on 3-chromatic perfect graphs [16], graphs with maximum degree 3 [1] and even (\(K_{4}\), diamond)-free perfect graphs [8]. Clique-coloring has received considerable attention ( [4,5,6, 9, 11, 17,18,19,20,21,22]).

An equitable vertex-coloring of G is a proper vertex-coloring such that any two color classes differ in size by at most one. Equitable vertex-coloring of graphs is widely researched in the literature [7, 10, 13,14,15]. An equitable clique-coloring of G is a clique-coloring such that any two color classes differ in size by at most one. If G has an equitable clique-coloring with k colors, we say that G is equitably k-clique-colorable. Note that if a graph G is triangle-free, then equitable clique-colorings of G coincide with equitable proper vertex colorings of G. Equitable clique-coloring of graphs can also be considered an example of the equitable coloring of hypergraphs proposed by Berge [3].

Note that, if G is 2-clique-colorable, it is not necessarily equitably 2-clique-colorable. For example, the star graph \(K_{1,k}\) (\(k\ge 3\)) is 2-clique-colorable while it has no equitable 2-clique-coloring. Bacsó and Tuza proved that every connected claw-free graph with maximum degree at most four, other than an odd cycle of order greater than three, is 2-clique-colorable and a 2-clique-coloring can be found in \(O(n^{2})\) time [2]. In this paper we prove that every connected claw-free graph with maximum degree at most four, other than an odd cycle greater than three, is also equitably 2-clique-colorable. In addition we improve the algorithm from [2] by giving an equitable 2-clique-coloring in linear time for this class of graphs.

2 Results and Proofs

In this section, we discuss equitable clique-coloring in claw-free graphs with maximum degree at most 4. Given a graph F, a graph G is said to be F-free if no induced subgraph of G is isomorphic to F. The claw is the complete bipartite graph \(K_{1,3}\) and the diamond is the graph obtained from the complete graph \(K_{4}\) by deleting one edge. First, for claw-free and diamond-free graphs, we have the following lemma.

Lemma 1

Let G be a (claw, diamond)-free graph, none of whose components is an odd cycle of length greater than three. Then G is equitably 2-clique-colorable.

Proof

We prove the lemma by induction on the order n of G. If G has at most three vertices, the lemma is trivial. Now, fix \(n \ge 4\), and assume inductively that the lemma holds for graphs of order less than n. In the following, we will prove that G is equitably 2-clique-colorable when the order of G is n. Suppose first that G is disconnected. By the induction hypothesis, we can equitably clique-color each component of G with colors r and g. After possibly permuting colors, we can obtain an equitable clique-coloring of G. From now on, we assume that G is connected. Let v be an arbitrary vertex of G. We have the following claims.

Claim 1

There are at most two maximal cliques containing v and any two maximal cliques of G have at most one common vertex. We prove Claim 1 as follows. Since G is connected and has at least four vertices, we know that \(N(v)\ne \emptyset\). Since G is diamond-free, G[N(v)] is \(P_{3}\)-free, and it follows that N(v) can be partitioned into (non-empty) cliques, with no edges between any two of them. Since G is claw-free, the number of such cliques is at most two. Thus, there are at most two maximal cliques containing v, and if there are exactly two such cliques, they have just one vertex (namely v) in common. This proves Claim 1.

By Claim 1, we immediately get the following claim.

Claim 2

If C is an induced cycle of length greater than three in G, and \(x\in V(G)\setminus V(C)\) has a neighbor in V(C), then \(G[N(x)\cap V(C)]\) is isomorphic to either \(K_{2}\) or disconnected \(2K_{2}\).

Claim 3

If \(G-v\) has an odd cycle of order greater than three as a component, then G has an equitable 2-clique-coloring. We prove Claim 3 as follows. Since G is connected, Claim 1 guarantees that \(G-v\) has at most two components. Let \(C=u_{1}u_{2}...u_{j}u_{1}\) be a component of \(G-v\) that is an odd cycle of order greater than three. If C is the unique component, then \(G=G[V(C)\cup \{v\}]\) and we can easily give an equitable 2-clique-coloring of G directly. If C is not the unique component, \(G[N(v)\cap V(C)]\) is isomorphic to \(K_{2}\). Suppose not, by Claim 2, \(G[N(v)\cap V(C)]\) is isomorphic to disconnected \(2K_{2}\) and there are already two maximal 3-cliques containing v. Then C would be the unique component, a contradiction. Further, by Claim 1, there exists exactly one maximal clique K containing v in G such that \(K\cap V(C)=\emptyset\) since C is not the unique component. If \(G-C-v\) is also an odd cycle of order greater than three, by Claim 2, K is also a maximal 3-clique and we can easily give an equitable 2-clique-coloring of G directly. If not, by induction, \(G-C-v\) has an equitable 2-clique-coloring \(\phi : V(G-C-v) \rightarrow \{r,g\}\). Let \(V_{r}\) and \(V_{g}\) be the two color classes with r and g respectively. By symmetry, assume that \(N(v)\cap V(C)=\{u_{1}, u_{j}\}\). We can get an equitable 2-clique-coloring of G by assigning v a different color from one vertex in \(K-v\) ( assume that \(\phi (v)=r\)), \(\phi (u_{i})=g\) (if i is odd) and \(\phi (u_{i})=r\) (if i is even). This proves Claim 3.

If there is no maximal 2-clique containing v, then by Claim 1, for every maximal clique K of G through v, \(K-v\) is a maximal clique of size at least two in \(G-v\). If \(G-v\) has an odd cycle of order greater than three as a component, then, by Claim 3, G has an equitable 2-clique-coloring. If not, by the induction hypothesis, \(G-v\) has an equitable 2-clique-coloring \(\phi : V-v \rightarrow \{r,g\}\). Let \(V_{r}=\{x\mid \phi (x)=r\}\) and \(V_{g}=\{x\mid \phi (x)=g\}\). Assume by symmetry that \(|V_{g}|\le |V_{r}|\le |V_{g}|+1\). We can get an equitable 2-clique-coloring by assigning \(\phi (v)=g\).

If there is a maximal 2-clique containing v, let \(P=u_{1}u_{2}...u_{j}\) be a maximal path (not necessarily induced) containing v such that every edge on the path forms a maximal 2-clique of G. By Claim 1, we have that \(d(u_{i})=2\) when \(1<i<j\). Obviously, \(d(u_{1})\ge 1\) and \(d(u_{j})\ge 1\). If \(d(u_{1})=d(u_{j})=1\), then \(G=P\) and we can give an equitable 2-clique-coloring of G directly. Suppose now that \(d(u_{1})=1\) and \(d(u_{j})\ge 2\). Then the maximality of P guarantees that \(d(u_{j})\ge 3\). If \(G-u_{j}\) has an odd cycle of order greater than three as a component, by Claim 3, G has an equitable 2-clique-coloring. If \(G-u_{j}\) has no odd cycle of order greater than three as a component, then by induction the component \(G-P\) has an equitable 2-clique-coloring. Note that \(N(u_{j})-V(P)\) is a maximal clique of \(G-P\) by Claim 1 and the fact \(d(u_{j})\ge 3\). Then \(N(u_{j})-V(P)\) is not colored monochromatically in the equitable 2-clique-coloring of \(G-P\). Hence, we can easily give an equitable 2-clique-coloring of G from the equitable 2-clique-coloring of \(G-P\). So we may assume that \(d(u_{1})\ge 2\) and \(d(u_{j})\ge 2\) in the following.

If P is not an induced path in G, then \(u_{1}\) is adjacent to \(u_{j}\) and, by Claim 1, G itself is an even cycle or both \(u_{1}\) and \(u_{j}\) are in a clique of order at least three. If G is an even cycle, obviously, G is equitably 2-clique-colorable.

If both \(u_{1}\) and \(u_{j}\) are in a clique K of order at least three and \(C=u_{1}u_{2}...u_{j}u_{1}\) is an odd cycle, let t be a vertex in \(K-u_{1}-u_{j}\) and \(K'\) be the other maximal clique containing t in G (if such a \(K'\) exists). At this time, we assume that \(G-t\) has no odd cycle of order greater than three as a component by Claim 3. We consider the graph \(G-C-t\). If \(G-C-t\) has an odd cycle \(C'\) of order greater than three as a component, we claim that K is a clique of order five as follows. Obviously, \(\{t, u_{1}, u_{j}\}\subseteq K\). If \(K=\{t, u_{1}, u_{j}\}\), then \(C'\) is also a component of \(G-t\), a contradiction to our assumption. If K is a clique of order four (assume that \(K=[tu_{1}u_{j}p]\)), then \(K \cap V(C')=\{p\}\). A claw would occur at p, a contradiction. If K is a clique of order no less than six, then one component of \(G-C-t\) contains a triangle of K. Thus \(C'\) must be a component of \(G-t\) since \(G-C-t\) has at most two components by Claim 1, a contradiction to our assumption. So K is a clique of order five (assume that \(K=[tu_{1}u_{j}pq]\)) and pq is an edge of \(C'\). Then \(G[V(C)\cup V(C')]\) is a component of \(G-t\). In this case, we can easily get an equitable 2-clique-coloring of G from the equitable 2-clique-coloring of \(G-t\). So we may assume that \(G-C-t\) has no odd cycle of order greater than three as a component. By induction, \(G-C-t\) has an equitable 2-clique-coloring. Let \(\phi : V(G)-V(C)-t \rightarrow \{r,g\}\) be an equitable 2-clique-coloring of \(G-C-t\). Let \(V_{r}=\{x\mid \phi (x)=r\}\) and \(V_{g}=\{x\mid \phi (x)=g\}\). No matter \(|V_{r}|=|V_{g}|\) or not, we can get an equitable 2-clique-coloring of G by assigning t a color different from one vertex in \(K'-t\), \(\phi (u_{i})\ne \phi (t)\) (if i is odd) and \(\phi (u_{i})=\phi (t)\) (if i is even).

If both \(u_{1}\) and \(u_{j}\) are in a clique K of order at least three and \(C=u_{1}u_{2}...u_{j}u_{1}\) is an even cycle, we consider the graph \(G-C\). If \(G-C\) is an odd cycle \(C'\) of order greater than three, then K is a clique of order four as follows. If K is a clique of order three (assume that \(K=[tu_{1}u_{j}]\)), then \(K \cap V(C')=\{t\}\). A claw would occur at t, a contradiction. If K is a clique of order no less than five, then \(G-C\) contains a triangle of K and thus has no odd cycle of order greater than three as a component since \(G-C\) is connected by Claim 1. So K is a clique of order four (assume that \(K=[u_{1}u_{j}pq]\)) and pq is an edge of \(C'\). Then \(G=G[V(C)\cup V(C')]\) and we can give an equitable 2-clique-coloring of G directly. If \(G-C\) is not an odd cycle \(C'\) of order greater than three, we can easily get an equitable 2-clique-coloring of G from the equitable 2-clique-coloring of \(G-C\).

If P is an induced path in G, let \(K_{1}\) be the other maximal clique containing \(u_{1}\) such that the order of \(K_{1}\) is at least three and \(K_{2}\) be the other maximal clique containing \(u_{j}\) such that the order of \(K_{2}\) is at least three. Both \(K_{1}\) and \(K_{2}\) exist by our assumption that \(d(u_{1})\ge 2\) and \(d(u_{j})\ge 2\). We consider the graph \(G-V(P)\). If \(G-V(P)\) has a component isomorphic to an odd cycle \(C=h_{1}h_{2}...h_{m}h_{1}\) of order greater than three, obviously, the neighbors of C are in \(\{u_{1},u_{j}\}\). Not losing the generality, assume that \(h_{1}\) is adjacent to \(u_{1}\). Then we have that \(h_{1}\in K_{1}\) and \(K_{1}\) is a maximal clique of order three by Claim 2 (assume that \(K_{1}=[h_{1}h_{m}u_{1}]\)). If \(u_{1}\) is the unique neighbor of C, then C is also a component of \(G-u_{1}\). By Claim 3, G has an equitable 2-clique-coloring. If \(u_{j}\) is also a neighbor of C, then \(K_{2}\) is also a maximal clique of order three. Then \(G=G[V(C)\cup V(P)]\) and we can give an equitable 2-clique-coloring of G directly. If \(G-V(P)\) has no component isomorphic to an odd cycle of order greater than three, by induction, \(G-V(P)\) has an equitable 2-clique-coloring \(\phi : V-V(P) \rightarrow \{r,g\}\). Let \(V_{r}=\{x\mid \phi (x)=r\}\) and \(V_{g}=\{x\mid \phi (x)=g\}\). Not losing the generality, we may assume that \(|V_{r}| \le |V_{g}|\le |V_{r}|+1\). Note that both \(K_{1}-u_{1}\) and \(K_{2}-u_{j}\) are maximal cliques of size at least two in \(G-V(P)\) by Claim 1. Then we can get an equitable 2-clique-coloring of G from \(\phi\) by assigning \(\phi (u_{i})=r\) if i is odd and \(\phi (u_{i})=g\) if i is even. \(\square\)

Remark

Based on the proofs of Lemma 1, we can easily design an algorithm in linear time for the equitable 2-clique-coloring in (claw, diamond)-free graphs with maximum degree at most 4, none of whose components is an odd cycle of length greater than three.

Theorem 2

Every claw-free graph with maximum degree at most four, none of whose components is an odd cycle of length greater than three, is equitably 2-clique-colorable.

Proof

We prove the theorem by the induction on the order of G. If G has at most three vertices, the theorem is trivial. Now fix \(n\ge 4\) and assume inductively that the theorem holds for graphs of order less than n. In the following, we will prove that G is equitably 2-clique-colorable when the order of G is n. Suppose first that G is disconnected. We then equitably clique-color each component of G with colors r and g. After possibly permuting colors, we can obtain an equitable clique-coloring of G. From now on, we assume that G is connected. If G has no diamond as an induced subgraph, then G is equitably 2-clique-colorable by Lemma 1. If not, let D be a diamond with vertex set \(\{c_{1},c_{2},f_{1},f_{2}\}\), where the only non-edge is \(f_{1}f_{2}\). By symmetry, we give an equitable 2-clique-coloring in the following cases.

Case 1: \(d(c_{1})=d(c_{2})=3\).

Then \([c_{1}c_{2}f_{1}]\) and \([c_{1}c_{2}f_{2}]\) are maximal 3-cliques of G. Consider the graph \(G'=G-c_{1}-c_{2}\). We can easily see that the maximal cliques of size at least two of \(G'\) are also maximal cliques of G. Furthermore, since G is claw-free, no component of \(G'\) is a cycle of length greater than three. By induction, \(G'\) has an equitable 2-clique-coloring \(\phi\) with two colors r and g. We can easily get an equitable 2-clique-coloring of G from \(\phi\) together with \(\phi (c_{1})=r\) and \(\phi (c_{2})=g\).

Case 2: \(d(c_{1})=3\) and \(d(c_{2})=4\).

Let \(f_{3}\) be the fourth neighbor of \(c_{2}\). By the claw-freeness of G, \(f_{3}\) is adjacent to \(f_{1}\) or \(f_{2}\). If \(f_{3}\) is adjacent to both \(f_{1}\) and \(f_{2}\), we consider \(d(f_{3})\). If \(d(f_{3})=3\), by the claw-freeness, G is a 4-wheel and G is equitably 2-clique-colorable. If \(d(f_{3})=4\), let \(f_{4}\) be the fourth neighbor of \(f_{3}\). Since G is claw-free, \(f_{4}\) is adjacent to at least one of \(f_{1}\), \(f_{2}\). If \(f_{4}\) is adjacent to both \(f_{1}\) and \(f_{2}\), G is graph with six vertices and G is equitably 2-clique-colorable. If not, assume that \(f_{4}\) is adjacent to \(f_{2}\) and non-adjacent to \(f_{1}\). Then, since G is claw-free and satisfies \(\Delta (G)\le 4\), the degree of \(f_{1}\) is 3. Let \(G'=G-\{c_{1},c_{2},f_{1}\}\). Then \(G'\) is connected and not an odd cycle of order greater than three. By induction \(G'\) has an equitable 2-clique-coloring \(\phi\) with two colors r and g. Let \(V_{r}=\{x\mid \phi (x)=r\}\) and \(V_{g}=\{x\mid \phi (x)=g\}\). Assume by symmetry that \(|V_{g}|\le |V_{r}|\le |V_{g}|+1\). We can get an equitable 2-clique-coloring by considering \(\phi (f_{2})\) and \(\phi (f_{3})\). If \(\phi (f_{2})=\phi (f_{3})=r\), we can get an equitable 2-clique-coloring by assigning \(\phi (c_{2})=\phi (c_{1})=g\) and \(\phi (f_{1})= r\). If \(\phi (f_{2})=\phi (f_{3})=g\) or \(\phi (f_{2})\ne \phi (f_{3})\), we can get an equitable 2-clique-coloring by assigning \(\phi (c_{2})=r\) and \(\phi (f_{1})=\phi (c_{1})=g\).

If \(f_{3}\) is not adjacent to \(f_{1}\), then \(f_{3}\) is adjacent to \(f_{2}\). In addition, if \(d(f_{2})=3\), we consider \(G'=G-\{c_{1},f_{2}\}\). Then \(G'\) is connected. Then \([f_{1}c_{2}]\) and \([f_{3}c_{2}]\) are maximal 2-cliques in \(G'\). If \(G'\) is an odd cycle, we can give an equitable 2-clique-coloring of G directly. If not, by the induction, \(G'\) has an equitable 2-clique-coloring \(\phi\). From \(\phi\), we can easily give an equitable 2-clique-coloring of G together with \(\phi (c_{1})\ne \phi (f_{2})\). If \(d(f_{2})=4\), let \(f_{4}\) be the fourth neighbor of \(f_{2}\). Then by the claw-freeness \(f_{4}\) is adjacent to \(f_{3}\). We consider \(G'=G-\{c_{1},f_{2}\}\). Then \(G'\) is connected. If \(G'\) is an odd cycle, we can give an equitable 2-clique-coloring of G directly. If not, by the induction, \(G'\) has an equitable 2-clique-coloring \(\phi\). Note that \([c_{2}f_{1}]\) and \([c_{2}f_{3}]\) form maximal 2-cliques of \(G'\). From \(\phi\), we can easily give an equitable 2-clique-coloring of G together with \(\phi (f_{2})\ne \phi (f_{3})\) and \(\phi (c_{1})= \phi (f_{3})\).

Case 3: \(d(c_{1})=4\) and \(d(c_{2})=4\).

If \(c_{1}\) and \(c_{2}\) have a common neighbor (say u), by the claw-freeness, u is adjacent to \(f_{1}\) or \(f_{2}\). If u is adjacent to both \(f_{1}\) and \(f_{2}\), then \([c_{1}c_{2}f_{2}u]\) and \([c_{1}c_{2}f_{1}u]\) form two maximal 4-cliques of G. Then \(G-\{c_{1},c_{2} \}\) is an odd cycle or has an equitable 2-clique-coloring \(\phi\). If \(G-\{c_{1},c_{2} \}\) is an odd cycle, we can easily give an equitable 2-clique-coloring of G directly. If not, we can easily give an equitable 2-clique-coloring of G from \(\phi\) together with \(\phi (c_{2})\ne \phi (c_{1})\). If u is adjacent to only one vertex in \(\{f_{1}, f_{2}\}\), assume that u is adjacent to \(f_{2}\), then \([c_{1}c_{2}f_{2}u]\) forms one maximal 4-clique of G. If \(G-\{c_{1},c_{2} \}\) has an odd cycle C of length greater than three as a component, by the limitation of degree and the claw-freeness, we may assume that \(C=uh_{1}h_{2}...h_{j}f_{2}u\). In this case, let \(G'=G-C-c_{1}-c_{2}\). Then \(G'\) is connected and has an equitable 2-clique-coloring \(\phi\). Let \(V_{r}=\{x\mid \phi (x)=r\}\) and \(V_{g}=\{x\mid \phi (x)=g\}\). Not losing the generality, assume by symmetry that \(|V_{g}|\le |V_{r}|\le |V_{g}|+1\). From \(\phi\), we can give an equitable 2-clique-coloring of G by assigning \(\phi (c_{1})\ne \phi (c_{2})\), \(\phi (u)=\phi (f_{2})=g\), \(\phi (h_{i})=r\) (if i is odd) and \(\phi (h_{i})=g\) (if i is even). If \(G-\{c_{1},c_{2} \}\) has no odd cycle of length greater than three as a component, by induction, \(G-\{c_{1},c_{2} \}\) has an equitable 2-clique-coloring \(\phi\) and we can easily get an equitable 2-clique-coloring from \(\phi\) by assigning \(\phi (c_{1})\ne \phi (c_{2})\). If \(c_{1}\) and \(c_{2}\) do not have a common neighbor, let \(u_{1}\) be the fourth neighbor of \(c_{1}\) and \(u_{2}\) be the fourth neighbor of \(c_{2}\). By the claw-freeness and the limitation of degree, we just consider the following cases by symmetry.

Case 3.1: \(\{u_{1}f_{1}, u_{1}f_{2}, u_{2}f_{1}, u_{2}f_{2}\}\subseteq E(G)\). Then, no matter whether \(u_{1}\) is adjacent to \(u_{2}\), G is a graph of six vertices by the claw-freeness and has an equitable 2-clique-coloring.

Case 3.2: \(\{u_{1}f_{1}, u_{1}f_{2}, u_{2}f_{1}\}\subseteq E(G)\) and \(u_{2}f_{2}\notin E(G)\). In addition, if \(d(u_{1})=3\), then \(d(f_{2})=3\) by the limitation of degree and the fact that G is claw-free. In this case, let \(G'=G-\{c_{1},c_{2},f_{1},f_{2}, u_{1}\}\). Then \(G'\) is connected and (by claw-freeness) not an odd cycle of order greater than three and so by the induction hypothesis, \(G'\) is equitably 2-clique-colorable. Let \(\phi : V(G')\rightarrow \{r,g\}\) be an equitable 2-clique-coloring of \(G'\). Let \(V_{r}=\{x\mid \phi (x)=r\}\) and \(V_{g}=\{x\mid \phi (x)=g\}\). Assume by symmetry that \(|V_{g}|\le |V_{r}|\le |V_{g}|+1\). We can get an equitable 2-clique-coloring by assigning \(\phi (c_{1})=\phi (c_{2})=r\) and \(\phi (f_{1})=\phi (f_{2})=\phi (u_{1})= g\). If not, then \(d(u_{1})=4\). Let w be the fourth neighbor of \(u_{1}\). If \(w=u_{2}\), then \(u_{1}\) is adjacent to \(u_{2}\). Since G is claw-free and connected, G is a graph of six vertices and G has an equitable 2-clique-coloring. If \(w\ne u_{2}\), by the limitation of degree and claw-freeness, w is adjacent to \(f_{2}\). In this case, let \(G'=G-\{c_{1},c_{2},f_{1},f_{2}, u_{1}\}\). Then since G is claw-free, no component of \(G'\) is an odd cycle of length greater than three, and so by the induction hypothesis \(G'\) is equitably 2-clique-colorable. Let \(\phi : V(G')\rightarrow \{r,g\}\) be an equitable 2-clique-coloring of \(G'\). Let \(V_{r}=\{x\mid \phi (x)=r\}\) and \(V_{g}=\{x\mid \phi (x)=g\}\). Assume by symmetry that \(|V_{g}|\le |V_{r}|\le |V_{g}|+1\). We can get an equitable 2-clique-coloring by assigning \(\phi (c_{1})=\phi (c_{2})=\phi (u_{1})=g\) and \(\phi (f_{1})=\phi (f_{2})= r\).

Case 3.3: \(\{u_{1}f_{1}, u_{2}f_{1}\}\subseteq E(G)\) and \(u_{1}f_{2}, u_{2}f_{2} \notin E(G)\).

If \(u_{1}\) is adjacent to \(u_{2}\), by the claw-freeness of G, \(G'=G-\{c_{1},c_{2}, f_{1}, u_{1},u_{2}\}\) has no odd cycle of order of greater than three as a component. By induction \(G'\) has an equitable 2-clique-coloring \(\phi\) with two colors r and g. Let \(V_{r}=\{x\mid \phi (x)=r\}\) and \(V_{g}=\{x\mid \phi (x)=g\}\). Assume by symmetry that \(|V_{g}|\le |V_{r}|\le |V_{g}|+1\). We can get an equitable 2-clique-coloring by assigning \(\phi (c_{1})=\phi (f_{1})=\phi (u_{2})=g\) and \(\phi (c_{2})= \phi (u_{1})=r\). If \(u_{1}\) is not adjacent to \(u_{2}\), let \(G'=G-\{c_{1},c_{2}\}\). Since \(d_{G}(f_{1})=4\), \([f_{1}u_{1}]\) and \([f_{1}u_{2}]\) are two maximal 2-cliques of \(G'\). If \(G'\) has one odd cycle C as a component, we may assume that \(C=u_{1}f_{1}u_{2}h_{1}....h_{j}u_{1}\) where j is even. In this case, by induction, \(G''=G-C-c_{1}-c_{2}\) has an equitable 2-clique-coloring \(\phi\) with two colors r and g. Let \(V_{r}=\{x\mid \phi (x)=r\}\) and \(V_{g}=\{x\mid \phi (x)=g\}\). Assume by symmetry that \(|V_{g}|\le |V_{r}|\le |V_{g}|+1\). We can get an equitable 2-clique-coloring by assigning \(\phi (u_{1})=\phi (f_{1})=\phi (c_{2})=g\), \(\phi (c_{1})= \phi (u_{2})=r\), \(\phi (h_{i})=g\) (if i is odd) and \(\phi (h_{i})=r\) (if i is even). If \(G'\) has no odd cycle as a component, we can easily get an equitable 2-clique-coloring of G from an equitable 2-clique-coloring \(\phi\) of \(G'\) by assigning \(\phi (c_{1})\ne \phi (c_{2})\).

Case 3.4: \(\{u_{1}f_{1}, u_{2}f_{2}\}\subseteq E(G)\) and \(u_{1}f_{2}, u_{2}f_{1} \notin E(G)\).

If \(d(f_{2})=3\), let \(G'=G-\{c_{2},f_{2}\}\). At this time, by the claw-freeness and the limitation of degree, no matter whether \(u_{1}\) is adjacent to \(u_{2}\), \(G'\) has no odd cycle of order greater than three as a component. By induction, \(G'\) has an equitable 2-clique-coloring \(\phi\). Then we can get an equitable 2-clique-coloring of G by assigning \(\phi (c_{2})\ne \phi (c_{1})\) and \(\phi (f_{2})=\phi (c_{1})\). If not, by symmetry, we assume that \(d(f_{2})=d(f_{1})=4\). Let \(w_{1}\) and \(w_{2}\) be the fourth neighbors of \(f_{1}\) and \(f_{2}\) respectively (\(w_{1}\) and \(w_{2}\) are not necessarily distinct). By the claw-freeness, \(w_{1}u_{1}\) and \(w_{2}u_{2}\) are edges of G. If \(w_{1}=w_{2}\), then G is a graph with seven vertices and G has an equitable 2-clique-coloring. If \(w_{1}\ne w_{2}\), by the claw-freeness and the limitation of degree, \(u_{1}\) is not adjacent to \(u_{2}\). Let \(G'=G-\{c_{1},c_{2}, f_{1}, f_{2}\}\). Then \(G'\) has no odd cycle of order greater than three as a component. By induction, \(G'\) has an equitable 2-clique-coloring \(\phi\). Then we can get an equitable 2-clique-coloring of G by assigning \(\phi (f_{1})\ne \phi (u_{1})\), \(\phi (c_{1})=\phi (u_{1})\), \(\phi (f_{2})\ne \phi (u_{2})\) and \(\phi (c_{2})=\phi (u_{2})\). \(\square\)

Based on the proofs of Lemma 1 and Theorem 2, we design a linear time algorithm to find an equitable 2-clique-coloring of this class of graphs as follows.

figure a

Theorem 3

Algorithm 1 is a linear time algorithm ( where the input size is the number n of vertices).

Proof

We prove the theorem by the induction on the order of G. Assume that it holds when the order is less than n. In step 1, we can find a diamond or not by checking every vertex. Since the maximum degree of G is at most 4, the time in step 1 is linear. If G has no diamond, we can give an equitable 2-clique-coloring \(\phi\) of G in linear time by the idea in Lemma 1. In step 2, we can construct a graph \(G'\) in linear time at most by the idea in Theorem 2. In step 3, by induction, we can give an equitable 2-clique-coloring \(\phi '\) of \(G'\) in \(O(|G'|)\). In step 4, the time is O(n) at most. Thus the total time is also O(n). \(\square\)

3 Conclusion

In this paper we prove that every connected claw-free graph with maximum degree at most four, other than a chordless odd cycle of order greater than three, is also equitably 2-clique-colorable. In addition we improve the algorithm in [2] by giving an equitable 2-clique-coloring in linear time for this class of graphs. At last, we propose the following problem.

Problem 4

Find the maximum integer k such that there is an equitable 2-clique-coloring in claw-free graphs with maximum degree at most k none of whose components is an odd cycle with order greater than three.

Note that \(k\le 7\) in this problem. By the Ramsey number \(R(3,3)=6\), we have that the line graph of \(K_{6}\) is not 2-clique-colorable. Since line graphs are claw-free and \(L(K_{6})\) is a graph with maximum degree 8, it follows that \(k\le 7\).