×

On the complexity of local-equitable coloring of graphs. (English) Zbl 07477134

Summary: An equitable k-partition \((k\geq 2)\) of a vertex set \(S\) is a partition of \(S\) into \(k\) disjoint subsets (may be empty sets) such that the sizes of any two subsets of \(S\) differ by at most one. 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. The local-equitable coloring of \(G\) is a stronger version of clique-coloring of graphs. Chordal graphs are 2-clique-colorable but not necessarily local-equitably 2-colorable. In this paper, we prove that it is NP-complete to decide the local-equitable 2-colorability in chordal graphs and even in split graphs. In addition, we prove that claw-free split graphs are local-equitably \(k\)-colorable when \(k\leq 4\), but not necessarily local-equitably \(k\)-colorable when \(k\geq 5\). A sufficient and sharp condition of local-equitably \(k\)-colorability is also given in claw-free split graphs. Secondly, we show that, given a split graph \(G\), deciding the local-equitable \(k\)-colorability of \(G\) is solvable in polynomial time when \(k=\omega(G)-1\), where \(\omega(G)\) is the clique number of \(G\). At last, we prove that the decision problem of local-equitable 2-coloring of planar graphs is solvable in polynomial time.

MSC:

68Qxx Theory of computing
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Andreae, T.; Schughart, M.; Tuza, Zs., Clique-transversal sets of line graphs and complements of line graphs, Discrete Math., 88, 11-20 (1991) · Zbl 0734.05077
[2] Bacsó, G.; Gravier, S.; Gyárfás, A.; Preissmann, M.; Sebő, A., Coloring the maximal cliques of graphs, SIAM J. Discrete Math., 17, 361-376 (2004) · Zbl 1056.05049
[3] Bacsó, G.; Tuza, Zs., Clique-transversal sets and weak 2-colorings in graphs of small maximum degree, Discrete Math. Theor. Comput. Sci., 11, 2, 15-24 (2009) · Zbl 1196.05029
[4] Bacsó, G.; Ryjáček, Z.; Tuza, Zs., Coloring the cliques of line graphs, Discrete Math., 340, 2641-2649 (2007) · Zbl 1369.05062
[5] Charbit, P.; Penev, I.; Thomassé, S.; Trotignon, N., Perfect graphs of arbitrarily large clique-chromatic number, J. Comb. Theory, Ser. B, 116, 456-464 (2016) · Zbl 1327.05130
[6] Chudnovsky, M.; Lo, I., Decomposing and clique-coloring (diamond, odd-hole)-free graphs, J. Graph Theory, 86, 5-41 (2017) · Zbl 1370.05060
[7] Défossez, D., Clique coloring some classess of odd-hole-free graphs, J. Graph Theory, 53, 233-249 (2006) · Zbl 1108.05036
[8] Défossez, D., Complexity of clique coloring odd-hole-free graphs, J. Graph Theory, 62, 139-156 (2009) · Zbl 1182.05092
[9] Marx, D., Complexity of clique coloring and related problems, Theor. Comput. Sci., 412, 3487-3500 (2011) · Zbl 1222.05070
[10] Kratochvíl, J.; Tuza, Zs., On the complexity of bicoloring clique hypergraphs of graphs, J. Algorithms, 45, 40-54 (2002) · Zbl 1030.68066
[11] Liang, Z.; Shan, E.; Kang, L., Clique-coloring claw-free graphs, Graphs Comb., 32, 1473-1488 (2016) · Zbl 1343.05064
[12] 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) · Zbl 1358.05110
[13] Mohar, B.; Škrekovski, R., The Grötzsch theorem for the hypergraph of maximal cliques, Electron. J. Comb., 6 (1999), #R26 · Zbl 0930.05040
[14] Penev, I., Perfect graphs with no balanced skew-partition are 2-clique-colorable, J. Graph Theory, 81, 213-235 (2016) · Zbl 1381.05025
[15] Rose, D.; Tarjan, R.; Lueker, G., Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput., 5, 266-283 (1976) · Zbl 0353.65019
[16] Schaefer, T. J., The complexity of satisfiability problems, (Proc. 10th Annual ACM Symposium on the Theory of Computing (1978)), 216-226 · Zbl 1282.68143
[17] Shan, E.; Liang, Z.; Kang, L., Clique-transversal sets and clique-coloring in planar graphs, Eur. J. Comb., 36, 367-376 (2014) · Zbl 1284.05075
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.