-
Chromatic number and complete graph substructures for degree sequencesDvořá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 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.Source: Combinatorica. - ISSN 0209-9683 (Vol. 33, no. 5, 2013, str. 513-529)Type of material - article, component partPublish date - 2013Language - englishCOBISS.SI-ID - 16922713
Author
Dvořák, Zdeněk |
Mohar, Bojan, 1956-
Topics
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 |
maximum clique |
clique minor |
clique subdivision |
Hajos Conjecture |
Hadwiger Conjecture |
Reed Conjecture
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|---|
Dvořák, Zdeněk | |
Mohar, Bojan, 1956- | 01931 |
Select pickup location:
Material pickup by post
Notification
Subject headings in COBISS General List of Subject Headings
Select pickup location
Pickup location | Material status | Reservation |
---|
Please wait a moment.