About: Chromatic number and complete graph substructures for degree sequences

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

About: Chromatic number and complete graph substructures for degree sequences 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
rdfs:seeAlso	http://link.springer.com/article/10.1007%2Fs00493-013-2649-z
Description	Given a graphic degree sequence D, let χ(D) (respectively ω(D), h(D), and H(D)) denote the maximum value of the chromatic number (respectively, the size of the largest clique, largest clique subdivision, and largest clique minor) taken over all simple graphs whose degree sequence is D. It is proved that χ(D)LESS-THAN OR EQUAL TOh(D). Moreover, it is shown that a subdivision of a clique of order χ(D) exists where each edge is subdivided at most once and the set of all subdivided edges forms a collection of disjoint stars. This bound is an analogue of the Hajós Conjecture for degree sequences and, in particular, settles a conjecture of Neil Robertson that degree sequences satisfy the bound χ(D) LESS-THAN OR EQUAL TO H(D) (which is related to the Hadwiger Conjecture). It is also proved that χ(D) LESS-THAN OR EQUAL TO 6/5 ω(D)+ 3/5 and that χ(D) LESS-THAN OR EQUAL TO 4/5 ω(D) + 1/5 Δ(D)+1, where Δ(D) denotes the maximum degree in D. The latter inequality is related to a conjecture of Bruce Reed bounding the chromatic number by a convex combination of the clique number and the maximum degree. All derived inequalities are best possible. Given a graphic degree sequence D, let χ(D) (respectively ω(D), h(D), and H(D)) denote the maximum value of the chromatic number (respectively, the size of the largest clique, largest clique subdivision, and largest clique minor) taken over all simple graphs whose degree sequence is D. It is proved that χ(D)LESS-THAN OR EQUAL TOh(D). Moreover, it is shown that a subdivision of a clique of order χ(D) exists where each edge is subdivided at most once and the set of all subdivided edges forms a collection of disjoint stars. This bound is an analogue of the Hajós Conjecture for degree sequences and, in particular, settles a conjecture of Neil Robertson that degree sequences satisfy the bound χ(D) LESS-THAN OR EQUAL TO H(D) (which is related to the Hadwiger Conjecture). It is also proved that χ(D) LESS-THAN OR EQUAL TO 6/5 ω(D)+ 3/5 and that χ(D) LESS-THAN OR EQUAL TO 4/5 ω(D) + 1/5 Δ(D)+1, where Δ(D) denotes the maximum degree in D. The latter inequality is related to a conjecture of Bruce Reed bounding the chromatic number by a convex combination of the clique number and the maximum degree. All derived inequalities are best possible. (en)
Title	Chromatic number and complete graph substructures for degree sequences Chromatic number and complete graph substructures for degree sequences (en)
skos:prefLabel	Chromatic number and complete graph substructures for degree sequences Chromatic number and complete graph substructures for degree sequences (en)
skos:notation	RIV/00216208:11320/13:10159004!RIV14-GA0-11320___
http://linked.open...avai/predkladatel	Matematicko-fyzikální fakulta
http://linked.open...avai/riv/aktivita	P
http://linked.open...avai/riv/aktivity	P(GA201/09/0197)
http://linked.open...iv/cisloPeriodika	5
http://linked.open...vai/riv/dodaniDat	2014
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	65388
http://linked.open...ai/riv/idVysledku	RIV/00216208:11320/13:10159004
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	Hadwiger conjecture; degree sequence (en)
http://linked.open.../riv/klicoveSlovo	Hadwiger conjecture degree sequence
http://linked.open...odStatuVydavatele	DE - Spolková republika Německo
http://linked.open...ontrolniKodProRIV	[7B4EFFB985E1]
http://linked.open...i/riv/nazevZdroje	Combinatorica
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	Graph colorings and flows: structure and applications
http://linked.open...UplatneniVysledku	2013
http://linked.open...v/svazekPeriodika	33
http://linked.open...iv/tvurceVysledku	Dvořák, Zdeněk Mohar, Bojan
http://linked.open...ain/vavai/riv/wos	000328202500001
issn	0209-9683
number of pages	17 (xsd:int)
http://bibframe.org/vocab/doi	10.1007/s00493-013-2649-z
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