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

Lin, Wu-Hsiung; Chang, Gerard J.

Discrete Appl. Math. 160, No. 3, 239-247 (2012).

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.)

Keywords:

equitable coloring; equitable chromatic number; equitable chromatic threshold; Cartesian product

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, ()
[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, (), 601-623
[10]	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 New York
[12]	Irani, S.; Leung, V., Scheduling with conflicts and applications to traffic signal control, (), 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, (), 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.
[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. · 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, (), 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