$k$-chromatic number of graphs on surfaces

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F09%3A00207123" target="_blank" >RIV/00216208:11320/09:00207123 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

$k$-chromatic number of graphs on surfaces

Popis výsledku v původním jazyce

Considering all partitions of the edges of a graph G to k parts, the the k-chromatic number of G is is the maximum of the sum of the chromatic numbers of the parts. We derive a Heawood-type formula for the k-chromatic number of graphs embedded in a fixedsurface, improving the previously known upper bounds. In infinitely many cases, the new upper bound coincides with the lower bound obtained from embedding disjoint cliques in the surface. In the proof of this result, we derive a variant of Euler's Formula for union of several graphs that might be interesting independently.

Název v anglickém jazyce

$k$-chromatic number of graphs on surfaces

Popis výsledku anglicky

Considering all partitions of the edges of a graph G to k parts, the the k-chromatic number of G is is the maximum of the sum of the chromatic numbers of the parts. We derive a Heawood-type formula for the k-chromatic number of graphs embedded in a fixedsurface, improving the previously known upper bounds. In infinitely many cases, the new upper bound coincides with the lower bound obtained from embedding disjoint cliques in the surface. In the proof of this result, we derive a variant of Euler's Formula for union of several graphs that might be interesting independently.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

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í

2009

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

SIAM Journal on Discrete Mathematics

ISSN

0895-4801

e-ISSN

—

Svazek periodika

23

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

10

Strana od-do

—

Kód UT WoS článku

000263103400034

EID výsledku v databázi Scopus

—