Defective Colouring of Graphs Excluding A Subgraph or Minor
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10422239" target="_blank" >RIV/00216208:11320/19:10422239 - isvavai.cz</a>
Výsledek na webu
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=1Zi2BVrW7b" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=1Zi2BVrW7b</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s00493-018-3733-1" target="_blank" >10.1007/s00493-018-3733-1</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Defective Colouring of Graphs Excluding A Subgraph or Minor
Popis výsledku v původním jazyce
Archdeacon (1987) proved that graphs embeddable on a fixed surface can be 3-coloured so that each colour class induces a subgraph of bounded maximum degree. Edwards, Kang, Kim, Oum and Seymour (2015) proved that graphs with no Kt+1-minor can be t-coloured so that each colour class induces a subgraph of bounded maximum degree. We prove a common generalisation of these theorems with a weaker assumption about excluded subgraphs. This result leads to new defective colouring results for several graph classes, including graphs with linear crossing number, graphs with given thickness (with relevance to the earth-moon problem), graphs with given stack- or queue-number, linklessly or knotlessly embeddable graphs, graphs with given Colin de Verdiere parameter, and graphs excluding a complete bipartite graph as a topological minor.
Název v anglickém jazyce
Defective Colouring of Graphs Excluding A Subgraph or Minor
Popis výsledku anglicky
Archdeacon (1987) proved that graphs embeddable on a fixed surface can be 3-coloured so that each colour class induces a subgraph of bounded maximum degree. Edwards, Kang, Kim, Oum and Seymour (2015) proved that graphs with no Kt+1-minor can be t-coloured so that each colour class induces a subgraph of bounded maximum degree. We prove a common generalisation of these theorems with a weaker assumption about excluded subgraphs. This result leads to new defective colouring results for several graph classes, including graphs with linear crossing number, graphs with given thickness (with relevance to the earth-moon problem), graphs with given stack- or queue-number, linklessly or knotlessly embeddable graphs, graphs with given Colin de Verdiere parameter, and graphs excluding a complete bipartite graph as a topological minor.
Klasifikace
Druh
J<sub>imp</sub> - Č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)
Návaznosti výsledku
Projekt
<a href="/cs/project/LL1201" target="_blank" >LL1201: Komplexní Struktury: Regularita v Kombinatorice a Diskrétní Matematice</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Ostatní
Rok uplatnění
2019
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ů
Údaje specifické pro druh výsledku
Název periodika
Combinatorica
ISSN
0209-9683
e-ISSN
—
Svazek periodika
39
Číslo periodika v rámci svazku
2
Stát vydavatele periodika
DE - Spolková republika Německo
Počet stran výsledku
34
Strana od-do
377-410
Kód UT WoS článku
000471679900007
EID výsledku v databázi Scopus
2-s2.0-85051715901