Publications of Alexandr V. Kostochka

Submitted

Talk at Oberwolfach [pdf ]

Talk at Budapest [pdf ]

P. Hamburger, P. Haxell, and A. V. Kostochka,
On Directed Triangles in Digraphs [ps, pdf].

T. Boehme and A. V. Kostochka,
Many Disjoint Dense Subgraphs versus Large $k$-connected Subgraphs in Large Graphs with Given Edge Density [ps, pdf].

A. V. Kostochka and G. Yu,
An Ore-type analogue of the Sauer-Spencer Theorem.

H. Kaul, A. V. Kostochka, and G. Yu,
On a graph packing conjecture by Bollobas, Eldridge, and Catlin.

A. V. Kostochka and B.Y. Stodolsky,
An upper bound on the domination number of $n$-vertex connected cubic graphs.

J. Balogh and A. V. Kostochka,
On 2-detour subgraphs of the hypercube.

A. V. Kostochka and D. Mubayi,
When is an almost monochromatic $K_4$ guaranteed?

A. V. Kostochka and G. Yu,
Degree conditions for packing many short cycles.

H. A. Kierstead and A. V. Kostochka,
A Short Proof of the Hajnal-Szemeredi Theorem on Equitable Coloring [ps, pdf].

H. A. Kierstead and A. V. Kostochka,
An Ore-type Theorem on Equitable Coloring[ps, pdf].

Accepted

B. Bollobas, A. V. Kostochka, and K. Nakprasit,
Packing d-degenerate graphs[ps, pdf],
to appear in Journal of Combinatorial Theory, Series B.

A. V. Kostochka and G. Yu,
Minimum degree conditions for H-linked graphs,
to appear in Discrete Appl. Math.

N. Eaton, Z. Furedi, A. V. Kostochka, and J. Skokan,
Tree representations of graphs,
to appear in European J. of Combinatorics .

A. V. Kostochka and N. Prince,
K_{s,t}-minors in graphs with given average degree, [ps, pdf]
to appear in Discrete Math.

H. Kaul and A. V. Kostochka,
Extremal Graphs for a Graph Packing Theorem of Sauer and Spencer,
to appear in Combinatorics, Probability and Computing.

N. Arizumi, P. Hamburger, and A. V. Kostochka,
On k-detour subgraphs of hypercubes,
to appear in Journal of Graph Theory.

2007

A. V. Kostochka and G. Yu,
Ore-type graph packing problems,
Combinatorics, Probability and Computing, 16 (2007), 167-169.

2006

R. Gould, A. V. Kostochka, and G. Yu,
On minimum degree implying that a graph is H-linked,
SIAM J. of Discrete Mathematics, 20 (2006), 829-840.

A. V. Kostochka and V. Rod,
On Ramsey numbers of uniform hypergraphs with given maximum degree,
Journal of Combinatorial Theory, Series A, 113}, (2006), 1555-1564.

K. Kawarabayshi, A. V. Kostochka, and G. Yu,
On sufficient degree conditions for a graph to be k-linked,
Combinatorics, Probability and Computing, 15 (2006), 685-694.

A. V. Kostochka,
Color-critical graphs and hypergraphs with few edges: a survey, in: More sets, graphs and numbers,
Bolyai Society Mathematical Studies, 15 (2006), Springer, 175-197.

N. Alon, G. Brightwell, H. A. Kierstead, A. V. Kostochka, and P. Winkler,
Dominating Sets in k-Majority Tournaments,
Journal of Combinatorial Theory, Series B, 96 (2006), 374-387.

A. V. Kostochka and D.B. West,
Chvatal's Condition Cannot Hold for Both a Graph and Its Complement,
Discussiones Mathematicae -- Graph Theory 26 (2006), 73-76.

A. V. Kostochka and N. Sheikh,
On the Induced Ramsey Number IR(P_3,H),
Algorithms and Combinatorics 26 (2006), 155-167, Springer.

M. Cropper, D. Greenwell, A.J.W. Hilton, and A. V. Kostochka,
The domination number of cubic Hamiltonian graphs,
AKCE International Journal of Graph Theory and Combinatorics, 2 (2005), 137-144.

O. V. Borodin, A. O. Ivanova, and A. V. Kostochka,
Oriented $5$-coloring of vertices of sparse graphs,
Discrete Analyzis and Operation Research, 13 (2006), No 1, 16-32 (in Russian).

2005

