Geodesic
A Note on the Equitable Choosability of Complete Bipartite Graphs
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 4, pp. 1091-1101

Voir la notice de l'article provenant de la source Library of Science

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 Kn,m is equitably k-choosable if k ≥ maxn, m provided Kn,m ≠ K2l+1,2l+1. We prove Kn,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.
Keywords: graph coloring, equitable coloring, list coloring, equitable choos-ability 
@article{DMGT_2021_41_4_a14,
     author = {Mudrock, Jeffrey A. and Chase, Madelynn and Thornburgh, Ezekiel and Kadera, Isaac and Wagstrom, Tim},
     title = {A {Note} on the {Equitable} {Choosability} of {Complete} {Bipartite} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1091--1101},
     publisher = {mathdoc},
     volume = {41},
     number = {4},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a14/}
}
TY  - JOUR
AU  - Mudrock, Jeffrey A.
AU  - Chase, Madelynn
AU  - Thornburgh, Ezekiel
AU  - Kadera, Isaac
AU  - Wagstrom, Tim
TI  - A Note on the Equitable Choosability of Complete Bipartite Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 1091
EP  - 1101
VL  - 41
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a14/
LA  - en
ID  - DMGT_2021_41_4_a14
ER  - 
%0 Journal Article
%A Mudrock, Jeffrey A.
%A Chase, Madelynn
%A Thornburgh, Ezekiel
%A Kadera, Isaac
%A Wagstrom, Tim
%T A Note on the Equitable Choosability of Complete Bipartite Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 1091-1101
%V 41
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a14/
%G en
%F DMGT_2021_41_4_a14
Mudrock, Jeffrey A.; Chase, Madelynn; Thornburgh, Ezekiel; Kadera, Isaac; Wagstrom, Tim. A Note on the Equitable Choosability of Complete Bipartite Graphs. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 4, pp. 1091-1101. http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a14/