Alexandr V. Kostochka

  • University of Illinois at Urbana-Champaign, USA

According to our database1, Alexandr V. Kostochka authored at least 239 papers between 1976 and 2023.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of one.



In proceedings 
PhD thesis 


Online presence:



Generalized DP-colorings of graphs.
Discret. Math., November, 2023

Saturation for the 3-uniform loose 3-cycle.
Discret. Math., November, 2023

A sharp lower bound for the spectral radius in <i>K</i><sub>4</sub>-saturated graphs.
Discret. Math., 2023

Longest cycles in 3-connected hypergraphs and bipartite graphs.
J. Graph Theory, 2022

Monochromatic connected matchings in 2-edge-colored multipartite graphs.
J. Graph Theory, 2022

Defective DP-colorings of sparse simple graphs.
Discret. Math., 2022

Monochromatic paths and cycles in 2-edge-coloured graphs with large minimum degree.
Comb. Probab. Comput., 2022

Towards the Small Quasi-Kernel Conjecture.
Electron. J. Comb., 2022

On Reconstruction of Graphs From the Multiset of Subgraphs Obtained by Deleting ℓ Vertices.
IEEE Trans. Inf. Theory, 2021

Partitioning ordered hypergraphs.
J. Comb. Theory, Ser. A, 2021

Cut-Edges and Regular Factors in Regular Graphs of Odd Degree.
Graphs Comb., 2021

On 2-defective DP-colorings of sparse graphs.
Eur. J. Comb., 2021

Injective edge-coloring of graphs with given maximum degree.
Eur. J. Comb., 2021

3-regular graphs are 2-reconstructible.
Eur. J. Comb., 2021

Defective DP-colorings of sparse multigraphs.
Eur. J. Comb., 2021

Packing (1, 1, 2, 4)-coloring of subcubic outerplanar graphs.
Discret. Appl. Math., 2021

Conditions for a Bigraph to be Super-Cyclic.
Electron. J. Comb., 2021

Fractional DP-colorings of sparse graphs.
J. Graph Theory, 2020

Super-pancyclic hypergraphs and bipartite graphs.
J. Comb. Theory, Ser. B, 2020

The Minimum Number of Edges in 4-Critical Digraphs of Given Order.
Graphs Comb., 2020

Degree Lists and Connectedness are 3-Reconstructible for Graphs with At Least Seven Vertices.
Graphs Comb., 2020

The minimum spectral radius of Kr+1-saturated graphs.
Discret. Math., 2020

Ordered and Convex Geometric Trees with Linear Extremal Function.
Discret. Comput. Geom., 2020

On r-uniform hypergraphs with circumference less than r.
Discret. Appl. Math., 2020

On-line DP-coloring of graphs.
Discret. Appl. Math., 2020

Hypergraphs not containing a tight tree with a bounded trunk II: 3-trees with a trunk of size 2.
Discret. Appl. Math., 2020

Berge Cycles in Non-Uniform Hypergraphs.
Electron. J. Comb., 2020

Hypergraphs Not Containing a Tight Tree with a Bounded Trunk.
SIAM J. Discret. Math., 2019

Avoiding long Berge cycles.
J. Comb. Theory, Ser. B, 2019

Largest 2-Regular Subgraphs in 3-Regular Graphs.
Graphs Comb., 2019

Extremal Union-Closed Set Families.
Graphs Comb., 2019

Packing Chromatic Number of Subdivisions of Cubic Graphs.
Graphs Comb., 2019

DP-colorings of hypergraphs.
Eur. J. Comb., 2019

A variation of a theorem by Pósa.
Discret. Math., 2019

On 2-Connected Hypergraphs with No Long Cycles.
Electron. J. Comb., 2019

Cubic Graphs with Small Independence Ratio.
Electron. J. Comb., 2019

Directed Intersection Representations and the Information Content of Digraphs.
Proceedings of the IEEE International Symposium on Information Theory, 2019

Extensions of a theorem of Erdős on nonhamiltonian graphs.
J. Graph Theory, 2018

Sharp Dirac's theorem for DP-critical graphs.
J. Graph Theory, 2018

Strong edge-colorings of sparse graphs with large maximum degree.
Eur. J. Comb., 2018

List star edge-coloring of subcubic graphs.
Discuss. Math. Graph Theory, 2018

Stability in the Erdős-Gallai Theorem on cycles and paths, II.
Discret. Math., 2018

Packing chromatic number of cubic graphs.
Discret. Math., 2018

A Sharp Dirac-Erdős Type Bound for Large Graphs.
Comb. Probab. Comput., 2018

