Discrete Math Seminar


Event Details

  • Date: Thursday, Sep 15th 2022 4:00pm
  • Venue: 203 TMCB
  • Categories:
  • Topic: Relationship between Correspondence Coloring and Alon-Tarsi Number of a Graph
  • Speaker: Eric Culver

Speaker: Eric Culver

Title: Relationship between Correspondence Coloring and Alon-Tarsi Number of a Graph

Abstract: Correspondence coloring is a generalization of list coloring in which the colors appear differently to different vertices. The Alon-Tarsi number of a graph is a parameter derived from the Combinatorial Nullstellensatz which upper bounds most coloring parameters of a graph. However, it fails to be an upper bound on the correspondence chromatic number, and in fact, the exact relationship is not well-understood. We investigate this relationship in more detail, seeing when the correspondence chromatic number is larger, and when the Alon-Tarsi number is larger, and how big of a gap there can be.