On image-minors in graphs with given average degree Original Research Article

Let image be the minimum d such that every graph G with average degree d has an H-minor. Myers and Thomason found good bounds on image for almost all graphs H and proved that for ‘balanced’ H random graphs provide extremal examples and determine the extremal function. Examples of ‘unbalanced graphs’ are complete bipartite graphs image for a fixed s and large t. Myers proved upper bounds on image and made a conjecture on the order of magnitude of image for a fixed s and image. He also found exact values for image for an infinite series of t. In this paper, we confirm the conjecture of Myers and find asymptotically (in s) exact bounds on image for a fixed s and large t.