×

Equitable colorings of Cartesian products of graphs. (English) Zbl 1241.05035

Summary: The present paper studies the following variation of vertex coloring on graphs. A graph \(G\) is equitably \(k\)-colorable if there is a mapping \(f: V(G)\to\{1,2,\dots,k\}\) such that \(f(x)\not\in f(y)\) for \(xy\in E(G)\) and \(\| f^{-1}(i)|-|f^{-1}(j)\|\leq 1\) for \(1\leq i,\,j\leq k\). The equitable chromatic number of a graph \(G\), denoted by \(\chi_=(G)\), is the minimum \(k\) such that \(G\) is equitably \(k\)-colorable. The equitable chromatic threshold of a graph \(G\), denoted by \(\chi^*_=(G)\), is the minimum \(t\) such that \(G\) is equitably \(k\)-colorable for all \(k\geq t\).
Our focus is on the equitable colorability of Cartesian products of graphs. In particular, we give exact values or upper bounds of \(\chi_= (G\square H)\) and \(\chi^*_=(G\square H)\) when \(G\) and \(H\) are cycles, paths, stars, or complete bipartite graphs.

MSC:

05C15 Coloring of graphs and hypergraphs
05C76 Graph operations (line graphs, products, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baker, B.; Coffman, E., Mutual exclusion scheduling, Theoret. Comput. Sci., 162, 2, 225-243 (1996) · Zbl 0877.68007
[2] Blum, D.; Torrey, D.; Hammack, R., Equitable chromatic number of complete multipartite graphs, Missouri J. Math. Sci., 15, 2, 75-81 (2003) · Zbl 1027.05038
[3] Chang, G. J., A note on equitable colorings of forests, European J. Combin., 30, 809-812 (2009) · Zbl 1220.05037
[4] Chen, B.-L.; Lih, K.-W., Equitable coloring of trees, J. Combin. Theory Ser. B, 61, 1, 83-87 (1994) · Zbl 0805.05027
[5] Chen, B.-L.; Lih, K.-W.; Wu, P.-L., Equitable coloring and the maximum degree, European J. Combin., 15, 5, 443-447 (1994) · Zbl 0809.05050
[6] Chen, B.-L.; Lih, K.-W.; Yan, J.-H., Equitable coloring of interval graphs and products of graphs
[7] Erdős, P., Problem 9, (Fielder, M., Theory of Graphs and its Applications, vol. 159 (1964), Czech. Acad. Sci. Publ.: Czech. Acad. Sci. Publ. Prague)
[8] Furmańczyk, H., Equitable colorings of graph products, Opuscula Math., 26, 1, 31-44 (2006)
[9] Hajnal, A.; Szemerédi, E., Proof of a conjecture of P. Erdős, (Erdős, P.; Rényi, A.; Sós, V. T., Combinatorial Theory and Applications (1970), North-Holland: North-Holland London), 601-623 · Zbl 0217.02601
[10] S. Hedetniemi, Homomorphism of graphs and automata, Univ. Michigan Technical Report 03105-44-T, 1966.; S. Hedetniemi, Homomorphism of graphs and automata, Univ. Michigan Technical Report 03105-44-T, 1966.
[11] Imrich, W.; Klavzaˇr, S., Product Graphs: Structure and Recognition (2000), Wiley: Wiley New York
[12] Irani, S.; Leung, V., Scheduling with conflicts and applications to traffic signal control, (Proc. of Seventh Annu. ACM-SIAM Symp. on Discrete Algorithms (1996), SIAM: SIAM Atlanta, GA), 85-94, Philadelphia, PA · Zbl 0845.90072
[13] Janson, S.; Ruciński, A., The infamous upper tail, Random Struct. Algorithms, 20, 3, 317-342 (2002) · Zbl 0996.60023
[14] Kierstead, H. A.; Kostochka, A. V., A short proof of the Hajnal-Szemerédi theorem on equitable coloring, Combin. Probab. Comput., 17, 2, 265-270 (2008) · Zbl 1163.05015
[15] Kierstead, H. A.; Kostochka, A. V., An Ore-type theorem on equitable coloring, J. Combin. Theory Ser. B, 98, 226-234 (2008) · Zbl 1127.05039
[16] Kitagawa, F.; Ikeda, H., An existential problem of a weight-controlled subset and its application to schedule timetable construction, Discrete Math., 72, 1-3, 195-211 (1988) · Zbl 0664.90076
[17] Kostochka, A. V., Equitable colorings of outerplanar graphs, Discrete Math., 258, 1-3, 373-377 (2002) · Zbl 1009.05059
[18] Kostochka, A. V.; Nakprasit, K., Equitable coloring of \(k\)-degenerate graphs, Combin. Probab. Comput., 12, 53-60 (2003) · Zbl 1012.05063
[19] Kostochka, A. V.; Nakprasit, K., On equitable \(\Delta \)-coloring of graphs with low average degree, Theoret. Comput. Sci., 349, 1, 82-91 (2005) · Zbl 1086.05030
[20] Kostochka, A. V.; Nakprasit, K.; Pemmaraju, S. V., On equitable coloring of \(d\)-degenerate graphs, SIAM J. Discrete Math., 19, 1, 83-95 (2005) · Zbl 1082.05037
[21] Kostochka, A. V.; Pelsmajer, M. J.; West, D. B., A list analogue of equitable coloring, J. Graph Theory, 44, 3, 166-177 (2003) · Zbl 1031.05050
[22] Lam, P. C.B.; Shiu, W. C.; Tong, C. S.; Zhang, C. F., On the equitable chromatic number of complete \(n\)-partite graphs, Discrete Appl. Math., 113, 2-3, 307-310 (2001) · Zbl 0990.05050
[23] Lih, K.-W., The equitable coloring of graphs, (Du, D.-Z.; Pardalos, P., Handbook of Combinatorial Optimization, vol. 3 (1998), Kluwer: Kluwer Dordrecht), 543-566 · Zbl 0944.05049
[24] Lih, K.-W.; Wu, P.-L., On equitable coloring of bipartite graphs, Discrete Math., 151, 1-3, 155-160 (1996) · Zbl 0856.05040
[25] Lin, W.-H.; Chang, G. J., Equitable colorings of Kronecker products of graphs, Discrete Appl. Math., 158, 1816-1826 (2010) · Zbl 1208.05029
[26] Meyer, W., Equitable coloring, Amer. Math. Monthly, 80, 920-922 (1973) · Zbl 0279.05106
[27] M. Mydlarz, E. Szemerédi, Algorithmic Brooks’ theorem, Manuscript.; M. Mydlarz, E. Szemerédi, Algorithmic Brooks’ theorem, Manuscript.
[28] Pelsmajer, M. J., Equitable list-coloring for graphs of maximum degree 3, J. Graph Theory, 47, 1, 1-8 (2004) · Zbl 1053.05051
[29] S.V. Pemmaraju, Equitable colorings extend Chernoff-Hoeffding bounds, in: Proc. Fifth Internat. Workshop on Randomization and Approximation Techniques in Computer Sciences, APPROX-RANDOM 2001, pp. 285-296.; S.V. Pemmaraju, Equitable colorings extend Chernoff-Hoeffding bounds, in: Proc. Fifth Internat. Workshop on Randomization and Approximation Techniques in Computer Sciences, APPROX-RANDOM 2001, pp. 285-296. · Zbl 0998.68231
[30] Sabidussi, G., Graphs with given group and given graph-theoretical properties, Canad. J. Math., 9, 515-525 (1957) · Zbl 0079.39202
[31] Smith, B. F.; Bjorstad, P. E.; Gropp, W. D., Domain decomposition, (Parallel Multilevel Methods for Elliptic Partial Differential Equations (1996), Cambridge University Press: Cambridge University Press Cambridge), 224 · Zbl 0857.65126
[32] Tucker, A., Perfect graphs and an application to optimizing municipal services, SIAM Rev., 15, 585-590 (1973) · Zbl 0255.05111
[33] Vizing, V. G., The Cartesian product of graphs, Vyčhisl. Sistemy, 9, 30-43 (1963) · Zbl 0931.05033
[34] Wang, W.-F.; Lih, K.-W., Equitable list coloring of graphs, Taiwanese J. Math., 8, 4, 747-759 (2004) · Zbl 1063.05051
[35] Yap, H.-P.; Zhang, Y., The \(\Delta \)-equitable colouring conjecture holds for outerplanar graphs, Bull. Inst. Math. Acad. Sin., 25, 2, 143-149 (1997) · Zbl 0882.05054
[36] Yap, H.-P.; Zhang, Y., Equitable colourings of planar graphs, J. Combin. Math. Combin. Comput., 27, 97-105 (1998) · Zbl 0927.05033
[37] Zhu, X., A survey on Hedetniemi’s conjecture, Taiwanese J. Math., 2, 1, 1-24 (1998) · Zbl 0906.05024
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.