On List Equitable Total Colorings of the Generalized Theta Graph

Mudrock, Jeffrey A. ; Marsh, Max ; Wagstrom, Tim

Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 4, pp. 1215-1233.

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 equitably k-choosable if G is equitably L-colorable whenever L is a k-assignment for G. In 2018, Kaul, Mudrock, and Pelsmajer subsequently introduced the List Equitable Total Coloring Conjecture which states that if T is a total graph of some simple graph, then T is equitably k-choosable for each k ≥ maxx_ℓ(T), Δ(T)/2 + 2 where Δ(T) is the maximum degree of a vertex in T and x_ℓ(T ) is the list chromatic number of T. In this paper, we verify the List Equitable Total Coloring Conjecture for subdivisions of stars and the generalized theta graph.

Détail

Keywords: graph coloring, total coloring, equitable coloring, list coloring, equitable choosability

Bibliographie

[1] M. Behzad, Graphs and their Chromatic Numbers, Ph.D. Thesis (Michigan State University, 1965).

[2] J. Beier, J. Fierson, R. Haas, H.M. Russel and K. Shavo, Classifying coloring graphs, Discrete Math. 339 (2016) 2100–2112. https://doi.org/10.1016/j.disc.2016.03.003

[3] J.I. Brown, C.A. Hickman, A.D. Sokal and D.G. Wagner, On the chromatic roots of generalized theta graphs, J. Combin. Theory Ser. B 83 (2001) 272–297. https://doi.org/10.1006/jctb.2001.2057

[4] J.M. Carraher, T. Mahoney, G.J. Puelo and D.B. West, Sum-paintability of generalized theta-graphs, Graphs Combin. 31 (2015) 1325–1334. https://doi.org/10.1007/s00373-014-1441-1

[5] 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

[6] T. Chunling, L. Xiaohui, Y. Yuansheng and L. Zhihe, Equitable total coloring of C m □ C n, Discrete Appl. Math. 157 (2009) 596–601. https://doi.org/10.1016/j.dam.2008.08.030

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

[8] 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

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

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

[11] H.-L. Fu, Some results on equalized total coloring, Congr. Numer. 102 (1994) 111–119.

[12] H. Furmańczyk and R. Zuazua, Equitable total coloring of corona of cubic graphs, Discuss. Math. Graph Theory 41 (2021) 1147–1163. https://doi.org/10.7151/dmgt.2245

[13] M.A. Gang and M.A. Ming, The equitable chromatic number of some join graphs, Open J. Appl. Sci. (2012) 96–99. https://doi.org/10.4236/ojapps.2012.24B023

[14] K. Gong, Z.-F. Zhang and J.-F. Wang, Equitable total coloring of F_n ∨ W_n, Acta Math. Appl. Sin. Engl. Ser. 25 (2009) 83–86. https://doi.org/10.1007/s10255-006-6031-4

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

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

[17] 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

[18] 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

[19] 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

[20] 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

[21] D. Laiche, I. Bouchemakh andÉ. Sopena, On the packing coloring of undirected and oriented generalized theta graphs, Australas. J. Combin. 66 (2016) 310–329.

[22] M.E. Leidner, A Study of the Total Colorings of Graphs, Ph.D. Thesis (University of Louisville, 2012).

[23] 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

[24] R. Li, H. Broersma and S. Zhang, Properly edge-colored theta graphs in edge-colored complete graphs, Graphs Combin. 35 (2019) 261–286. https://doi.org/10.1007/s00373-018-1989-2

[25] K.-W. Lih, The equitable coloring of graphs, in: Handbook of Combinatorial Optimization, D.-Z. Du and P. Pardalos (Ed(s)), (Vol. III, Kluwer, Dordrecht, 1998) 543–566.

[26] 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

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

[28] J. Mudrock, On the List Coloring Problem and Its Equitable Variants, Ph.D. Thesis (Illinois Institute of Technology, 2018).

[29] J. Mudrock, M. Chase, I. Kadera and T. Wagstrom, A note on the equitable choos-ability of complete bipartite graphs, Discuss. Math. Graph Theory 41 2021 1091– 1101. https://doi.org/10.7151/dmgt.2232

[30] K. Nakprasit, personal communication, 2002.

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

[32] G. Sathiamoorthy and T.N. Janakiraman, Graceful labeling of generalized theta graphs, Nat. Acad. Sci. Lett. 41 (2018) 121–122. https://doi.org/10.1007/s40009-018-0625-2

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

[34] V.G. Vizing, Some unsolved problems in graph theory, Ups. Mat. Nauk. 23 (1968) 117–134, in Russian, English translation in Russian Math. Surveys 23 (1968) 125–141. https://doi.org/10.1070/RM1968v023n06ABEH001252

[35] 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.

[36] W.-F. Wang, Equitable total coloring of graphs with maximum degree 3, Graphs Combin. 18 (2002) 677–685. https://doi.org/10.1007/s003730200051

[37] D.B. West, Introduction to Graph Theory (Prentice Hall, NJ, 2001).

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

[39] Z. Zhang, W. Wang, S. Bau and J. Li, On the equitable total colorings of some join graphs, J. Inf. Comput. Sci. 2 (2005) 829–834.

[40] 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

[41] 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

[42] 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

[43] 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