A strengthening and an efficient implementation of Alon-Tarsi list coloring method
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10491415" target="_blank" >RIV/00216208:11320/24:10491415 - isvavai.cz</a>
Result on the web
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=Hee7QJI.As" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=Hee7QJI.As</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.37236/12058" target="_blank" >10.37236/12058</a>
Alternative languages
Result language
angličtina
Original language name
A strengthening and an efficient implementation of Alon-Tarsi list coloring method
Original language description
As one of the first applications of the polynomial method in combinatorics, Alon and Tarsi 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.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Result continuities
Project
<a href="/en/project/GA22-17398S" target="_blank" >GA22-17398S: Flows and cycles in graphs on surfaces</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Others
Publication year
2024
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Electronic Journal of Combinatorics
ISSN
1097-1440
e-ISSN
1077-8926
Volume of the periodical
31
Issue of the periodical within the volume
1
Country of publishing house
US - UNITED STATES
Number of pages
26
Pages from-to
12058
UT code for WoS article
001167044400001
EID of the result in the Scopus database
2-s2.0-85184422587