Source author record

Michael Ferrara

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

12works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2019arXiv

Ore and Chvátal-type Degree Conditions for Bootstrap Percolation from Small Sets

Bootstrap percolation is a deterministic cellular automaton in which vertices of a graph~ $G$ begin in one of two states, "dormant" or "active". Given a fixed integer $r$ , a dormant vertex becomes active if at any stage it has at least $r$ active neighbors, and it remains active for the duration of the process. Given an initial set of active vertices $A$ , we say that $G$ $r$ -percolates (from $A$ ) if every vertex in $G$ becomes active after some number of steps. Let $m(G,r)$ denote the minimum size of a set $A$ such that $G$ $r$ -percolates from $A$ . Bootstrap percolation has been studied in a number of settings, and has applications to both statistical physics and discrete epidemiology. Here, we are concerned with degree-based density conditions that ensure $m(G,2)=2$ . In particular, we give an Ore-type degree sum result that states that if a graph $G$ satisfies $σ_2(G)\ge n-2$ , then either $m(G,2)=2$ or $G$ is in one of a small number of classes of exceptional graphs. We also give a Chvátal-type degree condition: If $G$ is a graph with degree sequence $d_1\le d_2\le\dots\le d_n$ such that $d_i \geq i+1$ or $d_{n-i} \geq n-i-1$ for all $1 \leq i < \frac{n}{2}$ , then $m(G,2)=2$ or $G$ falls into one of several specific exceptional classes of graphs. Both of these results are inspired by, and extend, an Ore-type result in [D. Freund, M. Poloczek, and D. Reichman, Contagious sets in dense graphs, to appear in European J. Combin.]

preprint2017arXiv

Navigating Between Packings of Graphic Sequences

