"Hadwiger conjecture; degree sequence"@en . "DE - Spolkov\u00E1 republika N\u011Bmecko" . "65388" . "Combinatorica" . "Dvo\u0159\u00E1k, Zden\u011Bk" . "Chromatic number and complete graph substructures for degree sequences" . "Given a graphic degree sequence D, let \u03C7(D) (respectively \u03C9(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 \u03C7(D)LESS-THAN OR EQUAL TOh(D). Moreover, it is shown that a subdivision of a clique of order \u03C7(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\u00F3s Conjecture for degree sequences and, in particular, settles a conjecture of Neil Robertson that degree sequences satisfy the bound \u03C7(D) LESS-THAN OR EQUAL TO H(D) (which is related to the Hadwiger Conjecture). It is also proved that \u03C7(D) LESS-THAN OR EQUAL TO 6/5 \u03C9(D)+ 3/5 and that \u03C7(D) LESS-THAN OR EQUAL TO 4/5 \u03C9(D) + 1/5 \u0394(D)+1, where \u0394(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 . "RIV/00216208:11320/13:10159004" . "Chromatic number and complete graph substructures for degree sequences" . "Given a graphic degree sequence D, let \u03C7(D) (respectively \u03C9(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 \u03C7(D)LESS-THAN OR EQUAL TOh(D). Moreover, it is shown that a subdivision of a clique of order \u03C7(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\u00F3s Conjecture for degree sequences and, in particular, settles a conjecture of Neil Robertson that degree sequences satisfy the bound \u03C7(D) LESS-THAN OR EQUAL TO H(D) (which is related to the Hadwiger Conjecture). It is also proved that \u03C7(D) LESS-THAN OR EQUAL TO 6/5 \u03C9(D)+ 3/5 and that \u03C7(D) LESS-THAN OR EQUAL TO 4/5 \u03C9(D) + 1/5 \u0394(D)+1, where \u0394(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." . "5" . . "Chromatic number and complete graph substructures for degree sequences"@en . "P(GA201/09/0197)" . "[7B4EFFB985E1]" . "0209-9683" . . "17"^^ . . "Mohar, Bojan" . . . "http://link.springer.com/article/10.1007%2Fs00493-013-2649-z" . . . "11320" . . "Chromatic number and complete graph substructures for degree sequences"@en . . "1"^^ . "000328202500001" . . "33" . . "10.1007/s00493-013-2649-z" . "RIV/00216208:11320/13:10159004!RIV14-GA0-11320___" . . . . "2"^^ . .