List-coloring embedded graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F13%3A10159007" target="_blank" >RIV/00216208:11320/13:10159007 - isvavai.cz</a>

Výsledek na webu

<a href="http://knowledgecenter.siam.org/0236-000037/1" target="_blank" >http://knowledgecenter.siam.org/0236-000037/1</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1137/1.9781611973105.72" target="_blank" >10.1137/1.9781611973105.72</a>

Jazyk výsledku

angličtina

Název v původním jazyce

List-coloring embedded graphs

Popis výsledku v původním jazyce

For any fixed surface Sigma of genus g, we give an algorithm to decide whether a graph G of girth at least five embedded in Sigma is colorable from an assignment of lists of size three in time O(|V(G)|)$ Furthermore, we can allow a subgraph (of any size)with at most s components to be precolored, at the expense of increasing the time complexity of the algorithm to $Ol(|V(G)|^{K(g+s)+1}) for some absolute constant K; in both cases, the multiplicative constant hidden in the O-notation depends on g and s.This also enables us to find such a coloring when it exists. The idea of the algorithm can be applied to other similar problems, e.g., 5-list-coloring of graphs on surfaces.

Název v anglickém jazyce

List-coloring embedded graphs

Popis výsledku anglicky

For any fixed surface Sigma of genus g, we give an algorithm to decide whether a graph G of girth at least five embedded in Sigma is colorable from an assignment of lists of size three in time O(|V(G)|)$ Furthermore, we can allow a subgraph (of any size)with at most s components to be precolored, at the expense of increasing the time complexity of the algorithm to $Ol(|V(G)|^{K(g+s)+1}) for some absolute constant K; in both cases, the multiplicative constant hidden in the O-notation depends on g and s.This also enables us to find such a coloring when it exists. The idea of the algorithm can be applied to other similar problems, e.g., 5-list-coloring of graphs on surfaces.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2013

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 statě ve sborníku

SODA 2013

ISBN

978-1-61197-251-1

ISSN

—

e-ISSN

—

Počet stran výsledku

9

Strana od-do

1004-1012

Název nakladatele

SIAM

Místo vydání

Neuveden

Místo konání akce

New Orleans, Louisiana, USA

Datum konání akce

6. 1. 2013

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—