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

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

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

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

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

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/GA22-17398S" target="_blank" >GA22-17398S: Toky a cykly v grafech na plochách</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Electronic Journal of Combinatorics

ISSN

1097-1440

e-ISSN

1077-8926

Svazek periodika

31

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

26

Strana od-do

12058

Kód UT WoS článku

001167044400001

EID výsledku v databázi Scopus

2-s2.0-85184422587