2018/06/18 by Hemanshu Kaul, Kaul, Hemanshu, Jeffrey A. Mudrock +5
Neuroscience · #05C15 #Combinatorics (math.CO) #FOS: Mathematics #Nuclear Receptors and Signaling
paper · pdf · doi:10.48550/arxiv.1806.06966
openalex publication_date 2018/06/18 · 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. In this paper, we motivate and define a new list analogue of equitable coloring called proportional choosability. A k-assignment L for a graph G specifies a list L(v) of k available colors for each vertex v of G. An L-coloring assigns a color to each vertex v from its list L(v). For each color c, let η(c) be the number of vertices v whose list L(v) contains c. A proportional L-coloring of G is a proper L-coloring in which each color c ∈ \bigcupv ∈ V(G) L(v) is used \lfloor η(c)/k \rfloor or \lceil η(c)/k \rceil times. A graph G is proportionally k-choosable if a proportional L-coloring of G exists whenever L is a k-assignment for G. We show that if a graph G is proportionally k-choosable, then every subgraph of G is also proportionally k-choosable and also G is proportionally (k+1)-choosable, unlike equitable choosability for which analogous claims would be false. We also show that any graph G is proportionally k-choosable whenever k ≥ Δ(G) + \lceil |V(G)|/2 \rceil, and we use matching theory to completely characterize the proportional choosability of stars and the disjoint union of cliques.