On the generalised colouring numbers of graphs that exclude a fixed minor

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F17%3A10369567" target="_blank" >RIV/00216208:11320/17:10369567 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1016/j.ejc.2017.06.019" target="_blank" >http://dx.doi.org/10.1016/j.ejc.2017.06.019</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.ejc.2017.06.019" target="_blank" >10.1016/j.ejc.2017.06.019</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On the generalised colouring numbers of graphs that exclude a fixed minor

Popis výsledku v původním jazyce

The generalised colouring numbers col(r)(G) and wcol(r)(G) were introduced by Kierstead and Yang as a generalisation of the usual colouring number, and have since then found important theoretical and algorithmic applications. In this paper, we dramatically improve upon the known upper bounds for generalised colouring numbers for graphs excluding a fixed minor, from the exponential bounds of Grohe et al. to a linear bound for the r-colouring number col(r) and a polynomial bound for the weak r-colouring number wcol(r).

Název v anglickém jazyce

On the generalised colouring numbers of graphs that exclude a fixed minor

Popis výsledku anglicky

The generalised colouring numbers col(r)(G) and wcol(r)(G) were introduced by Kierstead and Yang as a generalisation of the usual colouring number, and have since then found important theoretical and algorithmic applications. In this paper, we dramatically improve upon the known upper bounds for generalised colouring numbers for graphs excluding a fixed minor, from the exponential bounds of Grohe et al. to a linear bound for the r-colouring number col(r) and a polynomial bound for the weak r-colouring number wcol(r).

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

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

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

Rok uplatnění

2017

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

European Journal of Combinatorics

ISSN

0195-6698

e-ISSN

—

Svazek periodika

66

Číslo periodika v rámci svazku

December

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

16

Strana od-do

129-144

Kód UT WoS článku

000411777600012

EID výsledku v databázi Scopus

—