42 citations · 275 across the 72 of their papers we have counts for
6 papers · 1 filter
Coloring, sparseness, and girth
Noga Alon, Alexandr Kostochka, Benjamin Reiniger +2
An -augmented tree is a rooted tree plus edges added from each leaf to ancestors. For , we construct a bipartite -augmented complete -ary tree havi…
A Brooks-type result for sparse critical graphs
Alexandr Kostochka, Matthew Yancey
A graph is -{\em critical} if it has chromatic number , but every proper subgraph of is --colorable. Let denote the minimum number of edges in an -…
Turan Problems and Shadows III: expansions of graphs
Alexandr Kostochka, Dhruv Mubayi, Jacques Verstraete
The expansion of a graph is the -uniform hypergraph obtained from by enlarging each edge of with a new vertex disjoint from such that distinct edges are…
The (2k-1)-connected multigraphs with at most k-1 disjoint cycles
H. A. Kierstead, A. V. Kostochka, E. C. Yeager
In 1963, Corrádi and Hajnal proved that for all and , every (simple) graph on n vertices with minimum degree at least 2k contains k disjoint cycles. The same ye…
Cycles in triangle-free graphs of large chromatic number
Alexandr Kostochka, Benny Sudakov, Jacques Verstraete
More than twenty years ago Erdős conjectured~\cite{E1} that a triangle-free graph of chromatic number contains cycles of at least $k^{2 - \varepsilon}…
Turan Problems and Shadows II: Trees
Alexandr Kostochka, Dhruv Mubayi, Jacques Verstraete
The expansion of a graph is the 3-uniform hypergraph obtained from by enlarging each edge of with a vertex disjoint from such that distinct edges are enlar…