2018/08/04 by Jeffrey A. Mudrock, Madelynn Chase, Mudrock, Jeffrey A. +7
Computer Science · Mathematics · #05C15 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1808.02018
openalex publication_date 2018/08/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 \lceil |V(G)|/k \rceil. 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 ≥ max \n,m\ provided Kn,m ≠ K2l+1, 2l+1. We prove Kn,m is equitably k-choosable if m ≤ \lceil (m+n)/k \rceil(k-n) which gives Kn,m is equitably k-choosable for certain k satisfying k < max \n,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.