Relation between the correspondence chromatic number and the Alon--Tarsi number

2022/06/23 by Eric Culver, Culver, Eric, Stephen G. Hartke +1
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems

paper · pdf · doi:10.48550/arxiv.2206.11964

openalex publication_date 2022/06/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the relation between the correspondence chromatic number and the Alon--Tarsi number, both upper bounds on the list chromatic number of a graph. There are many graphs with Alon--Tarsi number greater than the correspondence chromatic number. We present here a family of graphs with arbitrary Alon--Tarsi number, with correspondence chromatic number one larger. Keywords: correspondence coloring, Alon--Tarsi number AMS Mathematics Subject Classification: 05C15

Related

• Alon-Tarsi Number of Some Regular Graphs
• The Alon-Tarsi number of planar graphs -- a simple proof
• On the Alon-Tarsi Number and Chromatic-choosability of Cartesian\n Products of Graphs
• On the Alon-Tarsi Number of Some Line and Total graphs
• Alon-Tarsi number of signed planar graphs