Abstract
An equitable k-partition (\(k\ge 2\)) of a vertex set S is a partition of S into k subsets (may be empty sets) such that the sizes of any two subsets of S differ by at most one. A maximal-m-clique is a clique with m vertices which is not in a larger clique than itself. A local-equitable k-coloring of G is an assignment of k colors to the vertices of G such that, for every maximal clique of G, the coloring of this clique forms an equitable k-partition of itself. Local-equitable coloring of graphs is a generalization of proper vertex coloring of graphs. In \(K_{4}\)-free planar graphs, the local-equitable 3-coloring is precisely the same as the proper 3-vertex-coloring. The famous Grötzsch Theorem states that triangle-free planar graphs are 3-colorable. 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.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
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 \)
Data Availability
Data sharing not applicable to this article as no datasets were generated or analysed during the current study.
References
G. Bacsó, Zs. Tuza, Clique-transversal sets and weak 2-colorings in graphs of small maximum degree, Disc. Math. Theoret. Comput. Sci. 11(2), 15–24 (2009)
Bacsó, G., Gravier, S., Gyárfás, A., Preissmann, M., Sebő, A.: Coloring the maximal cliques of graphs. SIAM J. Disc. Math. 17, 361–376 (2004)
G. Bacsó, Z. Ryjá\(\check{c}\)ek, Zs. Tuza, Coloring the cliques of line graphs, Discr. Math. 340, 2641–2649 (2007)
Charbit, P., Penev, I., Thomassé, S., Trotignon, N.: Perfect graphs of arbitrarily large clique-chromatic number. J. Combin. Theory Ser. B 116, 456–464 (2016)
Chudnovsky, M., Lo, I.: Decomposing and clique-coloring (diamond, odd-hole)-free graphs. J. Graph Theory 86, 5–41 (2017)
Défossez, D.: Clique coloring some classess of odd-hole-free graphs. J. Graph Theory 53, 233–249 (2006)
Défossez, D.: Complexity of clique coloring odd-hole-free graphs. J. Graph Theory 62, 139–156 (2009)
H. Grötzsch, Ein dreifarbensatz, Ein dreifarbensatz fur dreikreisfreienetze auf der kugel, Math. Nat. Reihe 8 109–120 (1959)
J. Kratochvíl, Zs. Tuza, On the complexity of bicoloring clique hypergraphs of graphs. J. Algorithms 45, 40-54 (2002)
Liang, Z., Shan, E., Kang, L.: Clique-coloring claw-free graphs. Graph Combin. 32, 1473–1488 (2016)
Liang, Z., Shan, E., Zhang, Y.: A linear-time algorithm for clique-coloring problem in circular-arc graphs. J. Comb. Optim. 33, 147–155 (2017)
Liang, Z., Wu, J., Shan, E.: List-coloring clique-hypergraphs of \(K_5\)-minor-free graphs strongly. Discrete Math. 343, 111777 (2020)
Liang, Z., Wang, J., Cai, J., Yang, X.: On the complexity of local-equitable coloring of graphs. Theoret. Comput. Sci. 906, 76–82 (2022)
Marx, D.: Complexity of clique coloring and related problems. Theor. Comput. Sci. 412, 3487–3500 (2011)
B. Mohar, R. \(\check{S}\)krekovski, The Grötzsch theorem for the hypergraph of maximal cliques, Electr. J. Combin. 6, #R26 (1999)
Penev, I.: Perfect graphs with no balanced skew-partition are 2-clique-colorable. J. Graph Theory 81, 213–235 (2016)
Shan, E., Liang, Z., Kang, L.: Clique-transversal sets and clique-coloring in planar graphs. Eur. J. Combin. 36, 367–376 (2014)
Funding
The funding has been received from Nature Science Foundation of Shandong Province with Grant nos. ZR2021MA012 and ZR2021MA103; the Natural Science Research Foundation of Colleges and Universities of Anhui Province with Grant no. KJ2021A0968.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
All of the authors have not disclosed any competing interests.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This research was partially supported by Nature Science Foundation of Shandong Province (Nos. ZR2021MA012 and ZR2021MA103) and the Natural Science Research Foundation of Colleges and Universities of Anhui Province (KJ2021A0968).
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Liang, Z., Wang, J. & Bai, C. A Generalization of Grötzsch Theorem on the Local-Equitable Coloring. Graphs and Combinatorics 39, 4 (2023). https://doi.org/10.1007/s00373-022-02598-5
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s00373-022-02598-5