Z. Furedi, A. V. Kostochka, R. Skrekovski, M. Stiebitz, and D. B. West,
Nordhaus-Gaddum-type theorems for decomposition into many parts,
Journal of Graph Theory, 50 (2005), 273-292.

A. V. Kostochka and B.Y. Stodolsky,
On domination in connected cubic graphs,
Discrete Mathematics 304 (2005), 45-50.

A. V. Kostochka and G. Yu,
An extremal problem for H-linked graphs,
Journal of Graph Theory, 50 (2005), 321-339.

A. V. Kostochka and K. Nakprasit,
On equitable $\Delta$-coloring of graphs with low average degree,
Theor. Comp. Science, 349 (2005), 82-91.

B. Bollobas, A. V. Kostochka, and K. Nakprasit,
On two conjectures on packing of graphs,
Combinatorics, Probability and Computing 14 (2005), 723-736.

A. V. Kostochka and J. Verstraete,
Even cycles in hypergraphs,
Journal of Combinatorial Theory, Series B, 94 (2004), 173-182.

A. V. Kostochka and D. R. Woodall,
Irreducible hypergraphs for Hall-type conditions, and arc-minimal digraph expanders,
European J. of Combinatorics, 26 (2005), 1119-1138.

A. V. Kostochka, K. Nakprasit, and S. Pemmaraju,
On Equitable Coloring of $d$-Degenerate Graphs,
SIAM J. of Combinatorics, 19 (2005), 83-95.

A. N. Glebov, A. V. Kostochka, and V. A. Tashkinov,
Smaller planar triangle-free graphs that are not 3-list-colorable,
Discrete Mathematics 290 (2005), 269-274.

T. Boehme and A. V. Kostochka,
Disjoint K_r-minors in large graphs with given average degree,
European J. of Combinatorics, 26 (2005), 289-292.

2004

M. Albertson, A. V. Kostochka, and D. B. West,
Precoloring extensions of Brooks' Theorem ,
SIAM J. of Combinatorics, 18 (2004), 542-553.

A. V. Kostochka and V. Rödl,
On graphs with small Ramsey numbers, II [ps],
Combinatorica, 24 (2004), 389-401.

P. N. Balister, A. V. Kostochka, Hao Li, and R. H. Schelp,
Balanced Edge Colorings,
Journal of Combinatorial Theory, Series B, 90 (2004), 3-20.

O. V. Borodin, S.-J. Kim, A. V. Kostochka, and D. B. West,
Homomorphisms from sparse graphs with large girth [ps],
Journal of Combinatorial Theory, Series B, 90 (2004), 147-159.

A. V. Kostochka,
Coloring uniform hypergraphs with few colors [ps],
Random Structures & Algorithms, 24 (2004), 1-10.

2003

A. V. Kostochka and V.A. Tashkinov,
Decomposing graphs into long paths ,
Order, 20 (2003), 239-253.

A. V. Kostochka,
Coloring intersection graphs of geometric figures with given clique number,
in: Towards a Theory of Geometric Graphs (J. Pach Ed.), AMS, Providence, Rhode Island, 127-138, 2003.

A. V. Kostochka and B. Sudakov,
On Ramsey numbers of sparse graphs [ps],
CPC 12 (2003), 627-641.

A. V. Kostochka and K. Nakprasit,
Equitable colorings of $k$-degenerate graphs [ps],
CPC 12 (2003), 53-60.

A. V. Kostochka, M. J. Pelsmajer, and D. B. West,
A list analogue of equitable coloring [ps],
Journal of Graph Theory, 44 (2003), 166-177.

A. V. Kostochka and M. Stiebitz,
A new lower bound on the number of edges in colour-critical graphs,
Journal of Combinatorial Theory, Series B, 87 (2003), 374-402.

R. Faudree, R. Gould, A. V. Kostochka, L. Lesniak, I. Schiermeyer, and A. Saito,
Degree conditions for k-ordered hamiltonian graphs,
Journal of Graph Theory}, 43 (2003), 199-210.

2002

O. V. Borodin, A. V. Kostochka, A. Raspaud and E. Sopena,
On the minimum number of colours in an acyclic k-strong coloring of maps on surfaces,
Matematicheskie Zametki, 72, #1 (2002), 35-37 (in Russian).

D. Fon-Der-Flaass, J. Nesetril, A. V. Kostochka, A. Raspaud, and E. Sopena,
Nilpotent families of endomorphisms of (P(V)^+,U),
Journal of Combinatorial Theory, Series B, 86 (2002), 100-108.