A Brooks-Type Result for Sparse Critical Graphs.
Comb., 2018

Strengthening Theorems of Dirac and Erdős on Disjoint Cycles.
J. Graph Theory, 2017

Tight Descriptions of 3-Paths in Normal Plane Maps : Dedicated to Andre Raspaud on the occasion of his 70th birthday.
J. Graph Theory, 2017

Turán problems and shadows II: Trees.
J. Comb. Theory, Ser. B, 2017

On the Corrádi-Hajnal theorem and a question of Dirac.
J. Comb. Theory, Ser. B, 2017

Decomposition of sparse graphs into forests: The Nine Dragon Tree Conjecture for k ≤ 2.
J. Comb. Theory, Ser. B, 2017

DP-colorings of graphs with high chromatic number.
Eur. J. Comb., 2017

A stability version for a theorem of Erdős on nonhamiltonian graphs.
Discret. Math., 2017

Cycles in triangle-free graphs of large chromatic number.
Comb., 2017

The (2k-1)-connected multigraphs with at most k-1 disjoint cycles.
Comb., 2017

Improper Coloring of Sparse Graphs with a Given Girth, II: Constructions.
J. Graph Theory, 2016

Stability in the Erdős-Gallai Theorems on cycles and paths.
J. Comb. Theory, Ser. B, 2016

Strong chromatic index of subcubic planar multigraphs.
Eur. J. Comb., 2016

On a packing problem of Alon and Yuster.
Discret. Math., 2016

A list version of graph packing.
Discret. Math., 2016

On the number of edges in a graph with no (k+1)-connected subgraphs.
Discret. Math., 2016

Adding Edges to Increase the Chromatic Number of a Graph.
Comb. Probab. Comput., 2016

Turán Problems and Shadows III: Expansions of Graphs.
SIAM J. Discret. Math., 2015

Turán problems and shadows I: Paths and cycles.
J. Comb. Theory, Ser. A, 2015

The minimum number of edges in a 4-critical graph that is bipartite plus 3 edges.
Eur. J. Comb., 2015

A refinement of a result of Corrádi and Hajnal.
Comb., 2015

On independent sets in hypergraphs.
Random Struct. Algorithms, 2014

Ks, t Minors in (s+t)- Chromatic Graphs, II.
J. Graph Theory, 2014

Choosability with Separation of Complete Multipartite Graphs and Hypergraphs.
J. Graph Theory, 2014

Ore's conjecture on color-critical graphs is almost true.
J. Comb. Theory, Ser. B, 2014

Defective 2-colorings of sparse graphs.
J. Comb. Theory, Ser. B, 2014

Improper coloring of sparse graphs with a given girth, I: (0, 1)-colorings of triangle-free graphs.
Eur. J. Comb., 2014

Short proofs of coloring theorems on planar graphs.
Eur. J. Comb., 2014

Planar 4-critical graphs with four triangles.
Eur. J. Comb., 2014

Maximum hypergraphs without regular subgraphs.
Discuss. Math. Graph Theory, 2014

A new tool for proving Vizing's Theorem.
Discret. Math., 2014

Describing faces in plane triangulations.
Discret. Math., 2014

Every 3-polytope with minimum degree 5 has a 6-cycle with maximum degree at most 11.
Discret. Math., 2014

Ore's conjecture for k=4 and Grötzsch's Theorem.
Comb., 2014

A Hypergraph Version of a Graph Packing Theorem by Bollobás and Eldridge.
J. Graph Theory, 2013

Decomposition of Sparse Graphs into Forests and a Graph with Bounded Degree.
J. Graph Theory, 2013

Equitable List Coloring of Graphs with Bounded Degree.
J. Graph Theory, 2013

Hypergraph Ramsey numbers: Triangles versus cliques.
J. Comb. Theory, Ser. A, 2013

Coloring some finite sets in <i> R<sup>n</sup> </i>.
Discuss. Math. Graph Theory, 2013

On almost (k-1)-degenerate (k+1)-chromatic graphs and hypergraphs.
Discret. Math., 2013

On 11-improper 22-coloring of sparse graphs.
Discret. Math., 2013

Describing 3-paths in normal plane maps.
Discret. Math., 2013

On Perfect Packings in Dense Graphs.
Electron. J. Comb., 2013

On Coloring of Sparse Graphs.
Proceedings of the Computer Science - Theory and Applications, 2013

A Bound of the Cardinality of Families Not Containing \(\Delta \) -Systems.
Proceedings of the Mathematics of Paul Erdős II, 2013

Every 4-Colorable Graph With Maximum Degree 4 Has an Equitable 4-Coloring.
J. Graph Theory, 2012

