Name
Abstract | ||
|---|---|---|
For a degree sequence $$d:d_1\\ge \\cdots \\ge d_n$$d:d1¿¿¿dn, we consider the smallest chromatic number $$\\chi _{\\min }(d)$$¿min(d) and the largest chromatic number $$\\chi _{\\max }(d)$$¿max(d) among all graphs with degree sequence d. We show that if $$d_n\\ge 1$$dn¿1, then $$\\chi _{\\min }(d)\\le \\max \\left\\{ 3,d_1-\\frac{n+1}{4d_1}+4\\right\\} $$¿min(d)≤max3,d1-n+14d1+4, and, if $$\\sqrt{n+\\frac{1}{4}}-\\frac{1}{2}d_1\\ge d_n\\ge 1$$n+14-12d1¿dn¿1, then $$\\chi _{\\max }(d)=\\max \\nolimits _{i\\in [n]}\\min \\left\\{ i,d_i+1\\right\\} $$¿max(d)=maxi¿[n]mini,di+1. For a given degree sequence d with bounded entries, we show that $$\\chi _{\\min }(d), \\chi _{\\max }(d)$$¿min(d),¿max(d), and also the smallest independence number $$\\alpha _{\\min }(d)$$¿min(d) among all graphs with degree sequence d, can be determined in polynomial time. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/s00373-017-1814-3 | Graphs and Combinatorics |
Keywords | Field | DocType |
Degree sequence, Chromatic number, Independence number, 05C07, 05C15, 05C69 | Discrete mathematics,Graph,Independence number,Combinatorics,Chromatic scale,Degree (graph theory),Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
33 | 4 | 0911-0119 |
Citations | PageRank | References |
0 | 0.34 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stéphane Bessy | 1 | 117 | 19.68 |
| Dieter Rautenbach | 2 | 946 | 138.87 |