O. V. Borodin, D. Fon-Der-Flaass, A. V. Kostochka, A. Raspaud and E. Sopena,
Acyclic list 7-coloring of planar graphs,
Journal of Graph Theory, 40 (2002), 83-90.

A. V. Kostochka,
Transversals in uniform hypergraphs with property (p,2),
Combinatorica, 22 (2002), 275-285.

A. V. Kostochka and D. R. Woodall,
Total choosability of multicircuits I,
Journal of Graph Theory}, 40 (2002), 26-43.

A. V. Kostochka and D. R. Woodall,
Total choosability of multicircuits II,
Journal of Graph Theory}, 40 (2002), 44-67.

A. V. Kostochka,
On a theorem by Erdos, Rubin, and Taylor [ps],
Electronic J. of Comb. 9 (2002), # N9.

A. V. Kostochka and J. Nesetril,
Colouring relatives of intervals on the plane, II: intervals and rays in two directions,
European Journal of Combinatorics 23 (2002), 37-41.

A. V. Kostochka,
Equitable colorings of outerplanar graphs [ps],
Discrete Mathematics 258 (2002), 373-377.

A. V. Kostochka and M. Stiebitz,
A list version of Dirac's theorem on the number of edges in colour-critical graphs,
J. Graph Theory 39 (2002), 165-167.

2001

A. V. Kostochka and V. Rödl,
On graphs with small Ramsey numbers,
J. Graph Theory 37 (2001), no. 4, 198-204.
A. V. Kostochka and D. R. Woodall ,
Choosability conjectures and multicircuits,
Discrete Mathematics 240 (2001), 123-143.
A. V. Kostochka and D. R. Woodall ,
Density conditions for panchromatic colourings of hypergraphs,
Combinatorica 21 (2001), 515-541.
A. V. Kostochka and D. R. Woodall ,
Sparse sets in the complements of graphs with given girth,
Discrete Mathematics 233 (2001), 163-174.
A. V. Kostochka, J. Nesetril, and P. Smolikova,
Coloring and homomorphisms of degenerate and bounded degree graphs,
Discrete Mathematics 233 (2001), 257-276.
P. Hell, A. V. Kostochka, A. Raspaud, and E. Sopena,
On nice graphs,
Discrete Mathematics 234 (2001), 39-51 .
O. V. Borodin, D. G. Fon-Der-Flaass, A. V. Kostochka, A. Raspaud, and E. Sopena,
On deeply critical oriented graphs,
J. of Combin. Theory (B) 81 (2001), 150-155 .
A. V. Kostochka, D. Mubayi, V. Rödl, and P. Tetali,
On the chromatic number of set systems,
Random Struct. & Algorithms 19 (2001), no. 2, 87-98.
M. Alzohairi, A. V. Kostochka, and I. Rival,
The pagenumber of spherical lattices is unbounded,
Arab Journal of Math. Sciences 7 (2001), 79-82.

2000

A. V. Kostochka and M. Stiebitz,
On the number of edges in colour-critical graphs and hypergraphs,
Combinatorica 20 (2000), 521-530.
A. V. Kostochka and D. R. Woodall ,
On the number of edges in hypergraphs critical with respect to strong colourings,
European Journal of Combinatorics 21 (2000), 249-255.
A. A. Ageev and A. V. Kostochka,
Vertex set partitions preserving conservativeness,
J. of Combin. Theory ( B) 80 (2000), 202-217.
A. V. Kostochka and I. G. Perepelitsa,
Colouring triangle-free intersection graphs of boxes on the plane,
Discrete Mathematics 220 (2000), 243-249.
B. Bollobas, A. V. Kostochka, and R. H. Schelp,
Local and Mean Ramsey Numbers for Trees,
J. of Combin. Theory ( B) 79 (2000), 100--103.
O. V. Borodin, A. V. Kostochka, A. Raspaud, and E. Sopena,
Acyclic k-Strong Coloring of Maps on Surfaces,
Mathematical Notes, 67 (2000), Nos. 1-2, 29-35.
O. V. Borodin, A. V. Kostochka, and B. Toft,
Variable degeneracy: extensions of Brooks' and Gallai's theorems,
Discrete Mathematics 214 (2000), 101-112.
G. Gutin, A. V. Kostochka, and B. Toft,
On the Hajos number of graphs,
Discrete Mathematics 213 (2000), 153-161.
A. V. Kostochka,
Extremal problems on Delta-systems,
in: ``Numbers, Information and Complexity'',
Kluwer, 2000, 143-150.
W. A. Deuber and A. V. Kostochka,
On degrees of vertices in paradoxical trees,
Discrete Mathematics 212 (2000), 53-60.

