Mathematics – Combinatorics
Scientific paper
2009-07-09
Mathematics
Combinatorics
Scientific paper
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 Hajos 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 {6/5}\omega(D)+{3/5}$ and that $\chi(D) \le {4/5}\omega(D) + {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.
Dvořák Zdeněk
Mohar Bojan
No associations
LandOfFree
Chromatic number and complete graph substructures for degree sequences does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Chromatic number and complete graph substructures for degree sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Chromatic number and complete graph substructures for degree sequences will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-341947