A Note on the Equitable Choosability of Complete Bipartite Graphs

Mudrock, Jeffrey A. ; Chase, Madelynn ; Thornburgh, Ezekiel ; Kadera, Isaac ; Wagstrom, Tim

Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 4, pp. 1091-1101.

Résumé

In 2003 Kostochka, Pelsmajer, and West introduced a list analogue of equitable coloring called equitable choosability. A k-assignment, L, for a graph G assigns a list, L(v), of k available colors to each v ∈ V (G), and an equitable L-coloring of G is a proper coloring, f, of G such that f(v) ∈ L(v) for each v ∈ V (G) and each color class of f has size at most ⌈|V (G)|/k⌉. Graph G is said to be equitably k-choosable if an equitable L-coloring of G exists whenever L is a k-assignment for G. In this note we study the equitable choosability of complete bipartite graphs. A result of Kostochka, Pelsmajer, and West implies K_n,m is equitably k-choosable if k ≥ maxn, m provided K_n,m ≠ K_2l+1,2l+1. We prove K_n,m is equitably k-choosable if m ≤ ⌈ (m + n)/k⌉ (k − n) which gives Kn,m is equitably k-choosable for certain k satisfying k lt; maxn, m. We also give a complete characterization of the equitable choosability of complete bipartite graphs that have a partite set of size at most 2.

Détail

Keywords: graph coloring, equitable coloring, list coloring, equitable choos-ability

Bibliographie

[1] B.-L. Chen, K.-W. Lih and P.-L. Wu, Equitable coloring and the maximum degree, European. J. Combin. 15 (1994) 443–447. https://doi.org/10.1006/eujc.1994.1047

[2] A. Dong and J. Wu, Equitable coloring and equitable choosability of planar graphs without chordal 4 - and 6 -cycles (2018). arXiv:1806.01064

[3] A. Dong and X. Zhang, Equitable coloring and equitable choosability of graphs with small maximum average degree, Discuss. Math. Graph Theory 38 (2018) 829–839. https://doi.org/10.7151/dmgt.2049

[4] E. Drgas-Burchardt, J. Dybizbański, H. Furmańczyk and E. Sidorowicz, Equitable list vertex colourability and arboricity of grids, Filomat. 32 (2018) 6353–6374. https://doi.org/10.2298/FIL1818353D

[5] P. Erdős, Problem 9, in: M. Fiedler (Ed.), Theory of Graphs and Its Applications, Proc. Sympos., Smolenice, 1963, Publ. House Czechoslovak Acad. Sci. Prague (1964) 159.

[6] P. Erdős, A.L. Rubin and H. Taylor, Choosability in graphs, Congr. Numer. 26 (1979) 125–127.

[7] A. Hajnál and E. Szemerédi, Proof of a conjecture of Erd˝os, in: A Rényi and V.T. Sós, (Eds), Combin. Theory Appl. II (North-Holland, Amsterdam, 1970) 601–623.

[8] S. Janson and A. Ruciński, The infamous upper tail, Random Structures Algorithms 20 (2002) 317–342. https://doi.org/10.1002/rsa.10031

[9] H. Kaul and S.H. Jacobson, New global optima results for the Kau man NK model: handling dependency, Math. Program. 108 (2006) 475–494. https://doi.org/10.1007/s10107-006-0719-3

[10] H. Kaul, J.A. Mudrock and M.J. Pelsmajer, Total equitable list coloring, Graphs Combin. 34 (2018) 1637–1649. https://doi.org/10.1007/s00373-018-1965-x

[11] H. Kaul, J.A. Mudrock, M.J. Pelsmajer and B. Reiniger, Proportional choosability: a new list analogue of equitable coloring, Discrete Math. 342 (2019) 2371–2383. https://doi.org/10.1016/j.disc.2019.05.011

[12] H.A. Kierstead and A.V. Kostochka, Equitable list coloring of graphs with bounded degree, J. Graph Theory 74 (2013) 309–334. https://doi.org/10.1002/jgt.21710

[13] A.V. Kostochka, M.J. Pelsmajer and D.B. West, A list analogue of equitable coloring, J. Graph Theory 44 (2003) 166–177. https://doi.org/10.1002/jgt.10137

[14] Q. Li and Y. Bu, Equitable list coloring of planar graphs without 4 - and 6 -cycles, Discrete Math. 309 (2009) 280–287. https://doi.org/10.1016/j.disc.2007.12.070

[15] K.-W. Lih, The equitable coloring of graphs, in: D.-Z. Du and P. Pardalos (Eds), Handbook of Combinatorial Optimization III (Kluwer, Dordrecht, 1998) 543–566. https://doi.org/10.1007/978-1-4613-0303-9_31

[16] K.-W. Lih and P.-L. Wu, On equitable coloring of bipartite graphs, Discrete Math. 151 (1996) 155–160. https://doi.org/10.1016/0012-365X(94)00092-W

[17] W. Meyer, Equitable coloring, Amer. Math. Monthly 80 (1973) 920–922. https://doi.org/10.1080/00029890.1973.11993408

[18] S.V. Pemmaraju, Equitable colorings extend Cherno -Hoe ding bounds, in: Proceedings of the 5th International Workshop on Randomization and Approximation Techniques in Computer Science (2001) 285–296.

[19] A. Tucker, Perfect graphs and an application to optimizing municipal services, SIAM Review 15 (1973) 585–590. https://doi.org/10.1137/1015072

[20] V.G. Vizing, Coloring the vertices of a graph in prescribed colors, Diskret. Analiz. 29, Metody Diskret. Anal. v Teorii Kodovi Skhem 101 (1976) 3–10.

[21] D.B. West, Introduction to Graph Theory (Upper Saddle River, NJ, Prentice Hall, 2001).

[22] H.P. Yap and Y. Zhang, The equitable -coloring conjecture holds for outerplanar graphs, Bull. Inst. Math. Acad. Sinica 25 (1997) 143–149.

[23] X. Zhang and J.-L. Wu, On equitable and equitable list colorings of series-parallel graphs, Discrete Math. 311 (2011) 800–803. https://doi.org/10.1016/j.disc.2011.02.001

[24] J. Zhu and Y. Bu, Equitable list coloring of planar graphs without short cycles, Theoret. Comput. Sci. 407 (2008) 21–28. https://doi.org/10.1016/j.tcs.2008.04.018

[25] J. Zhu and Y. Bu, Equitable and equitable list colorings of graphs, Theoret. Comput. Sci. 411 (2010) 3873-3876. https://doi.org/10.1016/j.tcs.2010.06.027

[26] J. Zhu, Y. Bu and X. Min, Equitable list-coloring for C₅-free plane graphs without adjacent triangles, Graphs Combin. 31 (2015) 795–804. https://doi.org/10.1007/s00373-013-1396-7