Source author record

Andrew McConvey

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

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

3works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Strengthening theorems of Dirac and Erdős on disjoint cycles

Let $k \ge 3$ be an integer, $H_{k}(G)$ be the set of vertices of degree at least $2k$ in a graph $G$ , and $L_{k}(G)$ be the set of vertices of degree at most $2k-2$ in $G$ . In 1963, Dirac and Erdős proved that $G$ contains $k$ (vertex-)disjoint cycles whenever $|H_{k}(G)| - |L_{k}(G)| \ge k^{2} + 2k - 4$ . The main result of this paper is that for $k \ge 2$ , every graph $G$ with $|V(G)| \ge 3k$ containing at most $t$ disjoint triangles and with $|H_{k}(G)| - |L_{k}(G)| \ge 2k + t$ contains $k$ disjoint cycles. This yields that if $k \ge 2$ and $|H_{k}(G)| - |L_{k}(G)| \ge 3k$ , then $G$ contains $k$ disjoint cycles. This generalizes the Corrádi-Hajnal Theorem, which states that every graph $G$ with $H_{k}(G) = V(G)$ and $|H_{k}(G)| \ge 3k$ contains $k$ disjoint cycles.

preprint2015arXiv

A list version of graph packing

We consider the following generalization of graph packing. Let $G_{1} = (V_{1}, E_{1})$ and $G_{2} = (V_{2}, E_{2})$ be graphs of order $n$ and $G_{3} = (V_{1} \cup V_{2}, E_{3})$ a bipartite graph. A bijection $f$ from $V_{1}$ onto $V_{2}$ is a list packing of the triple $(G_{1}, G_{2}, G_{3})$ if $uv \in E_{2}$ implies $f(u)f(v) \notin E_{2}$ and $vf(v) \notin E_{3}$ for all $v \in V_{1}$ . We extend the classical results of Sauer and Spencer and Bollobás and Eldridge on packing of graphs with small sizes or maximum degrees to the setting of list packing. In particular, we extend the well-known Bollobás--Eldridge Theorem, proving that if $Δ(G_{1}) \leq n-2, Δ(G_{2}) \leq n-2, Δ(G_{3}) \leq n-1$ , and $|E_1| + |E_2| + |E_3| \leq 2n-3$ , then either $(G_{1}, G_{2}, G_{3})$ packs or is one of 7 possible exceptions. Hopefully, the concept of list packing will help to solve some problems on ordinary graph packing, as the concept of list coloring did for ordinary coloring.

preprint2015arXiv

Toward Żak's conjecture on graph packing

Two graphs $G_{1} = (V_{1}, E_{1})$ and $G_{2} = (V_{2}, E_{2})$ , each of order $n$ , pack if there exists a bijection $f$ from $V_{1}$ onto $V_{2}$ such that $uv \in E_{1}$ implies $f(u)f(v) \notin E_{2}$ . In 2014, Żak proved that if $Δ(G_{1}), Δ(G_{2}) \leq n-2$ and $|E_{1}| + |E_{2}| + \max \{ Δ(G_{1}), Δ(G_{2}) \} \leq 3n - 96n^{3/4} - 65$ , then $G_{1}$ and $G_{2}$ pack. In the same paper, he conjectured that if $Δ(G_{1}), Δ(G_{2}) \leq n-2$ , then $|E_{1}| + |E_{2}| + \max \{ Δ(G_{1}), Δ(G_{2}) \} \leq 3n - 7$ is sufficient for $G_{1}$ and $G_{2}$ to pack. We prove that, up to an additive constant, Żak's conjecture is correct. Namely, there is a constant $C$ such that if $Δ(G_1),Δ(G_2) \leq n-2$ and $|E_{1}| + |E_{2}| + \max \{ Δ(G_{1}), Δ(G_{2}) \} \leq 3n - C$ , then $G_{1}$ and $G_{2}$ pack. In order to facilitate induction, we prove a stronger result on list packing.

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.