About: $k$-chromatic number of graphs on surfaces

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: $k$-chromatic number of graphs on surfaces Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
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 fixed surface, 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. 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 fixed surface, 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. (en)
Title	$k$-chromatic number of graphs on surfaces $k$-chromatic number of graphs on surfaces (en)
skos:prefLabel	$k$-chromatic number of graphs on surfaces $k$-chromatic number of graphs on surfaces (en)
skos:notation	RIV/00216208:11320/09:00207123!RIV10-MSM-11320___
http://linked.open...avai/riv/aktivita	P
http://linked.open...avai/riv/aktivity	P(1M0545), P(MEB090805)
http://linked.open...iv/cisloPeriodika	1
http://linked.open...vai/riv/dodaniDat	2010
http://linked.open...aciTvurceVysledku	Dvořák, Zdeněk
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Univerzita Karlova v Praze / Matematicko-fyzikální fakulta
http://linked.open...dnocenehoVysledku	321634
http://linked.open...ai/riv/idVysledku	RIV/00216208:11320/09:00207123
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	$k$-chromatic; number; graphs; surfaces (en)
http://linked.open.../riv/klicoveSlovo	$k$-chromatic number graphs surfaces
http://linked.open...odStatuVydavatele	US - Spojené státy americké
http://linked.open...ontrolniKodProRIV	[D3D140D6E43A]
http://linked.open...i/riv/nazevZdroje	SIAM Journal on Discrete Mathematics
http://linked.open...in/vavai/riv/obor	BA
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	2 (xsd:int)
http://linked.open...vavai/riv/projekt	Structure of planar graphs and applications to graph colorings and frequency assignment Institute for Theoretical Computer Science
http://linked.open...UplatneniVysledku	2009
http://linked.open...v/svazekPeriodika	23
http://linked.open...iv/tvurceVysledku	Dvořák, Zdeněk Škrekovski, Riste
http://linked.open...ain/vavai/riv/wos	000263103400034
issn	0895-4801
number of pages	10 (xsd:int)
http://localhost/t...ganizacniJednotka	11320

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software