-
Chromatic number and complete graph substructures for degree sequences [Elektronski vir]Dvořák, Zdeněk ; Mohar, Bojan, 1956-Given a graphic degree sequence ▫$D$▫, let ▫$\chi(D)$▫ (respectively ▫$\omega(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 ▫$\chi(D)\le h(D)$▫. Moreover, it is shown that a subdivision of a clique of order ▫$\chi(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 ▫$\chi(D) \le H(D)$▫ (which is related to the Hadwiger Conjecture). It is also proved that ▫$\chi(D) \le \frac{6}{5} \,\omega(D) + \frac{3}{5}$▫ and that ▫$\chi(D) \le \frac{4}{5}\omega(D) + \frac{1}{5}\Delta(D) + 1$▫, where ▫$\Delta(D)$▫ denotes the maximum degree in ▫$D$▫. The latter inequality is a strengthened version of a conjecture of Bruce Reed. All derived inequalities are best possible.Vir: Preprint series. - ISSN 1318-4865 (Vol. 47, št. 1098, 2009, str. 1-15)Vrsta gradiva - e-članekLeto - 2009Jezik - angleškiCOBISS.SI-ID - 15245913
Avtor
Dvořák, Zdeněk |
Mohar, Bojan, 1956-
Teme
matematika |
teorija grafov |
zaporedje stopenj |
maksimalna klika |
klični minor |
klična subdivizija |
Hajóševa domneva |
Hadwigerjeva domneva |
Reedova domneva |
mathematics |
graph theory |
degree sequence |
maximun cligue |
clique number |
Hajós conjecture |
Hadwiger conjecture |
Reed conjecture
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|---|
Dvořák, Zdeněk | |
Mohar, Bojan, 1956- | 01931 |
Izberite prevzemno mesto:
Prevzem gradiva po pošti
Obvestilo
Gesla v Splošnem geslovniku COBISS
Izbira mesta prevzema
Mesto prevzema | Status gradiva | Rezervacija |
---|
Prosimo, počakajte trenutek.