$k$-chromatic number of graphs on surfaces

Result code in 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>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

$k$-chromatic number of graphs on surfaces

Original language description

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.

Czech name

—

Czech description

—

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

BA - General mathematics

OECD FORD branch

—

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

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

Publication year

2009

Confidentiality

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

Name of the periodical

SIAM Journal on Discrete Mathematics

ISSN

0895-4801

e-ISSN

—

Volume of the periodical

23

Issue of the periodical within the volume

1

Country of publishing house

US - UNITED STATES

Number of pages

10

Pages from-to

—

UT code for WoS article

000263103400034

EID of the result in the Scopus database

—