Graphs Containing Every 2-Factor.
Graphs Comb., 2012

Packing and Covering Triangles in K 4-free Planar Graphs.
Graphs Comb., 2012

A stability theorem on fractional covering of triangles by edges.
Eur. J. Comb., 2012

Graphs with chromatic number close to maximum degree.
Discret. Math., 2012

On K<sub>s, t</sub>-minors in graphs with given average degree, II.
Discret. Math., 2012

Dense uniform hypergraphs have high list chromatic number.
Discret. Math., 2012

Harmonious coloring of trees with large maximum degree.
Discret. Math., 2012

Large Rainbow Matchings in Edge-Coloured Graphs.
Comb. Probab. Comput., 2012

Conflict-Free Colourings of Uniform Hypergraphs With Few Edges.
Comb. Probab. Comput., 2012

Hypergraph list coloring and Euclidean Ramsey theory.
Random Struct. Algorithms, 2011

Ohba's conjecture for graphs with independence number five.
Discret. Math., 2011

Large minors in graphs with given independence number.
Discret. Math., 2011

Minors in Graphs with High Chromatic Number.
Comb. Probab. Comput., 2011

Graphs with maximum degree 5 are acyclically 7-colorable.
Ars Math. Contemp., 2011

Constructions of sparse uniform hypergraphs with high chromatic number.
Random Struct. Algorithms, 2010

On <i>K</i><sub><i>s, t</i></sub> minors in (<i>s</i>+<i>t</i>)-chromatic graphs.
J. Graph Theory, 2010

Some constructive bounds on Ramsey numbers.
J. Comb. Theory, Ser. B, 2010

Graphs with bounded tree-width and large odd-girth are almost bipartite.
J. Comb. Theory, Ser. B, 2010

Dense graphs have K<sub>3, t</sub> minors.
Discret. Math., 2010

Hadwiger numbers and over-dominating colourings.
Discret. Math., 2010

A fast algorithm for equitable coloring.
Comb., 2010

Equitable versus nearly equitable coloring and the Chen-Lih-Wu conjecture.
Comb., 2010

Coloring uniform hypergraphs with few edges.
Random Struct. Algorithms, 2009

Induced subgraphs with distinct sizes.
Random Struct. Algorithms, 2009

<i>M</i>-degrees of quadrangle-free planar graphs.
J. Graph Theory, 2009

Ore-type versions of Brooks' theorem.
J. Comb. Theory, Ser. B, 2009

Decompositions of quadrangle-free planar graphs.
Discuss. Math. Graph Theory, 2009

Ore-type conditions implying 2-factors consisting of short cycles.
Discret. Math., 2009

An upper bound on the domination number of n-vertex connected cubic graphs.
Discret. Math., 2009

A Brooks-type bound for squares of K<sub>4</sub>-minor-free graphs.
Discret. Math., 2009

Planar graphs decomposable into a forest and a matching.
Discret. Math., 2009

Many disjoint dense subgraphs versus large k-connected subgraphs in large graphs with given edge density.
Discret. Math., 2009

The Erdos-Lovász Tihany conjecture for quasi-line graphs.
Discret. Math., 2009

Efficient Graph Packing via Game Colouring.
Comb. Probab. Comput., 2009

Sizes of Induced Subgraphs of Ramsey Graphs.
Comb. Probab. Comput., 2009

Adapted List Coloring of Graphs and Hypergraphs.
SIAM J. Discret. Math., 2008

Ore-type degree conditions for a graph to be <i>H</i>-linked.
J. Graph Theory, 2008

On <i>k</i>-detour subgraphs of hypercubes.
J. Graph Theory, 2008

Packing of graphs with small product of sizes.
J. Comb. Theory, Ser. B, 2008

An Ore-type theorem on equitable coloring.
J. Comb. Theory, Ser. B, 2008

Packing d-degenerate graphs.
J. Comb. Theory, Ser. B, 2008

Hadwiger Number and the Cartesian Product of Graphs.
Graphs Comb., 2008

On 2-Detour Subgraphs of the Hypercube.
Graphs Comb., 2008

Decomposing a planar graph with girth 9 into a forest and a matching.
Eur. J. Comb., 2008

On K<sub>s, t</sub>-minors in graphs with given average degree.
Discret. Math., 2008

When is an Almost Monochromatic <i>K</i><sub>4</sub> Guaranteed?
Comb. Probab. Comput., 2008

A Short Proof of the Hajnal-Szemerédi Theorem on Equitable Colouring.
Comb. Probab. Comput., 2008

Partitions and Edge Colourings of Multigraphs.
Electron. J. Comb., 2008

