A strengthening and an efficient implementation of Alon-Tarsi list coloring method (Q6197808)

From MaRDI portal
scientific article; zbMATH DE number 7806470
Language Label Description Also known as
English
A strengthening and an efficient implementation of Alon-Tarsi list coloring method
scientific article; zbMATH DE number 7806470

    Statements

    A strengthening and an efficient implementation of Alon-Tarsi list coloring method (English)
    0 references
    0 references
    19 February 2024
    0 references
    Summary: As one of the first applications of the polynomial method in combinatorics, \textit{N. Alon} and \textit{M. Tarsi} [Combinatorica 12, No. 2, 125--134 (1992; Zbl 0756.05049)] proved that if certain coefficients of the graph polynomial are non-zero, then the graph is choosable, i.e., colorable from any assignment of lists of prescribed size. We show that in case all relevant coefficients are zero, then further coefficients of the graph polynomial provide constraints on the list assignments from which the graph cannot be colored. This often enables us to confirm colorability from a given list assignment, or to decide choosability by testing just a few list assignments. We also describe an efficient way to implement this approach, making it feasible to test choosability of graphs with around 70 edges.
    0 references
    polynomial method
    0 references
    orientations
    0 references
    chromatic number
    0 references
    vertex-coloring
    0 references

    Identifiers

    0 references
    0 references
    0 references