Alexandr V. Kostochka

activity

20212026

2 ℓ + 1

vertices are

ℓ

-recognizable

2 citations · 2 across the 16 of their papers we have counts for

collaborators

17 papers

math.CO2026

DP vertex-arboricity of sparse graphs

Peter Bradshaw, Alexandr Kostochka, Zimu Xiang

The vertex arboricity $va (G)$ of a multigraph $G$ is the minimum number $k$ for which $V (G)$ can be partitioned into $k$ subsets, each of which induces an acyclic subgraph…

math.CO2026

An introduction to equitable DP coloring of graphs

H. A. Kierstead, Alexandr Kostochka, Zimu Xiang

A proper $k$ -coloring of vertices of an $n$ -vertex graph is equitable if the size of every color class is $⌊ n / k ⌋$ or $⌈ n / k ⌉$ . An extension of it to list col…

math.CO2025

Caterpillars with $n$ vertices are reconstructible from subgraphs with at most $n /2 + 1$ vertices

Alexandr V. Kostochka, Zishen Qu, Maddy Ritter +1

The $\textit{$m$-deck}$ of an $n$ -vertex graph is the multiset of unlabeled induced subgraphs with $m$ vertices. Caterpillars are trees in which all nonleaf vertices lie on a singl…

math.CO2025

Turán number of four vertex-disjoint cliques

Alexandr Kostochka, Dadong Peng, Liang Zhang

Given a graph $H$ , the Turán number $ex (n, H)$ of $H$ is the maximum number of edges of an $n$ -vertex simple graph containing no $H$ as a subgraph. Let $k K_{p}$ denote the disjo…

math.CO2025

Flexible DP 3-coloring of sparse multigraphs

Peter Bradshaw, Ilkyoo Choi, Alexandr Kostochka

A \emph{request} on a graph assigns a preferred color to a subset of the vertices. A graph $G$ is \emph{ $ε$ -flexibly $k$ -choosable} if for every $k$ -list assignment $L$ and every r…

math.CO2025

Partition of Sparse Multigraphs into a Forest and a Forest with Restrictions

Ilkyoo Choi, Alexandr V. Kostochka, Matthew Yancey

The following measure of sparsity of multigraphs refining the maximum average degree: For $a > 0$ and an arbitrary real $b$ , a multigraph $H$ is \emph{ $(a, b)$ -sparse} if it is loople…

math.CO2025

Results and Problems on Equitable Coloring of Graphs

H. A. Kierstead, Alexandr Kostochka, Zimu Xiang

A proper coloring of vertices of a graph is equitable if the sizes of any two color classes differ by at most 1. Such colorings have many applications and are interesting by themse…

math.CO2024

Equitable list coloring of sparse graphs

H. A. Kierstead, Alexandr Kostochka, Zimu Xiang

A proper vertex coloring of a graph is equitable if the sizes of all color classes differ by at most $1$ . For a list assignment $L$ of $k$ colors to each vertex of an $n$ -vertex gr…

math.CO2024

A lower bound on the number of edges in DP-critical graphs. II. Four colors

Peter Bradshaw, Ilkyoo Choi, Alexandr Kostochka +1