Let $π_1=(d_1^{(1)}, \ldots,d_n^{(1)})$ and $π_2=(d_1^{(2)},\ldots,d_n^{(2)})$ be graphic sequences. We say they \emph{pack} if there exist edge-disjoint realizations $G_1$ and $G_2$ of $π_1$ and $π_2$ , respectively, on vertex set $\{v_1,\dots,v_n\}$ such that for $j\in\{1,2\}$ , $d_{G_j}(v_i)=d_i^{(j)}$ for all $i\in\{1,\ldots,n\}$ . In this case, we say that $(G_1,G_2)$ is a $(π_1,π_2)$ -\textit{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 $NP$ - 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 $π+\mathbf{1}$ is graphic. By Kundu's theorem, the sequences $π$ and $\mathbf{1}$ pack, and there exist edge-disjoint realizations $G$ and $\mathcal{I}$ , where $\mathcal{I}$ is a 1-factor. We call such a $(π,\mathbf{1})$ packing a {\em Kundu realization}. Assume that $π$ is a graphic sequence, in which each term is at most $n/24$ , that packs with $\mathbf{1}$ . This paper contains two results. On one hand, any two Kundu realizations of the degree sequence $π+\mathbf{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 $π+\mathbf{1}$ .

preprint2015arXiv

Chvátal-type results for degree sequence Ramsey numbers

A sequence of nonnegative integers $π=(d_1,d_2,...,d_n)$ is graphic if there is a (simple) graph $G$ of order $n$ having degree sequence $π$ . In this case, $G$ is said to realize or be a realization of $π$ . Given a graph $H$ , a graphic sequence $π$ is potentially $H$ -graphic if there is some realization of $π$ that contains $H$ as a subgraph. In this paper, we consider a degree sequence analogue to classical graph Ramsey numbers. For graphs $H_1$ and $H_2$ , the potential-Ramsey number $r_{pot}(H_1,H_2)$ is the minimum integer $N$ such that for any $N$ -term graphic sequence $π$ , either $π$ is potentially $H_1$ -graphic or the complementary sequence $\overlineπ=(N-1-d_N,\dots, N-1-d_1)$ is potentially $H_2$ -graphic. We prove that if $s\ge 2$ is an integer and $T_t$ is a tree of order $t> 7(s-2)$ , then $r_{pot}(K_s, T_t) = t+s-2.$ This result, which is best possible up to the bound on $t$ , is a degree sequence analogue to a classical 1977 result of Chvátal on the graph Ramsey number of trees vs. cliques. To obtain this theorem, we prove a sharp condition that ensures an arbitrary graph packs with a forest, which is likely to be of independent interest.

preprint2015arXiv

I,F-partitions of Sparse Graphs

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

preprint2015arXiv

On the Strong Chromatic Index of Sparse Graphs

The strong chromatic index of a graph $G$ , denoted $χ_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 $χ_{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 $χ_{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 $χ_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 $χ_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.

preprint2015arXiv

On the Sum Neccesary to Ensure that a Degree Sequence is Potentially H-Graphic

A sequence of nonnegative integers π=(d_1,d_2,...,d_n) is graphic if there is a (simple) graph G with degree sequence π. In this case, G is said to realize or be a realization of π. Degree sequence results in the literature generally fall into two classes: forcible problems, in which all realizations of a graphic sequence must have a given property, and potential problems, in which at least one realization of πmust have the given property. 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 integer σ(H,n) such that every n-term graphic sequence with sum at least σ(H,n) is potentially H-graphic. As the sum of the terms of πis twice the number of edges in any realization of π, the Erdős-Jacobson-Lehel problem can be viewed as a potential degree sequence relaxation of the (forcible) Turán problem, wherein one wishes to determine the maximum number of edges in a graph that contains no copy of H. 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.

preprint2015arXiv

Partitioning a graph into highly connected subgraphs

Given $k\ge 1$ , a $k$ -proper partition of a graph $G$ is a partition ${\mathcal P}$ of $V(G)$ such that each part $P$ of ${\mathcal P}$ induces a $k$ -connected subgraph of $G$ . We prove that if $G$ is a graph of order $n$ such that $δ(G)\ge \sqrt{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)\ge\sqrt{c(k-1)n}$ , where $c=\frac{2123}{180}$ , then $G$ has a $k$ -proper partition into at most $\frac{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$ .

preprint2014arXiv

Extending Precolorings to Distinguish Group Actions

Given a group $Γ$ acting on a set $X$ , a $k$ -coloring $ϕ:X\to\{1,\dots,k\}$ of $X$ is distinguishing with respect to $Γ$ if the only $γ\in Γ$ that fixes $ϕ$ is the identity action. The distinguishing number of the action $Γ$ , denoted $D_Γ(X)$ , is then the smallest positive integer $k$ such that there is a distinguishing $k$ -coloring of $X$ with respect to $Γ$ . 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 $Γ$ if for every non-identity element $γ\in Γ$ there is an element $s \in S$ such that $γ(s) \neq s$ . The distinguishing extension number $\operatorname{ext}_D(X,Γ;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.

preprint2014arXiv

Graph Saturation in Multipartite Graphs

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é, 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].

preprint2013arXiv

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

A sequence of nonnegative integers $π$ 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 $π$ , and we write $π=π(G)$ . A graphic sequence $π$ is {\it potentially $H$ -graphic} if there is a realization of $π$ that contains $H$ as a subgraph. Given nonincreasing graphic sequences $π_1=(d_1,\ldots,d_n)$ and $π_2 = (s_1,\ldots,s_n)$ , we say that $π_1$ {\it majorizes} $π_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 $π(G)$ majorizes $π(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 $π^*(H)$ such that if $π$ is a graphic sequence that is not potentially $H$ -graphic, then $π$ is close to being majorized by $π^*(H)$ . Similar to the role played by complete multipartite graphs in the traditional extremal setting, the sequence $π^*(H)$ asymptotically gives the maximum possible sum of a graphic sequence $π$ that is not potentially $H$ -graphic.

preprint2011arXiv

List Distinguishing Parameters of Trees

A coloring of the vertices of a graph G is said to be distinguishing} provided no nontrivial automorphism of G preserves all of the vertex colors. The distinguishing number of G, D(G), is the minimum number of colors in a distinguishing coloring of G. The distinguishing chromatic number of G, chi_D(G), is the minimum number of colors in a distinguishing coloring of G that is also a proper coloring. Recently the notion of a distinguishing coloring was extended to that of a list distinguishing coloring. Given an assignment L= {L(v) : v in V(G)} of lists of available colors to the vertices of G, we say that G is (properly) L-distinguishable if there is a (proper) distinguishing coloring f of G such that f(v) is in L(v) for all v. The list distinguishing number of G, D_l(G), is the minimum integer k such that G is L-distinguishable for any list assignment L with |L(v)| = k for all v. Similarly, the list distinguishing chromatic number of G, denoted chi_{D_l}(G) is the minimum integer k such that G is properly L-distinguishable for any list assignment L with |L(v)| = k for all v. In this paper, we study these distinguishing parameters for trees, and in particular extend an enumerative technique of Cheng to show that for any tree T, D_l(T) = D(T), chi_D(T)=chi_{D_l}(T), and chi_D(T) <= D(T) + 1.

preprint2011arXiv

Rainbow Matchings of size δ(G) in Properly Edge-colored Graphs

A {\it rainbow matching} in an edge-colored graph is a matching in which all the edges have distinct colors. Wang asked if there is a function f(δ) such that a properly edge-colored graph G with minimum degree δand order at least f(δ) must have a rainbow matching of size δ. We answer this question in the affirmative; f(δ) = 6.5δsuffices. Furthermore, the proof provides a O(δ(G)|V(G)|^2)-time algorithm that generates such a matching.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Michael Ferrara

Research overview

Is this your work?

12 publications

Ore and Chvátal-type Degree Conditions for Bootstrap Percolation from Small Sets

Navigating Between Packings of Graphic Sequences

Chvátal-type results for degree sequence Ramsey numbers

I,F-partitions of Sparse Graphs

On the Strong Chromatic Index of Sparse Graphs

On the Sum Neccesary to Ensure that a Degree Sequence is Potentially H-Graphic

Partitioning a graph into highly connected subgraphs

Extending Precolorings to Distinguish Group Actions

Graph Saturation in Multipartite Graphs

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

List Distinguishing Parameters of Trees

Rainbow Matchings of size δ(G) in Properly Edge-colored Graphs

See the researcher in context

Building this map preview

Michael Ferrara

Research overview

Is this your work?

12 publications

Ore and Chvátal-type Degree Conditions for Bootstrap Percolation from Small Sets

Navigating Between Packings of Graphic Sequences

Chvátal-type results for degree sequence Ramsey numbers

I,F-partitions of Sparse Graphs

On the Strong Chromatic Index of Sparse Graphs

On the Sum Neccesary to Ensure that a Degree Sequence is Potentially H-Graphic

Partitioning a graph into highly connected subgraphs

Extending Precolorings to Distinguish Group Actions

Graph Saturation in Multipartite Graphs

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

List Distinguishing Parameters of Trees

Rainbow Matchings of size δ(G) in Properly Edge-colored Graphs

See the researcher in context

Building this map preview

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