On a graph packing conjecture by Bollobás, Eldridge and Catlin.
Comb., 2008

An Ore-type analogue of the Sauer-Spencer Theorem.
Graphs Comb., 2007

Tree representations of graphs.
Eur. J. Comb., 2007

Ore-type graph packing problems.
Comb. Probab. Comput., 2007

Extremal Graphs for a Graph Packing Theorem of Sauer and Spencer.
Comb. Probab. Comput., 2007

On Directed Triangles in Digraphs.
Electron. J. Comb., 2007

On Minimum Degree Implying That a Graph is H-Linked.
SIAM J. Discret. Math., 2006

On Ramsey numbers of uniform hypergraphs with given maximum degree.
J. Comb. Theory, Ser. A, 2006

Dominating sets in k-majority tournaments.
J. Comb. Theory, Ser. B, 2006

Chvátal's Condition cannot hold for both a graph and its complement.
Discuss. Math. Graph Theory, 2006

On Sufficient Degree Conditions for a Graph to be k-linked.
Comb. Probab. Comput., 2006

On equitable <i>Delta</i>-coloring of graphs with low average degree.
Theor. Comput. Sci., 2005

On Equitable Coloring of d-Degenerate Graphs.
SIAM J. Discret. Math., 2005

An extremal problem for <i>H</i>-linked graphs.
J. Graph Theory, 2005

Nordhaus-Gaddum-type Theorems for decompositions into many parts.
J. Graph Theory, 2005

Even cycles in hypergraphs.
J. Comb. Theory, Ser. B, 2005

Minimum degree conditions for H-linked graphs.
Electron. Notes Discret. Math., 2005

Irreducible hypergraphs for Hall-type conditions, and arc-minimal digraph expanders.
Eur. J. Comb., 2005

Disjoint <i>K<sub>r</sub></i>-minors in large graphs with given average degree.
Eur. J. Comb., 2005

On domination in connected cubic graphs.
Discret. Math., 2005

Smaller planar triangle-free graphs that are not 3-list-colorable.
Discret. Math., 2005

Precoloring Extensions of Brooks' Theorem.
SIAM J. Discret. Math., 2004

Coloring uniform hypergraphs with few colors.
Random Struct. Algorithms, 2004

Homomorphisms from sparse graphs with large girth.
J. Comb. Theory, Ser. B, 2004

Balanced edge colorings.
J. Comb. Theory, Ser. B, 2004

On the Chromatic Number of Intersection Graphs of Convex Sets in the Plane.
Electron. J. Comb., 2004

On Graphs With Small Ramsey Numbers, II.
Comb., 2004

Decomposing Graphs into Long Paths.
Order, 2003

A list analogue of equitable coloring.
J. Graph Theory, 2003

Degree conditions for <i>k</i>-ordered hamiltonian graphs.
J. Graph Theory, 2003

A new lower bound on the number of edges in colour-critical graphs and hypergraphs.
J. Comb. Theory, Ser. B, 2003

On Ramsey Numbers of Sparse Graphs.
Comb. Probab. Comput., 2003

Equitable Colourings Of D-Degenerate Graphs.
Comb. Probab. Comput., 2003

Equitable colorings with constant number of colors.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Total choosability of multicircuits II.
J. Graph Theory, 2002

Total choosability of multicircuits I.
J. Graph Theory, 2002

A list version of Dirac's theorem on the number of edges in colour-critical graphs.
J. Graph Theory, 2002

Acyclic list 7-coloring of planar graphs.
J. Graph Theory, 2002

Nilpotent Families of Endomorphisms of (p(V)+, cup).
J. Comb. Theory, Ser. B, 2002

Colouring Relatives of Intervals on the Plane, II: Intervals and Rays in Two Directions.
Eur. J. Comb., 2002

Equitable colorings of outerplanar graphs.
Discret. Math., 2002

On a Theorem of Erdos, Rubin, and Taylor on Choosability of Complete Bipartite Graphs.
Electron. J. Comb., 2002

Transversals in Uniform Hypergraphs with Property (p, 2).
Comb., 2002

On the chromatic number of set systems.
Random Struct. Algorithms, 2001

On graphs with small Ramsey numbers.
J. Graph Theory, 2001

On Deeply Critical Oriented Graphs.
J. Comb. Theory, Ser. B, 2001

Sparse sets in the complements of graphs with given girth.
Discret. Math., 2001

Choosability conjectures and multicircuits.
Discret. Math., 2001

Colorings and homomorphisms of degenerate and bounded degree graphs.
Discret. Math., 2001

On nice graphs.
Discret. Math., 2001