A graph $G$ is $k$ -critical (list $k$ -critical, DP $k$ -critical) if $χ (G) = k$ ( $χ_{ℓ} (G) = k$ , $χ_{DP} (G) = k$ ) and for every proper subgraph $G^{'}$ of $G$ , $χ (G^{'}) < k$ ($χ_\ell(…

math.CO2024

A lower bound on the number of edges in DP-critical graphs

Peter Bradshaw, Ilkyoo Choi, Alexandr Kostochka +1

math.CO2024

Ore-type conditions for existence of a jellyfish in a graph

Jaehoon Kim, Alexandr Kostochka, Ruth Luo

The famous Dirac's Theorem states that for each $n \geq 3$ every $n$ -vertex graph $G$ with minimum degree $δ (G) \geq n /2$ has a hamiltonian cycle. When $δ (G) < n /2$ , this cannot be gu…

math.CO2023

Sparse critical graphs for defective $(1, 3)$ -coloring

Alexandr Kostochka, Jingwei Xu, Xuding Zhu

A graph $G$ is $(1, 3)$ -colorable if its vertices can be partitioned into subsets $V_{1}$ and $V_{2}$ so that every vertex in $G [V_{1}]$ has degree at most $1$ and every vertex in $G[V_2]…

math.CO2023

Equitable list coloring of planar graphs with given maximum degree

H. A. Kierstead, Alexandr Kostochka, Zimu Xiang

If $L$ is a list assignment of $r$ colors to each vertex of an $n$ -vertex graph $G$ , then an equitable $L$ -coloring of $G$ is a proper coloring of vertices of $G$ from their lists…

math.CO2023

Acyclic graphs with at least $2 ℓ + 1$ vertices are $ℓ$ -recognizable

Alexandr V. Kostochka, Mina Nahvi, Douglas B. West +1

The $(n - ℓ)$ -deck of an $n$ -vertex graph is the multiset of subgraphs obtained from it by deleting $ℓ$ vertices. A family of $n$ -vertex graphs is $ℓ$ -recognizable if every…

math.CO2022

Sharp lower bounds for the number of maximum matchings in bipartite multigraphs

Alexandr V. Kostochka, Douglas B. West, Zimu Xiang

We study the minimum number of maximum matchings in a bipartite multigraph G with parts $X$ and $Y$ under various conditions, refining the well-known lower bound due to M. Hall. Wh…

math.CO2021

On sizes of 1-cross intersecting set pair systems

Alexandr V. Kostochka, Grace McCourt, Mina Nahvi

Let ${(A_{i}, B_{i})}_{i = 1}^{m}$ be a set pair system. Füredi, Gyárfás and Király called it {\em $1$ -cross intersecting} if $∣ A_{i} \cap B_{j} ∣$ is $1$ when $i \neq = j$ and $0$ if $i = j$ . They…

math.CO2021★ 2 cited

Acyclic graphs with at least $2 ℓ + 1$ vertices are $ℓ$ -recognizable

Alexandr V. Kostochka, Mina Nahvi, Douglas B. West +1

The $(n - ℓ)$ -deck of an $n$ -vertex graph is the multiset of subgraphs obtained from it by deleting $ℓ$ vertices. A family of $n$ -vertex graphs is $ℓ$ -recognizable if every…

DP vertex-arboricity of sparse graphs

An introduction to equitable DP coloring of graphs

Caterpillars with n vertices are reconstructible from subgraphs with at most n/2+1 vertices

Turán number of four vertex-disjoint cliques

Flexible DP 3-coloring of sparse multigraphs

Partition of Sparse Multigraphs into a Forest and a Forest with Restrictions

Results and Problems on Equitable Coloring of Graphs

Equitable list coloring of sparse graphs

A lower bound on the number of edges in DP-critical graphs. II. Four colors

A lower bound on the number of edges in DP-critical graphs

Ore-type conditions for existence of a jellyfish in a graph

Sparse critical graphs for defective (1,3)-coloring

Equitable list coloring of planar graphs with given maximum degree

Acyclic graphs with at least 2ℓ+1 vertices are ℓ-recognizable

Sharp lower bounds for the number of maximum matchings in bipartite multigraphs

On sizes of 1-cross intersecting set pair systems

Acyclic graphs with at least 2ℓ+1 vertices are ℓ-recognizable

Caterpillars with $n$ vertices are reconstructible from subgraphs with at most $n /2 + 1$ vertices

Sparse critical graphs for defective $(1, 3)$ -coloring

Acyclic graphs with at least $2 ℓ + 1$ vertices are $ℓ$ -recognizable

Acyclic graphs with at least $2 ℓ + 1$ vertices are $ℓ$ -recognizable