Search

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\in L(v)$. In this paper, we look at a variant of the widely studied class of precoloring extension problems from [Z. Dvo\v{r}\'ak, S. Norin, and L. Postle: List coloring with requests. J. Graph Theory 2019], wherein one must satisfy "enough", as opposed to all, of the requested set of precolors. A graph $G$ is $\varepsilon$-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 an $\varepsilon$-fraction of the requests in $S$. It is conjectured that planar graphs are $\varepsilon$-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\v{r}\'ik and show that planar graphs without $K_4^-$ are $\varepsilon$-flexible for list size $5$. We also prove that planar graphs without $4$-cycles and $3$-cycle distance at least 2 are $\varepsilon$-flexible for list size $4$. Finally, we introduce a new (slightly weaker) form of $\varepsilon$-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 $\varepsilon$-flexible for list size $5$., Comment: 18 pages, 4 figures

A graphic sequence $\pi$ is potentially $H$-graphic if there is some realization of $\pi$ that contains $H$ as a subgraph. The Erd\H{o}s-Jacobson-Lehel problem asks 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 ${\rm ex}(n,H)$. Recently, Ferrara, LeSaulnier, Moffatt and Wenger [On the sum necessary to ensure that a degree sequence is potentially $H$-graphic, Combinatorica 36 (2016), 687--702] determined $\sigma(H,n)$ asymptotically for all $H$, which is analogous to the Erd\H{o}s-Stone-Simonovits Theorem that determines ${\rm 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., Comment: 20 pages, 3 figures

Inspired by a 1987 result of Hanson and Toft [Edge-colored saturated graphs, J Graph Theory 11 (1987), 191–196] and several recent results, we consider the following saturation problem for edge-colored graphs. An edge-coloring of a graph F is rainbow if every edge of F receives a different color. Let R(F) denote the set of rainbow-colored copies of F. A t-edge-colored graph G is (R(F),t)-saturated if G does not contain a rainbow copy of F but for any edge e∈E(G¯) and any color i∈[t], the addition of e to G in color i creates a rainbow copy of F. Let sat t(n,R(F)) denote the minimum number of edges in an (R(F),t)-saturated graph of order n. We call this the rainbow saturation number of F. In this article, we prove several results about rainbow saturation numbers of graphs. In stark contrast with the related problem for monochromatic subgraphs, wherein the saturation is always linear in n, we prove that rainbow saturation numbers have a variety of different orders of growth. For instance, the rainbow saturation number of the complete graph Kn lies between nlogn/loglogn and nlogn, the rainbow saturation number of an n-vertex star is quadratic in n, and the rainbow saturation number of any tree that is not a star is at most linear.

Given a graph H, a graphic sequence ź is potentially H-graphic if there is some realization of ź that contains H as a subgraph. In 1991, Erdźs, Jacobson and Lehel posed the following question: Determine the minimum even integer ź(H,n) such that every n-term graphic sequence with sum at least ź(H,n) is potentially H-graphic. This problem can be viewed as a "potential" degree sequence relaxation of the (forcible) Turan problems. While the exact value of ź(H,n) has been determined for a number of specific classes of graphs (including cliques, cycles, complete bigraphs and others), very little is known about the parameter for arbitrary H. In this paper, we determine ź(H,n) asymptotically for all H, thereby providing an Erdźs-Stone-Simonovits-type theorem for the Erdźs-Jacobson-Lehel problem.

Given k ≥ 1, a k-proper partition of a graph G is a partition P of V (G) such that each part P of P induces a k-connected subgraph of G. We prove that if G is a graph of order n such that �(G) ≥ √ n, then G has a 2-proper partition with at most n/�(G) parts. The bounds on the number of parts and the minimum degree are both best possible. We then prove that If G is a graph of order n with minimum degree �(G) ≥ p c(k − 1)n, where c = 2123 180 , then G has a k-proper partition into at most cn δ(G) parts. This improves a result of Ferrara, Magnant and Wenger [Conditions for Families of Disjoint k-connected Subgraphs in a Graph, Discrete Math. 313 (2013), 760– 764] and both the degree condition and the number of parts are best possible up to the constant c.

Given a poset P , a family F of elements in the Boolean lattice is said to be P -saturated if (1) F contains no copy of P as a subposet and (2) every proper superset of F contains a copy of P as a subposet. The maximum size of a P -saturated family is denoted by La ( n , P ) , which has been studied for a number of choices of P . The minimum size of a P -saturated family, sat ( n , P ) , was introduced by Gerbner et al. (2013), and parallels the deep literature on the saturation function for graphs. We introduce and study the concept of saturation for induced subposets. As opposed to induced saturation in graphs, the above definition of saturation for posets extends naturally to the induced setting. We give several exact results and a number of bounds on the induced saturation number for several small posets. We also use a transformation to the biclique cover problem to prove a logarithmic lower bound for a rich infinite family of target posets.

Let π 1 = ( d 1 ( 1 ) , … , d n ( 1 ) ) and π 2 = ( d 1 ( 2 ) , … , d n ( 2 ) ) be graphic sequences. We say they pack if there exist edge-disjoint realizations G 1 and G 2 of π 1 and π 2 , respectively, on vertex set { v 1 , … , v n } such that for j ∈ { 1 , 2 } , d G j ( v i ) = d i ( j ) for all i ∈ { 1 , … , n } . In this case, we say that ( G 1 , G 2 ) is a ( π 1 , π 2 ) -packing. A clear necessary condition for graphic sequences π 1 and π 2 to pack is that π 1 + π 2 , their componentwise sum, is also graphic. It is known, however, that this condition is not sufficient, and furthermore that the general problem of determining if two sequences pack is N P -complete. S. Kundu proved in 1973 that if π 2 is almost regular, that is each element is from { k − 1 , k } , then π 1 and π 2 pack if and only if π 1 + π 2 is graphic. In this paper we will consider graphic sequences π with the property that π + 1 is graphic. By Kundu’s theorem, the sequences π and 1 pack, and there exist edge-disjoint realizations G and I , where I is a 1-factor. We call such a ( π , 1 ) packing a Kundu realization. Assume that π is a graphic sequence, in which each term is at most n ∕ 24 , that packs with 1 . This paper contains two results. On one hand, any two Kundu realizations of the degree sequence π + 1 can be transformed into each other through a sequence of other Kundu realizations by swap operations. On the other hand, the same conditions ensure that any particular 1-factor can be part of a Kundu realization of π + 1 .

A graph G is H-saturated if G does not contain H as a subgraph but for any nonadjacent vertices u and v, G+uv contains H as a subgraph. The parameter sat(H,n) is the minimum number of edges in an H-saturated graph of order n. In this paper, we determine sat(H,n) for sufficiently large n when H is a union of cliques of the same order, an arbitrary union of two cliques and a generalized friendship graph.

A nonincreasing sequence of nonnegative integers @p=(d"1,d"2,...,d"n) is graphic if there is a (simple) graph G of order n having degree sequence @p. In this case, G is said to realize@p. For a given graph H, a graphic sequence @p is potentiallyH-graphic if there is some realization of @p containing H as a (weak) subgraph. Let @s(@p) denote the sum of the terms of @p. For a graph H and n@?Z^+, @s(H,n) is defined as the smallest even integer m so that every n-term graphic sequence @p with @s(@p)>=m is potentially H-graphic. Let K"s^t denote the complete t partite graph such that each partite set has exactly s vertices. We show that @s(K"s^t,n)=@s(K"("t"-"2")"s+K"s","s,n) and obtain the exact value of @s(K"j+K"s","s,n) for n sufficiently large. Consequently, we obtain the exact value of @s(K"s^t,n) for n sufficiently large.

A star $k$-coloring is a proper $k$-coloring where the union of two color classes induces a star forest. While every planar graph is 4-colorable, not every planar graph is star 4-colorable. One method to produce a star 4-coloring is to partition the vertex set into a 2-independent set and a forest; such a partition is called an I,F-partition. We use a combination of potential functions and discharging to prove that every graph with maximum average degree less than $\frac{5}{2}$ has an I,F-partition, which is sharp and answers a question of Cranston and West [A guide to the discharging method, arXiv:1306.4434]. This result implies that planar graphs of girth at least 10 are star 4-colorable, improving upon previous results of Bu, Cranston, Montassier, Raspaud, and Wang [Star coloring of sparse graphs, J. Graph Theory 62 (2009), 201-219]., Comment: 11 pages, 6 figures

Let $G$ be a fixed graph and let ${\mathcal F}$ be a family of graphs. A subgraph $J$ of $G$ is ${\mathcal F}$-saturated if no member of ${\mathcal F}$ is a subgraph of $J$, but for any edge $e$ in $E(G)-E(J)$, some element of ${\mathcal F}$ is a subgraph of $J+e$. We let $\text{ex}({\mathcal F},G)$ and $\text{sat}({\mathcal F},G)$ denote the maximum and minimum size of an ${\mathcal F}$-saturated subgraph of $G$, respectively. If no element of ${\mathcal F}$ is a subgraph of $G$, then $\text{sat}({\mathcal F},G) = \text{ex}({\mathcal F}, G) = |E(G)|$. In this paper, for $k\ge 3$ and $n\ge 100$ we determine $\text{sat}(K_3,K_k^n)$, where $K_k^n$ is the complete balanced $k$-partite graph with partite sets of size $n$. We also give several families of constructions of $K_t$-saturated subgraphs of $K_k^n$ for $t\ge 4$. Our results and constructions provide an informative contrast to recent results on the edge-density version of $\text{ex}(K_t,K_k^n)$ from [A. Bondy, J. Shen, S. Thomass\'e, and C. Thomassen, Density conditions for triangles in multipartite graphs, Combinatorica 26 (2006), 121--131] and [F. Pfender, Complete subgraphs in multipartite graphs, Combinatorica 32 (2012), no. 4, 483--495]., Comment: 16 pages, 4 figures

Given a group $\Gamma$ acting on a set $X$, a $k$-coloring $\phi:X\to\{1,\dots,k\}$ of $X$ is distinguishing with respect to $\Gamma$ if the only $\gamma\in \Gamma$ that fixes $\phi$ is the identity action. The distinguishing number of the action $\Gamma$, denoted $D_{\Gamma}(X)$, is then the smallest positive integer $k$ such that there is a distinguishing $k$-coloring of $X$ with respect to $\Gamma$. This notion has been studied in a number of settings, but by far the largest body of work has been concerned with finding the distinguishing number of the action of the automorphism group of a graph $G$ upon its vertex set, which is referred to as the distinguishing number of $G$. The distinguishing number of a group action is a measure of how difficult it is to "break" all of the permutations arising from that action. In this paper, we aim to further differentiate the resilience of group actions with the same distinguishing number. In particular, we introduce a precoloring extension framework to address this issue. A set $S \subseteq X$ is a fixing set for $\Gamma$ if for every non-identity element $\gamma \in \Gamma$ there is an element $s \in S$ such that $\gamma(s) \neq s$. The distinguishing extension number $\operatorname{ext}_D(X,\Gamma;k)$ is the minimum number $m$ such that for all fixing sets $W \subseteq X$ with $|W| \geq m$, every $k$-coloring $c : X \setminus W \to [k]$ can be extended to a $k$-coloring that distinguishes $X$. In this paper, we prove that $\operatorname{ext}_D(\mathbb{R},\operatorname{Aut}(\mathbb{R}),2) =4$, where $\operatorname{Aut}(\mathbb{R})$ is comprised of compositions of translations and reflections. We also consider the distinguishing extension number of the circle and (finite) cycles, obtaining several exact results and bounds., Comment: 21 pages, 4 figures

A sequence of nonnegative integers $\pi$ is {\it graphic} if it is the degree sequence of some graph $G$. In this case we say that $G$ is a \textit{realization} of $\pi$, and we write $\pi=\pi(G)$. A graphic sequence $\pi$ is {\it potentially $H$-graphic} if there is a realization of $\pi$ that contains $H$ as a subgraph. Given nonincreasing graphic sequences $\pi_1=(d_1,\ldots,d_n)$ and $\pi_2 = (s_1,\ldots,s_n)$, we say that $\pi_1$ {\it majorizes} $\pi_2$ if $d_i \geq s_i$ for all $i$, $1 \leq i \leq n$. In 1970, Erd\H{o}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^*(H)$ such that if $\pi$ is a graphic sequence that is not potentially $H$-graphic, then $\pi$ is close to being majorized by $\pi^*(H)$. Similar to the role played by complete multipartite graphs in the traditional extremal setting, the sequence $\pi^*(H)$ asymptotically gives the maximum possible sum of a graphic sequence $\pi$ that is not potentially $H$-graphic., Comment: 19 pages

The strong chromatic index of a graph $G$, denoted $\chi_s'(G)$, is the least number of colors needed to edge-color $G$ so that edges at distance at most two receive distinct colors. The strong list chromatic index, denoted $\chi_{s,\ell}'(G)$, is the least integer $k$ such that if arbitrary lists of size $k$ are assigned to each edge then $G$ can be edge-colored from those lists where edges at distance at most two receive distinct colors. We use the discharging method, the Combinatorial Nullstellensatz, and computation to show that if $G$ is a subcubic planar graph with $\operatorname{girth}(G) \geq 41$ then $\chi_{s,\ell}'(G) \leq 5$, answering a question of Borodin and Ivanova [Precise upper bound for the strong edge chromatic number of sparse planar graphs, Discuss. Math. Graph Theory, 33(4), (2014) 759--770]. We further show that if $G$ is a subcubic planar graph and $\operatorname{girth}(G) \geq 30$, then $\chi_s'(G) \leq 5$, improving a bound from the same paper. Finally, if $G$ is a planar graph with maximum degree at most four and $\operatorname{girth}(G) \geq 28$, then $\chi_s'(G) \leq 7$, improving a more general bound of Wang and Zhao from [Odd graphs and its application on the strong edge coloring, arXiv:1412.8358] in this case., Comment: 15 pages, 10 figures