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 2012Show all

5 papers · 1 filter

math.CO2012★ 16 cited

Short proofs of coloring theorems on planar graphs

Oleg V. Borodin, Alexandr V. Kostochka, Bernard Lidický +1

A recent lower bound on the number of edges in a k-critical n-vertex graph by Kostochka and Yancey yields a half-page proof of the celebrated Grötzsch Theorem that every planar tri…

math.CO2012★ 8 cited

Ore's Conjecture for $k = 4$ and Gr\" otzsch Theorem

Alexandr Kostochka, Matthew Yancey

A graph $G$ is $k$ -{\em critical} if it has chromatic number $k$ , but every proper subgraph of $G$ is $(k - 1)$ --colorable. Let $f_{k} (n)$ denote the minimum number of edges in an $n$ -…

math.CO2012★ 4 cited

Ore's Conjecture on color-critical graphs is almost true

Alexandr Kostochka, Matthew Yancey

A graph $G$ is $k$ -critical if it has chromatic number $k$ , but every proper subgraph of $G$ is $(k - 1)$ --colorable. Let $f_{k} (n)$ denote the minimum number of edges in an $n$ -vertex…

math.CO2012★ 7 cited

Large rainbow matchings in large graphs

Alexandr Kostochka, Florian Pfender, Matthew Yancey

A \textit{rainbow subgraph} of an edge-colored graph is a subgraph whose edges have distinct colors. The \textit{color degree} of a vertex $v$ is the number of different colors on…

math.CO2012

Harmonious Coloring of Trees with Large Maximum Degree

Saieed Akbari, Jaehoon Kim, Alexandr Kostochka

A harmonious coloring of $G$ is a proper vertex coloring of $G$ such that every pair of colors appears on at most one pair of adjacent vertices. The harmonious chromatic number of…