Journal of Combinatorics

Volume 10 (2019)

Number 2

On the approximate shape of degree sequences that are not potentially $H$-graphic

Pages: 339 – 363

DOI: https://dx.doi.org/10.4310/JOC.2019.v10.n2.a9

Authors

Catherine Erbes (Department of Mathematics, Hiram College, Hiram, Ohio, U.S.A.)

Michael Ferrara (Department of Mathematical and Statistical Sciences, University of Colorado, Denver, Co., U.S.A.)

Ryan R. Martin (Department of Mathematics, Iowa State University, Ames, Ia., U.S.A.)

Paul S. Wenger (School of Mathematical Sciences, Rochester Institute of Technology, Rochester, New York, U.S.A.)

Abstract

A sequence of nonnegative integers $\pi$ is graphic if it is the degree sequence of some graph $G$. In this case we say that $G$ is a realization of $\pi$, and we write $\pi = \pi (G)$. A graphic sequence $\pi$ is potentially $H$-graphic if there is a realization of $\pi$ that contains $H$ as a subgraph.

Given non-increasing graphic sequences $\pi_1 = (d_1, \dotsc , d_n)$ and $\pi_2 = (s_1, \dotsc , s_n)$, we say that $\pi_1$ majorizes $\pi_2$ if $d_i \geq s_i$ for all $i , 1 \leq i \leq n$. In 1970, Erdős showed that for any $K_{r+1}$-free graph $H$, there exists an $r$-partite graph $G$ such that $\pi (G)$ majorizes $\pi (H)$. In 2005, Pikhurko and Taraz generalized this notion and showed that for any graph $F$ with chromatic number $r + 1$, the degree sequence of an $F$-free graph is, in an appropriate sense, nearly majorized by the degree sequence of an $r$-partite graph.

In this paper, we give similar results for degree sequences that are not potentially $H$-graphic. In particular, there is a graphic sequence $\pi ^{\ast} (H)$ such that if $\pi$ is a graphic sequence that is not potentially $H$-graphic, then $\pi$ is close to being majorized by $\pi ^{\ast} (H)$. Similar to the role played by complete multipartite graphs in the traditional extremal setting, the sequence $\pi ^{\ast} (H)$ asymptotically gives the maximum possible sum of a graphic sequence $\pi$ that is not potentially $H$-graphic.

Keywords

potentially $H$-graphic

2010 Mathematics Subject Classification

Primary 05C07. Secondary 05C35.

Received 25 March 2013

Published 25 January 2019