A. Kostochka

activity

20052023

most citedDP-colorings of graphs with high chromatic number

42 citations · 275 across the 72 of their papers we have counts for

collaborators

Showing 2015Show all

6 papers · 1 filter

math.CO2015

Toward Żak's conjecture on graph packing

Ervin Győri, Alexandr Kostochka, Andrew McConvey +1

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…

math.CO2015

Strong chromatic index of subcubic planar multigraphs

A. V. Kostochka, X. Li, W. Ruksasakchai +3

The strong chromatic index of a multigraph is the minimum $k$ such that the edge set can be $k$ -colored requiring that each color class induces a matching. We verify a conjecture o…

math.CO2015★ 1 cited

Stability in the Erdos--Gallai Theorem on cycles and paths

Zoltán Füredi, Alexandr Kostochka, Jacques Verstraëte

The Erdős-Gallai Theorem states that for $k \geq 2$ , every graph of average degree more than $k - 2$ contains a $k$ -vertex path. This result is a consequence of a stronger result o…

math.CO2015★ 15 cited

On the number of edges in a graph with no $(k + 1)$ -connected subgraphs

Anton Bernshteyn, Alexandr Kostochka

Mader proved that for $k \geq 2$ and $n \geq 2 k$ , every $n$ -vertex graph with no $(k + 1)$ -connected subgraphs has at most $(1 + \frac{1}{2}) k (n - k)$ edges. He also conjectured tha…

math.CO2015★ 1 cited

Decomposition of Sparse Graphs into Forests: The Nine Dragon Tree Conjecture for $k \leq 2$

Min Chen, Seog-Jin Kim, Alexandr Kostochka +2

For a loopless multigraph $G$ , the fractional arboricity $A r b (G)$ is the maximum of $\frac{∣ E ( H ) ∣}{∣ V ( H ) ∣ - 1}$ over all subgraphs $H$ with at least two vertices. Generalizing the Na…

math.CO2015

A list version of graph packing

Ervin Győri, Alexandr Kostochka, Andrew McConvey +1

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})$ …

Toward Żak's conjecture on graph packing

Strong chromatic index of subcubic planar multigraphs

Stability in the Erdos--Gallai Theorem on cycles and paths

On the number of edges in a graph with no (k+1)-connected subgraphs

Decomposition of Sparse Graphs into Forests: The Nine Dragon Tree Conjecture for k≤2

A list version of graph packing

On the number of edges in a graph with no $(k + 1)$ -connected subgraphs

Decomposition of Sparse Graphs into Forests: The Nine Dragon Tree Conjecture for $k \leq 2$