×

Equitable clique-coloring in claw-free graphs with maximum degree at most 4. (English) Zbl 1464.05155

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\). A clique-coloring, also known as weak coloring, 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 is monochromatic. An equitable vertex-coloring of \(G\) is a proper vertex-coloring such that any two color classes differ in size by at most one. 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.
The purpose of the paper is to show 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, where the claw is the complete bipartite graph \(K(1;3)\). The paper also gives an algorithm for an equitable 2-clique-coloring in linear time for this class of graphs.

MSC:

05C15 Coloring of graphs and hypergraphs
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C85 Graph algorithms (graph-theoretic aspects)

Citations:

Zbl 1196.05029
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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 · doi:10.1137/S0895480199359995
[2] Bacsó, G.; Tuza, Z., 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
[3] Berge, C.; Sterboul, F., Equipartite colorings in graphs and hypergraphs, J. Combin. Theory (B), 22, 97-113 (1977) · Zbl 0353.05035 · doi:10.1016/0095-8956(77)90002-8
[4] Bacsó, G.; Ryjáček, Z.; Tuza, Z., Coloring the cliques of line graphs, Discrete Math., 340, 2641-2649 (2007) · Zbl 1369.05062 · doi:10.1016/j.disc.2016.11.011
[5] 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) · Zbl 1327.05130 · doi:10.1016/j.jctb.2015.09.008
[6] Chudnovsky, M.; Lo, I., Decomposing and clique-coloring (diamond, odd-hole)-free graphs, J. Graph Theory, 86, 5-41 (2017) · Zbl 1370.05060 · doi:10.1002/jgt.22110
[7] Chen, BL; Lih, KW; Wu, PL, Equitable coloring and the maximum degree, Eur. J. Combin., 15, 443-447 (1994) · Zbl 0809.05050 · doi:10.1006/eujc.1994.1047
[8] Défossez, D., Clique coloring some classess of odd-hole-free graphs, J. Graph Theory, 53, 233-249 (2006) · Zbl 1108.05036 · doi:10.1002/jgt.20177
[9] Défossez, D., Complexity of clique coloring odd-hole-free graphs, J. Graph Theory, 62, 139-156 (2009) · Zbl 1182.05092 · doi:10.1002/jgt.20387
[10] Hajnal, A., Szemerédi, E.: Proof of a conjecture of P. Erdös, In: Erdös, P., Rényi, A., Sós V.T. (eds) Combinatorial theory and its application. North-Holland, London, pp. 601-623 (1970) · Zbl 0217.02601
[11] Marx, D., Complexity of clique coloring and related problems, Theoret. Comput. Sci., 412, 3487-3500 (2011) · Zbl 1222.05070 · doi:10.1016/j.tcs.2011.02.038
[12] Mycielski, J., Sur le coloriage des graphes, Colloq. Math., 3, 161-162 (1955) · Zbl 0064.17805 · doi:10.4064/cm-3-2-161-162
[13] Kierstead, HA; Kostochka, AV, A short proof of the Hajnal-Szemerédi Theorem on equitable coloring, Combin. Probab. Comput., 17, 265-270 (2008) · Zbl 1163.05015 · doi:10.1017/S0963548307008619
[14] Kierstead, HA; Kostochka, AV, Every 4-colorable graph with maximum degree 4 has an equitable 4-coloring, J. Graph Theory, 71, 31-48 (2012) · Zbl 1248.05069 · doi:10.1002/jgt.20630
[15] Kierstead, HA; Kostochka, AV; Mydlarz, M.; Szemerédi, E., A fast algorithm for equitable coloring, Combinatorica, 30, 217-224 (2010) · Zbl 1224.05176 · doi:10.1007/s00493-010-2483-5
[16] Kratochvíl, J.; Tuza, Z., On the complexity of bicoloring clique hypergraphs of graphs, J. Algorithms, 45, 40-54 (2002) · Zbl 1030.68066 · doi:10.1016/S0196-6774(02)00221-3
[17] Liang, Z.; Shan, E.; Kang, L., Clique-coloring claw-free graphs, Graph Combin., 32, 1473-1488 (2016) · Zbl 1343.05064 · doi:10.1007/s00373-015-1657-8
[18] Liang, Z.; Shan, E.; Kang, L., Clique-perfectness of claw-free planar graphs, Graph Combin., 32, 2551-2562 (2016) · Zbl 1353.05091 · doi:10.1007/s00373-016-1726-7
[19] 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 · doi:10.1007/s10878-015-9941-3
[20] Mohar, B.; Škrekovski, R., The Grötzsch theorem for the hypergraph of maximal cliques, Electr. J. Combin., 6, #R26 (1999) · Zbl 0930.05040 · doi:10.37236/1458
[21] Penev, I., Perfect graphs with no balanced skew-partition are 2-clique-colorable, J. Graph Theory, 81, 213-235 (2016) · Zbl 1381.05025 · doi:10.1002/jgt.21870
[22] Shan, E.; Liang, Z.; Kang, L., Clique-transversal sets and clique-coloring in planar graphs, Eur. J. Combin., 36, 367-376 (2014) · Zbl 1284.05075 · doi:10.1016/j.ejc.2013.08.003
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.