Acyclic colouring of 1-planar graphs.
Discret. Appl. Math., 2001

Density Conditions for Panchromatic Colourings of Hypergraphs.
Comb., 2001

Local and Mean Ramsey Numbers for Trees.
J. Comb. Theory, Ser. B, 2000

Vertex Set Partitions Preserving Conservativeness.
J. Comb. Theory, Ser. B, 2000

On the Number of Edges in Hypergraphs Critical with Respect to Strong Colourings.
Eur. J. Comb., 2000

Colouring triangle-free intersection graphs of boxes on the plane.
Discret. Math., 2000

On the Hajo's number of graphs.
Discret. Math., 2000

On degrees of vertices in paradoxical trees.
Discret. Math., 2000

Variable degeneracy: extensions of Brooks' and Gallai's theorems.
Discret. Math., 2000

On the Number of Edges in Colour-Critical Graphs and Hypergraphs.
Comb., 2000

Hypercube subgraphs with local detours.
J. Graph Theory, 1999

Regular Honest Graphs, Isoperimetric Numbers, and Bisection of Weighted Graphs.
Eur. J. Comb., 1999

Transversals in uniform hypergraphs with property (7, 2).
Discret. Math., 1999

On the maximum average degree and the oriented chromatic number of a graph.
Discret. Math., 1999

Properties Of Descartes' Construction Of Triangle-Free Graphs With High Chromatic Number.
Comb. Probab. Comput., 1999

Partial Steiner systems and matchings in hypergraphs.
Random Struct. Algorithms, 1998

Coloring Relatives of Intervals on the Plane, I: Chromatic Number Versus Girth.
Eur. J. Comb., 1998

Total Colourings of Planar Graphs with Large Girth.
Eur. J. Comb., 1998

Colour-critical graphs with few edges.
Discret. Math., 1998

On the independent domination number of graphs with given minimum degree.
Discret. Math., 1998

On kernel-perfect orientations of line graphs.
Discret. Math., 1998

On universal graphs for planar oriented graphs of a given girth.
Discret. Math., 1998

On Large Systems of Sets with No Large Weak <Delta>-subsystems.
Comb., 1998

Total interval number for graphs with bounded degree.
J. Graph Theory, 1997

Acyclic and oriented chromatic numbers of graphs.
J. Graph Theory, 1997

Total colorings of planar graphs with large maximum degree.
J. Graph Theory, 1997

A characterization of Seymour graphs.
J. Graph Theory, 1997

Intersection Statements for Systems of Sets.
J. Comb. Theory, Ser. A, 1997

List Edge and List Total Colourings of Multigraphs.
J. Comb. Theory, Ser. B, 1997

Covering and coloring polygon-circle graphs.
Discret. Math., 1997

Graphs without short odd cycles are nearly bipartite.
Discret. Math., 1997

Spanning trees with pairwise nonadjacent endvertices.
Discret. Math., 1997

On the minimum number of edges giving maximum oriented chromatic number.
Proceedings of the Contemporary Trends in Discrete Mathematics: From DIMACS and DIMATIA to the Future, 1997

An intersection theorem for systems of sets.
Random Struct. Algorithms, 1996

The colour theorems of Brooks and Gallai extended.
Discret. Math., 1996

The total chromatic number of any multigraph with maximum degree five is at most seven.
Discret. Math., 1996

The Number of Spanning Trees in Graphs with Given Degree Sequence.
Random Struct. Algorithms, 1995

The 7/5-conjecture strengthens itself.
J. Graph Theory, 1995

On set systems without weak 3-Delta-subsystems.
Discret. Math., 1995

Radius and Diameter of Random Subgraphs of the Hypercube.
Random Struct. Algorithms, 1993

The independent domination number of a cubic 3-connected graph can be much larger than its domination number.
Graphs Comb., 1993

Covering boxes by points.
Discret. Math., 1993

List edge chromatic number of graphs with large girth.
Discret. Math., 1992

Matchings in Random Spanning Subgraphs of Cubelike Graphs.
Random Struct. Algorithms, 1990

Samll topological complete subgraphs of "dense" graphs.
Comb., 1988

Maximum set of edges no two covered by a clique.
Comb., 1985

Lower bound of the Hadwiger number of graphs by their average degree.
Comb., 1984

A class of constructions for Turán's (3, 4) problem.
Comb., 1982

On an upper bound of a graph's chromatic number, depending on the graph's degree and density.
J. Comb. Theory, Ser. B, 1977

The total coloring of a multigraph with maximal degree 4.
Discret. Math., 1977

Note to the paper of Grünbaum on acyclic colorings.
Discret. Math., 1976