Chromatic number and complete graph substructures for degree sequences (Q485549)

Let \(D\) be a degree sequence and let \(\chi (D)\), \(\omega (D)\), \(h(D)\), and \(H(D)\) denote the maximum chromatic number, the maximum clique number, the size of the largest clique subdivision, and largest clique minor, respectively, over all simple graphs with the degree sequence \(D.\) Clearly, \(\omega (D)\leq h(D)\leq H(D).\) In the paper, a number of inequalities for the given four invariants is derived. Robertson (unpublished) conjectured that \(\chi (D)\leq H(D).\) The main result of the paper states that \(\chi (D)\leq h(D).\)