Alexandr V. Kostochka

collaborators

9 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.CO2026

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 disj…

math.CO2026

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

Peter Bradshaw, Ilkyoo Choi, Alexandr Kostochka +1

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

math.CO2025

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

DP vertex-arboricity of sparse graphs

An introduction to equitable DP coloring of graphs

TurÃ¡n number of four vertex-disjoint cliques

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

Equitable list coloring of sparse graphs

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

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