Contents Online

# 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

#### 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.

The first author’s research was supported in part by UCD GK12 Transforming Experiences Project, National Science Foundation Grant DGE-0742434.

The second author’s research was supported in part by Simons Foundation Collaboration Grant #206692.

The third author’s research was supported in part by National Science Foundation grant DMS-0901008 and by National Security Agency grant H98230-13-1-0226.

Received 25 March 2013

Published 25 January 2019