Alexandr Kostochka
Russian-American mathematician
From Wikipedia, the free encyclopedia
Alexandr Vasilyevich Kostochka is a mathematician who works in combinatorics and graph theory. He is a professor emeritus of mathematics at the University of Illinois Urbana-Champaign and has been affiliated with the Sobolev Institute of Mathematics in Novosibirsk, Russia.[1][2] His research concerns graph coloring, graph minors, extremal graph theory, and hypergraphs. He is known for the Kostochka–Thomason bound on clique minors and for the Borodin–Kostochka conjecture on chromatic numbers.[2][3][4]
- Kostochka–Thomason theorem
- Borodin–Kostochka conjecture
Alexandr Kostochka | |
|---|---|
Александр Косточка | |
| Born | Alexandr Vasilyevich Kostochka |
| Known for |
|
| Academic background | |
| Education | Novosibirsk State University (PhD) |
| Thesis | Upper bounds of chromatic functions of graphs (1978) |
| Academic work | |
| Institutions | |
Education and career
Kostochka was raised in the Soviet Union. He trained in the graph-theory school of Alexander Zykov at Novosibirsk.[5] He defended his Candidate of Sciences dissertation on upper bounds for chromatic characteristics of graphs at Novosibirsk State University in 1977 and received his degree in 1978.[6][7][8]
In 1990, he received the higher degree of Doctor of Physico-Mathematical Sciences for work on extremal combinatorial and probabilistic problems.[6] He conducted much of his early career at the Sobolev Institute of Mathematics, part of the Siberian Branch of the Russian Academy of Sciences, and maintained an affiliation after moving to the United States.[2][6][9] He joined the mathematics faculty of the University of Illinois Urbana-Champaign, where he later became professor emeritus, and held an appointment at the university's Center for Advanced Study.[1][2] According to the Mathematics Genealogy Project, he has supervised 17 doctoral students.[7]
Research
Kostochka has published extensively on problems in graph theory, including graph and list coloring, equitable coloring, graph and hypergraph packing, Ramsey-type questions, and Turán-type extremal problems.[2][10] He has frequently collaborated with mathematicians such as Oleg Borodin, Douglas B. West, Zoltán Füredi, H. A. Kierstead, and József Balogh.[10][11]
Graph minors
In the 1980s Kostochka and Andrew Thomason independently determined the order of the largest clique minor forced by the average degree of a graph. They found that every graph of average degree d contains a complete minor of order Θ(d/√log d), a bound that is tight up to a constant factor.[3][12] Equivalently, a graph with no Kt minor is O(t√log t)-degenerate.[13] The result, now commonly called the , gave for several decades the best general lower bound on the size of a clique minor in terms of chromatic number and thus the strongest known partial progress on Hadwiger's conjecture for arbitrary graphs.[13][3] With T. Böhme and Thomason, he later established related bounds on minors in graphs of high chromatic number.[14]
Graph coloring
In a 1977 paper with Oleg Borodin, Kostochka introduced what became known as the Borodin–Kostochka conjecture: every graph with maximum degree Δ ≥ 9 whose clique number satisfies ω ≤ Δ − 1 has chromatic number at most Δ − 1.[15][4] The conjecture, which strengthens Brooks' theorem, remains open in general; Bruce Reed proved it for sufficiently large maximum degree in 1999, and it has been verified for various restricted classes of graphs.[4][16] Kostochka has also worked on the total chromatic number of multigraphs and on defective and improper colorings of sparse graphs.[10]
Editorial and other activities
Kostochka serves on the editorial board of the journal Diskretnyi Analiz i Issledovanie Operatsii (published in English translation as the Journal of Applied and Industrial Mathematics).[17] He edited a volume of Topics in Graph Theory dedicated to the ninetieth birthday of the graph theorist Alexander Zykov (1922–2013).[1][5]
Selected publications
- Borodin, O. V.; Kostochka, A. V. (1977). "On an upper bound of a graph's chromatic number, depending on the graph's degree and density". Journal of Combinatorial Theory, Series B. 23 (2–3): 247–250. doi:10.1016/0095-8956(77)90037-5.
- Kostochka, A. V. (1984). "Lower bound of the Hadwiger number of graphs by their average degree". Combinatorica. 4 (4): 307–316. doi:10.1007/BF02579141.
- Kostochka, A. V.; Stiebitz, M.; Wirth, B. (1996). "The colour theorems of Brooks and Gallai extended". Discrete Mathematics. 162 (1–3): 299–303. doi:10.1016/0012-365X(95)00294-7.
- Böhme, T.; Kostochka, A.; Thomason, A. (2011). "Minors in graphs with high chromatic number". Combinatorics, Probability and Computing. 20 (4): 513–518. doi:10.1017/S0963548311000174.