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