1 Introduction

All graphs considered here are finite, simple and connected graphs with at least one edge.

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 induced by S is denoted by G[S]. As usual, \(K_n\) and \(C_n\) denote the complete graph and cycle on n vertices, respectively.

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, and the largest such m is called the clique number \(\omega (G)\) of G. A maximal-m-clique is an m-clique which is not in a larger clique than itself. 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 maximal clique of size at least two of G is monochromatic. A k-clique-coloring of G is a clique-coloring with k colors. 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 \(\chi _{C}(G)\le \chi (G)\). Clique-coloring has received considerable attention (see [1-7, 9-13, 15-17]).

Local-equitable coloring of graphs is a stronger version of clique-coloring by coloring all the maximal cliques of a graph equitably, which is proposed in [13]. An equitable k-partition (\(k\ge 2\)) of a vertex set S is a k-partition of S such that the sizes of any two subsets of S differ by at most one. A local-equitable k-coloring (\(k\ge 2\)) of G is an assignment of k colors to the vertices of G such that, for every maximal clique K of G, the coloring on K is an equitable k-partition of K. Obviously, if a maximal clique K of G has no more than k vertices, K must receive |K| colors in the local-equitable k-coloring of G. Thus, if \(k\ge \chi (G)\), the local-equitable k-coloring of G is a proper vertex coloring of G. Hence, the local-equitable coloring of graphs is a generalization of the vertex coloring of graphs. If G has a local-equitable k-coloring, we say that G is local-equitably k-colorable. The smallest integer \(k^{*}\), such that G admits a local-equitable k-coloring of G when \(k\ge k^{*}\), is called the local-equitable chromatic number and denoted by \(\chi _{LEQ}(G)\). Obviously, \(\chi _{C}(G)\le \chi _{LEQ}(G)\le \chi (G)\). In \(K_{4}\)-free graphs, a local-equitable 3-coloring is the same as a 3-vertex-coloring. Hence, in planar graphs, local-equitable 3-coloring includes the hot 3-color problem. In addition, in \(K_{4}\)-free graphs, a local-equitable 2-coloring is also the same as a 2-clique-coloring. Hence, determining \(\chi _{LEQ}(G)\) is also hard as follows. First, the 3-color-problem is NP-complete. Secondly, to decide whether a graph is 2-clique-colorable is NP-complete on \(K_{4}\)-free graphs [9], graphs with maximum degree 3 [2] and even (\(K_{4}\), diamond)-free perfect graphs [6]. Recently, Liang et al. proved that the decision problem of local-equitable 2-coloring of chordal graphs is NP-complete and the decision problem of local-equitable 2-coloring of planar graphs is solvable in polynomial time.

The famous Grötzsch Theorem states that triangle-free planar graphs are 3-colorable [8]. In this paper, we show that maximal-3-clique-free planar graphs are local-equitable 3-colorable, which is a generalization of Grötzsch Theorem.

2 Local-Equitable Coloring in Planar Graphs

By the definition of local-equitable coloring of graphs, we can see that \(\chi _{LEQ}(G)\le 4\) by the Four Color Theorem for a planar graph G. Clearly, a planar graph G is local-equitable 3-colorable if and only if every maximal 2-clique of G receives two colors and every other maximal clique of G receives three colors. This implies that the local-equitable 3-coloring in \(K_{4}\)-free planar graphs is precisely the same as the proper 3-vertex-coloring.

Recall that, in planar graphs, the local-equitable 3-coloring is also a stronger version of strong clique-coloring. A strong clique-coloring of a graph is defined as a clique-coloring of G such that every triangle of G receives at least two colors. Mohar and \({\check{S}}\)krekovskiwere [15] proved that planar graphs are strongly 3-clique-colorable. However, a strong 3-clique-coloring of a planar graph is not equivalent to a local-equitable 3-coloring of this graph, since, if a triangle is a maximal 3-clique, then it should get three colors in the local-equitable 3-coloring.

The famous Grötzsch Theorem states that triangle-free planar graphs are 3-colorable. It is natural to ask whether every maximal-3-clique-free planar graph is local-equitably 3-colorable. If the answer is positive, it would be a generalization of Grötzsch Theorem. In this section we will answer the question. First, we give some results, which will be useful.

Theorem 1

[8] Every triangle-free planar graph G is 3-colorable. Moreover, every 3-coloring of a 4-cycle or a 5-cycle of G can be extended to a 3-coloring of the whole graph.

Theorem 2

[15] Every planar graph is 3-clique-colorable.

Lemma 3

[15] Let G be a connected plane graph whose outer cycle C is a 3-cycle. Let c be a coloring of C with 2 or 3 colors. Then c can be extended to a 3-clique-coloring of G.

Lemma 4

Let G be a planar graph. If G has only maximal 4-cliques, then G is local-equitable 3-colorable. In addition, for any one given edge \(e=x_{1}x_{2}\) of G, there is a local-equitable 3-coloring of G such that the ends of e receive different colors or the same color.

Proof

