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

86 papers

math.CO2023

A hypergraph analog of Dirac's Theorem for long cycles in 2-connected graphs, II: Large uniformities

Alexandr Kostochka, Ruth Luo, Grace McCourt

Dirac proved that each $n$ -vertex $2$ -connected graph with minimum degree $k$ contains a cycle of length at least $min {2 k, n}$ . We obtain analogous results for Berge cycles in h…

math.CO2023

Trees with at least $6 ℓ + 11$ vertices are $ℓ$ -reconstructible

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

The $(n - ℓ)$ -deck of an $n$ -vertex graph is the multiset of (unlabeled) subgraphs obtained from it by deleting $ℓ$ vertices. An $n$ -vertex graph is $ℓ$ -reconstructible if i…

math.CO2023

Tur\' an number for bushes

Zoltán Füredi, Alexandr Kostochka

Let $a, b \in Z^{+}$ , $r = a + b$ , and let $T$ be a tree with parts $U = {u_{1}, u_{2}, \dots, u_{s}}$ and $V = {v_{1}, v_{2}, \dots, v_{t}}$ . Let $U_{1}, \dots, U_{s}$ and $V_{1}, \dots, V_{t}$ be di…

math.CO2023

Sparse critical graphs for defective DP-colorings

Alexandr Kostochka, Jingwei Xu

An interesting generalization of list coloring is so called DP-coloring (named after Dvořák and Postle). We study $(i, j)$ -defective DP-colorings of simple graphs. Define $g_{DP}(i,…

math.CO2023

Equitable coloring of planar graphs with maximum degree at least eight

Alexandr Kostochka, Duo Lin, Zimu Xiang

The Chen-Lih-Wu Conjecture states that each connected graph with maximum degree $Δ \geq 3$ that is not the complete graph $K_{Δ + 1}$ or the complete bipartite graph $K_{Δ, Δ}$ admits…

math.CO2022

A hypergraph analog of Dirac's Theorem for long cycles in 2-connected graphs

Alexandr Kostochka, Ruth Luo, Grace McCourt

Dirac proved that each $n$ -vertex $2$ -connected graph with minimum degree at least $k$ contains a cycle of length at least $min {2 k, n}$ . We consider a hypergraph version of this…

A hypergraph analog of Dirac's Theorem for long cycles in 2-connected graphs, II: Large uniformities

Trees with at least 6ℓ+11 vertices are ℓ-reconstructible

Tur\' an number for bushes

Sparse critical graphs for defective DP-colorings

Equitable coloring of planar graphs with maximum degree at least eight

A hypergraph analog of Dirac's Theorem for long cycles in 2-connected graphs

Trees with at least $6 ℓ + 11$ vertices are $ℓ$ -reconstructible