2020/04/04 by Matthew J. Morgan Henderson, Henderson, M., A. J. W. Hilton +3
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.2004.01848
openalex publication_date 2020/04/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that for a simple graph G, c'(G)≤Δ(G)+2 where c'(G) is the choice index (or edge-list chromatic number) of G, and Δ(G) is the maximum degree of G. As a simple corollary of this result, we show that the total chromatic number χT(G) of a simple graph satisfies the inequality χT(G)≤ Δ(G)+4 and the total choice number cT(G) also satisfies this inequality. We also relate these bounds to the Hall index and the Hall condition index of a simple graph, and to the total Hall number and the total Hall condition number of a simple graph.