×

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.)
PDF BibTeX XML Cite
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, ()
[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
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.