A graph where each vertex v has a list L(v) of available colors is L-colorable if there is a proper coloring such that the color of v is in L(v) for each v. A graph is k-choosable if every assignment L of at least k colors to each vertex guarantees an L-coloring. Given a list assignment L, an L-request for a vertex v is a color c∈L(v). In this paper, we look at a variant of the widely studied class of precoloring extension problems from Dvořák, Norin, and Postle (J. Graph Theory, 2019), wherein one must satisfy “enough”, as opposed to all, of the requested set of precolors. A graph G is ɛ-flexible for list size k if for any k-list assignment L, and any set S of L-requests, there is an L-coloring of G satisfying ɛ-fraction of the requests in S. It is conjectured that planar graphs are ɛ-flexible for list size 5, yet it is proved only for list size 6 and for certain subclasses of planar graphs. We give a stronger version of the main tool used in the proofs of the aforementioned results. By doing so, we improve upon a result by Masařík and show that planar graphs without K4− are ɛ-flexible for list size 5. We also prove that planar graphs without 4-cycles and 3-cycle distance at least 2 are ɛ-flexible for list size 4. Finally, we introduce a new (slightly weaker) form of ɛ-flexibility where each vertex has exactly one request. In that setting, we provide a stronger tool and we demonstrate its usefulness to further extend the class of graphs that are ɛ-flexible for list size 5.

A graphic sequence $\pi$ is potentially $H$-graphic if there is some realization of $\pi$ that contains $H$ as a subgraph. The Erdös--Jacobson--Lehel problem asks one to determine $\sigma(H,n)$, the minimum even integer such that any $n$-term graphic sequence $\pi$ with sum at least $\sigma(H,n)$ is potentially $H$-graphic. The parameter $\sigma(H,n)$ is known as the potential function of $H$, and can be viewed as a degree sequence variant of the classical extremal function ${ex}(n,H)$. Recently, Ferrara et al. [ Combinatorica 36 (2016), pp. 687--702] determined $\sigma(H,n)$ asymptotically for all $H$, which is analogous to the Erdös--Stone--Simonovits theorem that determines ${ex}(n,H)$ asymptotically for nonbipartite $H$. In this paper, we investigate a stability concept for the potential number, inspired by Simonovits' classical result on the stability of the extremal function. We first define a notion of stability for the potential number that is a natural analogue to the stability given by Simonovits. However, under this definition, many families of graphs are not $\sigma$-stable, establishing a stark contrast between the extremal and potential functions. We then give a sufficient condition for a graph $H$ to be stable with respect to the potential function, and characterize the stability of those graphs $H$ that contain an induced subgraph of order $\alpha(H)+1$ with exactly one edge.

A sequence $\pi=(d_1,\ldots,d_n)$ is graphic if there is a simple graph $G$ with vertex set $\{v_1,\ldots,v_n\}$ such that the degree of $v_i$ is $d_i$. We say that graphic sequences $\pi_1=(d_1^{(1)},\ldots,d_n^{(1)})$ and $\pi_2=(d_1^{(2)},\ldots,d_n^{(2)})$ pack if there exist edge-disjoint $n$-vertex graphs $G_1$ and $G_2$ such that for $j\in\{1,2\}$, $d_{G_j}(v_i)=d_i^{(j)}$ for all $i\in\{1,\ldots,n\}$. Here, we prove several extremal degree sequence packing theorems that parallel central results and open problems from the graph packing literature. Specifically, the main result of this paper implies degree sequence packing analogues to the Bollobás--Eldridge--Catlin graph packing conjecture and the classical graph packing theorem of Sauer and Spencer. In discrete tomography, a branch of discrete imaging science, the goal is to reconstruct discrete objects using data acquired from low-dimensional projections. Specifically, in the $k$-color discrete tomography problem the goal is to color the entries of an $m\times n$ matrix using $k$ colors so that each row and column receives a prescribed number of entries of each color. This problem is equivalent to packing the degree sequences of $k$ bipartite graphs with parts of sizes $m$ and $n$. Here we also prove several Sauer--Spencer-type theorems with applications to the two-color discrete tomography problem.

We consider a variation of the classical Turán-type extremal problem as introduced by Erdős, Jacobson, and Lehel in [Graphs realizing the same degree sequences and their respective clique numbers, in Graph Theory, Combinatorics, and Applications, Vol. 1, Wiley, New York, 1991, pp. 439–449]. Let $\pi$ be an n-element graphic sequence and $\sigma(\pi)$ be the sum of the terms in $\pi$, that is, the degree sum. Let H be a graph. We wish to determine the smallest m such that any n-term graphic sequence $\pi$ having $\sigma(\pi)\geq m$ has some realization containing H as a subgraph. Denote this value m by $\sigma(H,n)$. For an arbitrarily chosen H, we construct a graphic sequence $\pi^*(H,n)$ such that $\sigma(\pi^*(H,n))+2\le\sigma(H,n)$. Furthermore, we conjecture that equality holds in general, as this is the case for all choices of H where $\sigma(H,n)$ is currently known. We support this conjecture by examining those graphs that are the complement of triangle-free graphs and showing that the conjecture holds despite the wide variety of structure in this class. We will conclude with a brief discussion of a connection between potentially H-graphic sequences and H-saturated graphs of minimum size.