By the 4-Color Theorem, there is a 4-coloring of G. For \(i=1,2,3,4\), let \(U_{i}\subseteq V(G)\) be the set of vertices colored i. Without the loss of generality, assume that \(x_{1}\in U_{1}\) and \(x_{2}\in U_{2}\). Let \( c(v)=2\) if \(v\in U_{1}\cup U_{2}\), \( c(v)=3\) if \(v\in U_{3}\) and \( c(v)=4\) if \(v\in U_{4}\). Then c is a local-equitable 3-coloring of G such that the ends of e receive the same color. Let \( c(v)=1\) if \(v\in U_{1}\), \( c(v)=2\) if \(v\in U_{2}\) and \( c(v)=3\) if \(v\in U_{3}\cup U_{4}\). Then c is a local-equitable 3-coloring of G such that the ends of e receive different colors. \(\square \)

Now, we prove our main result.

Theorem 5

Every planar graph G with no maximal 3-clique is local-equitably 3-colorable.

Proof

Suppose that G is a counterexample to the theorem with the smallest number of vertices and assume that G is embedded in the plane already. Clearly, G has both maximal 2-cliques and maximal 4-cliques. If G has no 4-clique, by Theorem 1, G is 3-colorable and thus local-equitably 3-colorable, a contradiction. If G has only 4-cliques, by Lemma 4, we still has a contradiction. Now, we consider the properties of the minimal counterexample G.

Let \(K^{1}=[x_{1}x_{2}x_{3}x_{4}]\) represent an arbitrary 4-clique of G. Assume that \({x_{1}}\) is inside the cycle \(C_{1}= [x_{2}x_{3}x_{4}] \) in the embedding of G in the plane, and call \(C_{1}\) the outer cycle of \(K^{1}\). We call that a maximal clique (a 2-clique or a 4-clique) is embedded in a 4-clique \(K^{1}\) if all the vertices of this clique are on or inside the outer cycle of \(K^{1}\). Further, we can also say that a maximal clique \(K^{2}\) (a 2-clique or a 4-clique) is younger than a 4-clique \(K^{1}\) if \(K^{2}\) is embedded in the 4-clique \(K^{1}\). We first have the following claim about G.

Claim 1. There is no maximal 2-clique of G which is embedded in a 4-clique of G.

Suppose not, let \(K=[y_{1}y_{2}y_{3}y_{4}]\) be a 4-clique such that there is a maximal 2-clique embedded in K, and for every 4-clique \(K'\) which is younger than K, no maximal 2-cliques are embedded in \(K'\). We may assume that \([y_{2}y_{3}y_{4}] \) is the outer cycle of K and there exist maximal 2-cliques embedded in \(T=[y_{1}y_{2}y_{3}]\). We construct \(G^{*}\), \(G_{T}\) and \(G_{T}^{*}\) as follows. Let \(G^{*}\) be the graph obtained from G by deleting the vertices inside T. Then \(G^{*}\) has no maximal 3-clique and is local-equitable 3-colorable since G is the smallest counterexample. Let \(G_{T}\) be the graph induced by the vertices on T and the vertices inside T. Then T is a maximal-3-clique of \(G_{T}\) by our assumption that, for every 4-clique \(K'\) which is younger that K, no maximal 2-cliques are embedded in \(K'\). We construct \(G_{T}^{*}\) from \(G_{T}\) as follows: for every 4-clique \(K^{*}\) in \(G_{T}\) which are not embedded in other 4-clique of \(G_{T}\), we deleting all the vertices inside the outer cycle of \(K^{*}\). Then \(G_{T}^{*}\) has no 4-cliques. Let \(\phi \) be the local-equitable-3-coloring of \(G^{*}\). Then the triangle T receives at least two colors. By Lemma 3, we can extend the coloring on T into a 3-clique-coloring of \(G_{T}^{*}\). Then every triangle in \(G_{T}^{*}\) receive at least two colors. For every triangle \(T^{*}\) in \(G_{T}^{*}\) different from T, we consider the graph \(G_{T^{*}}\) induced by the vertices of G which are on or inside \(T^{*}\). Then \(G_{T^{*}}\) has only maximal 4-cliques. By Lemma 4, we can extend the coloring on \(T^{*}\) into a local-equitable 3-coloring of \(G_{T^{*}}\). Thus we get a local-equitable 3-coloring of G, a contradiction.

According to Claim 1, we consider every 4-clique \(K^{*}\) in G which are not embedded in other 4-clique of G. Let \(T^{*}\) be the outer cycle of every \(K^{*}\) and \(G_{T^{*}}\) be the graph induced by the vertices on and inside \(T^{*}\). By Claim 1, \(G_{T^{*}}\) has only 4-cliques. Let \(G'\) be the graph obtained by deleting all the vertices inside the outer cycle of every \(K^{*}\) of G. Then \(G'\) has no 4-clique. By Theorem 2, \(G'\) is 3-clique-colorable. Let \(\phi \) be the 3-clique-coloring of \(G'\). Then every triangle \(T^{*}\) of \(G'\) receives at least two colors. For every triangle \(T^{*}\) of \(G'\), by Lemma 4, we can extend the coloring on \(T^{*}\) into a local-equitable 3-coloring of \(G_{T^{*}}\). Thus we get a local-equitable 3-coloring of G, still a contradiction. \(\square \)