1999

A. V. Kostochka and D. B. West,
Every outerplanar graph is the union of two interval graphs,
Congressus Numerantium, 139 (1999), 5-8.
A. V. Kostochka, V. Rödl, and L. A. Talysheva,
On systems of small sets with no large $\Delta$-subsystems,
Combin. Prob. Comput. 8 (1999), no. 3, 265-268.
D. G. Fon-Der-Flaass, A. V. Kostochka, and D. R. Woodall ,
Transversals in uniform hypergraphs with property~$(7,2)$,
Discrete Mathematics 207 (1999), 277-284 .
O. V. Borodin, A. V. Kostochka, and D. R. Woodall ,
Acyclic colourings of planar graphs with large girth,
The Journal of the London Math. Society, 60 (1999), 344-352.
A. V. Kostochka and J. Nesetril,
Properties of Descartes' construction of triangle-free graphs with high chromatic number, Combin. Prob. Comput. 8 (1999), 467-472.
O. V. Borodin, A. V. Kostochka, A. Raspaud, and E. Sopena,
Acyclic colouring of 1-planar graphs, Diskretnyi Analiz i Issledovanie Operacii, Series 1, 6 (1999), no 4, 20-35.
N. Alon, P. Hamburger, and A. V. Kostochka,
Regular honest graphs, isoperimetric numbers and bisection of weighted graphs,
European Journal of Combinatorics 20 (1999), 469-481.
O. V. Borodin, A. V. Kostochka, J. Nesetril, A. Raspaud, and E. Sopena,
On the maximum average degree and the oriented chromatic number of a graph,
Discrete Mathematics 206 (1999), 77-90 .
A. V. Kostochka, T. Luczak, G. Simonyi, and E. Sopena,
On the minimum number of edges giving maximum oriented chromatic number,
DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 49 (1999), 179-182.
P. Hamburger, A. V. Kostochka, and A. Sidorenko,
Hypercube subgraphs with local detours, J. Graph Theory 30 (1999), 101-111.
A. V. Kostochka and M. Stiebitz,
Excess in colour-critical graphs,
Bolyai Society Mathematical Studies 7 (1999), 87-99.

1998

A. V. Kostochka and L. A. Talysheva,
The dimension of interior levels of the Boolean lattice, II,
Order 15 (1998), 377-383
A. Kostochka and V. Rödl,
On large systems of sets with no large weak $\Delta$--subsystems,
Combinatorica 18 (1998), 235-240.
A. Kostochka and V. Rödl,
Partial Steiner systems and matchings in hypergraphs,
Random Struct. & Algorithms 13 (1998), 335-347.
A. Kostochka, V. D. Mazurov, and L. Ya. Saveliev,
The number of $q$-ary words with restrictions on the length of the maximal run,,
Discrete Math. and its Appl. 8 (1998), No 2, 109--118.
A. V. Kostochka and M. Stiebitz,
Colour-critical graphs with few edges,
Discrete Mathematics 191 (1998), 125-137 .
O. V. Borodin, A. V. Kostochka, and D. R. Woodall ,
On kernel-perfect orientations of line graphs,
Discrete Mathematics 191 (1998), 45-49 .
A. V. Kostochka and N. I. Glebov,
On independent domination number of graphs with given minimum degree,
Discrete Mathematics 188 (1998), 261-266.
O. V. Borodin, A. V. Kostochka, J. Nesetril, A. Raspaud, and E. Sopena,
On universal graphs for planar oriented graphs of a given girth,
Discrete Mathematics 188 (1998), 73-85 .
A. V. Kostochka,
The dimension of neighboring levels of the Boolean lattice,
Order 14 (1998), 267-268.
A. V. Kostochka and J. Nesetril,
Coloring relatives of intervals on the plane, I: chromatic number versus girth,
European Journal of Combinatorics 19 (1998), 103-110.
O. V. Borodin, A. V. Kostochka, and D. R. Woodall ,
Total colourings of planar graphs with large girth,
European Journal of Combinatorics 19 (1998), 19-24.

Reviews in MR can be viewed here.

Reviews in Zentralblatt can be viewed here.

Partially supported by an NSF research grant.