| Publication | Date of Publication | Type |
|---|
Spanning trees in graphs of high minimum degree with a universal vertex II: A tight result
Journal of Graph Theory | 2023-10-09 | Paper |
Spanning trees in graphs of high minimum degree with a universal vertex I: An asymptotic result
Journal of Graph Theory | 2023-10-09 | Paper |
Notes on tree- and path-chromatic number
| 2021-12-10 | Paper |
Tight bounds on the clique chromatic number
The Electronic Journal of Combinatorics | 2021-09-28 | Paper |
Cops and robbers on oriented toroidal grids
Theoretical Computer Science | 2021-01-25 | Paper |
Tight Bounds on the Clique Chromatic Number
| 2020-06-19 | Paper |
A lower bound on the average degree forcing a minor
The Electronic Journal of Combinatorics | 2020-06-15 | Paper |
A variant of the Erdős-Sós conjecture
Journal of Graph Theory | 2020-05-21 | Paper |
Corrigendum to: ``Bisimplicial vertices in even-hole-free graphs
Journal of Combinatorial Theory. Series B | 2020-04-07 | Paper |
Notes on growing a tree in a graph
Random Structures \& Algorithms | 2019-11-07 | Paper |
Near-domination in graphs
Journal of Combinatorial Theory. Series A | 2019-06-25 | Paper |
A Simple Algorithm for the Graph Minor Decomposition − Logic meets Structural Graph Theory–
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-05-15 | Paper |
scientific article; zbMATH DE number 7051289 (Why is no real title available?)
| 2019-05-06 | Paper |
Asymptotically optimal frugal colouring
| 2019-05-06 | Paper |
A logarithmic bound for the chromatic number of the associahedron
| 2018-11-21 | Paper |
Polyhedral results on the stable set problem in graphs containing even or odd pairs
Mathematical Programming. Series A. Series B | 2018-09-28 | Paper |
How to determine if a random graph with a fixed degree sequence has a giant component
Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete | 2018-02-12 | Paper |
Colourings with Bounded Monochromatic Components in Graphs of Given Circumference
| 2017-12-06 | Paper |
Forcing a sparse minor
Combinatorics, Probability and Computing | 2017-10-10 | Paper |
Existence of spanning \(\mathcal{F}\)-free subgraphs with large minimum degree
Combinatorics, Probability and Computing | 2017-10-10 | Paper |
Corrigendum: ``Forcing a sparse minor
Combinatorics, Probability and Computing | 2017-10-10 | Paper |
Building your path to escape from home
| 2017-09-29 | Paper |
Acyclic edge colourings of graphs with large girth
Random Structures \& Algorithms | 2017-08-10 | Paper |
\(k\)-colouring when \(k\) is close to \(\Delta\)
| 2016-07-01 | Paper |
A short proof that \(\chi\) can be bounded \(\epsilon\) away from \(\Delta + 1\) toward \(\omega\)
Journal of Graph Theory | 2016-02-01 | Paper |
The height of a random binary search tree
Journal of the ACM | 2015-11-12 | Paper |
Connectivity Preserving Iterative Compaction and Finding 2 Disjoint Rooted Paths in Linear Time
| 2015-09-25 | Paper |
A proof of a conjecture of Ohba
Journal of Graph Theory | 2015-05-22 | Paper |
Excluding a substar and an antisubstar
SIAM Journal on Discrete Mathematics | 2015-05-20 | Paper |
An improved algorithm for finding tree decompositions of small width
International Journal of Foundations of Computer Science | 2015-04-29 | Paper |
Claw-free graphs, skeletal graphs, and a stronger conjecture on \(\omega\), \(\Delta\), and \(\chi\)
Journal of Graph Theory | 2015-03-24 | Paper |
Colouring graphs when the number of colours is nearly the maximum degree
Proceedings of the thirty-third annual ACM symposium on Theory of computing | 2015-02-27 | Paper |
Hadwiger's conjecture is decidable
Proceedings of the forty-first annual ACM symposium on Theory of computing | 2015-02-04 | Paper |
A linear-time algorithm to find a separator in a graph excluding a minor
ACM Transactions on Algorithms | 2014-11-18 | Paper |
For most graphs \(H\), most \(H\)-free graphs have a linear homogeneous set
Random Structures \& Algorithms | 2014-11-17 | Paper |
Colouring graphs when the number of colours is almost the maximum degree
Journal of Combinatorial Theory. Series B | 2014-10-22 | Paper |
A Density Version of the Corradi-Hajnal Theorem
| 2014-10-01 | Paper |
How tall is a tree?
Proceedings of the thirty-second annual ACM symposium on Theory of computing | 2014-09-26 | Paper |
Removable paths and cycles with parity constraints
Journal of Combinatorial Theory. Series B | 2014-08-28 | Paper |
Odd cycle packing
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
The Graph Minor Algorithm with Parity Conditions
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science | 2014-07-30 | Paper |
Recognizing a totally odd \(K_{4}\)-subdivision, parity 2-disjoint rooted paths and a parity cycle through specified elements
| 2014-05-22 | Paper |
scientific article; zbMATH DE number 6297714 (Why is no real title available?)
| 2014-05-22 | Paper |
A Linear-Time Algorithm for Finding a Complete Graph Minor in a Dense Graph
SIAM Journal on Discrete Mathematics | 2014-04-10 | Paper |
A general critical condition for the emergence of a giant component in random graphs with given degrees
Electronic Notes in Discrete Mathematics | 2013-10-10 | Paper |
Fractionally edge colouring graphs with large maximum degree in linear time
Electronic Notes in Discrete Mathematics | 2013-10-10 | Paper |
Digraph girth via chromatic number
SIAM Journal on Discrete Mathematics | 2013-09-26 | Paper |
Asymptotics of the chromatic number for quasi-line graphs
Journal of Graph Theory | 2013-07-31 | Paper |
A characterization of graphs with fractional total chromatic number equal to \(\Delta +2\)
Electronic Notes in Discrete Mathematics | 2013-07-19 | Paper |
Oriented trees in digraphs
Discrete Mathematics | 2013-04-15 | Paper |
Connectivity for Bridge-addable monotone graph classes
Combinatorics, Probability and Computing | 2012-10-31 | Paper |
Griggs and Yeh's conjecture and \(L(p,1)\)-labelings
SIAM Journal on Discrete Mathematics | 2012-08-22 | Paper |
Polynomial-time recognition of clique-width \(\leq 3\) graphs
Discrete Applied Mathematics | 2012-05-11 | Paper |
The disjoint paths problem in quadratic time
Journal of Combinatorial Theory. Series B | 2012-05-04 | Paper |
Polynomial treewidth forces a large grid-like-minor
European Journal of Combinatorics | 2012-02-11 | Paper |
Almost all \(H\)-free graphs have the Erdős-Hajnal property
| 2011-02-18 | Paper |
The edge-density for \(K_{2,t}\) minors
Journal of Combinatorial Theory. Series B | 2011-01-14 | Paper |
Critical random graphs and the structure of a minimum spanning tree
Random Structures \& Algorithms | 2010-11-09 | Paper |
Highly parity linked graphs
Combinatorica | 2010-08-13 | Paper |
scientific article; zbMATH DE number 5764899 (Why is no real title available?)
| 2010-08-06 | Paper |
scientific article; zbMATH DE number 5764892 (Why is no real title available?)
| 2010-08-06 | Paper |
Fast separation in a graph with an excluded minor
| 2010-07-30 | Paper |
An upper bound for the chromatic number of line graphs
| 2010-07-30 | Paper |
scientific article; zbMATH DE number 5730481 (Why is no real title available?)
| 2010-07-05 | Paper |
Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph
Discrete Applied Mathematics | 2010-05-25 | Paper |
Tree-width of graphs without a \(3\times 3\) grid minor
Discrete Applied Mathematics | 2010-04-28 | Paper |
Asymptotically optimal frugal colouring
Journal of Combinatorial Theory. Series B | 2010-04-21 | Paper |
Corrigendum to ``Asymptotically optimal frugal colouring [J. Comb. Theory, Ser. B 100, No. 2, 226--246 (2010)]
Journal of Combinatorial Theory. Series B | 2010-04-21 | Paper |
Minima in branching random walks
The Annals of Probability | 2009-07-28 | Paper |
Coloring Artemis graphs
Theoretical Computer Science | 2009-05-28 | Paper |
On Planar Quasi-Parity Graphs
SIAM Journal on Discrete Mathematics | 2009-03-16 | Paper |
Bounding χ in terms of ω and Δ for quasi-line graphs
Journal of Graph Theory | 2009-02-20 | Paper |
Properly 2-Colouring Linear Hypergraphs
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-02-17 | Paper |
On the odd-minor variant of Hadwiger's conjecture
Journal of Combinatorial Theory. Series B | 2009-01-21 | Paper |
Removable cycles in non-bipartite graphs
Journal of Combinatorial Theory. Series B | 2009-01-21 | Paper |
Domination in Cubic Graphs of Large Girth
Computational Geometry and Graph Theory | 2009-01-13 | Paper |
Fast Skew Partition Recognition
Computational Geometry and Graph Theory | 2009-01-13 | Paper |
scientific article; zbMATH DE number 5485473 (Why is no real title available?)
| 2009-01-05 | Paper |
Bisimplicial vertices in even-hole-free graphs
Journal of Combinatorial Theory. Series B | 2008-12-08 | Paper |
A weaker version of Lovász' path removal conjecture
Journal of Combinatorial Theory. Series B | 2008-10-07 | Paper |
On the Maximum Degree of a Random Planar Graph
Combinatorics, Probability and Computing | 2008-09-29 | Paper |
Partition into cliques for cubic graphs: Planar case, complexity and approximation
Discrete Applied Mathematics | 2008-09-29 | Paper |
The evolution of the mixing rate of a simple random walk on the giant component of a random graph
Random Structures \& Algorithms | 2008-09-04 | Paper |
Ballot theorems, old and new
| 2008-07-01 | Paper |
Asymptotics of the chromatic number for quasi-line graphs
Electronic Notes in Discrete Mathematics | 2008-06-05 | Paper |
List Colouring Squares of Planar Graphs
Electronic Notes in Discrete Mathematics | 2008-06-05 | Paper |
List Colouring Constants of Triangle Free Graphs
Electronic Notes in Discrete Mathematics | 2008-06-05 | Paper |
Degree constrained subgraphs
Discrete Applied Mathematics | 2008-04-16 | Paper |
Planar graph bipartization in linear time
Discrete Applied Mathematics | 2008-04-16 | Paper |
Skew partitions in perfect graphs
Discrete Applied Mathematics | 2008-04-16 | Paper |
Fractionally total colouring \(G_{n,p}\)
Discrete Applied Mathematics | 2008-04-16 | Paper |
Optimization and Recognition for K 5-minor Free Graphs in Linear Time
Lecture Notes in Computer Science | 2008-04-15 | Paper |
Fractional coloring and the odd Hadwiger's conjecture
European Journal of Combinatorics | 2008-02-25 | Paper |
Ballot theorems for random walks with finite variance
| 2008-02-18 | Paper |
Vertex-colouring edge-weightings
Combinatorica | 2008-01-14 | Paper |
An upper bound for the chromatic number of line graphs
European Journal of Combinatorics | 2007-11-21 | Paper |
The Erdős-Pósa property for long circuits
Combinatorica | 2007-11-12 | Paper |
Approximate Min-max Relations for Odd Cycles in Planar Graphs
Integer Programming and Combinatorial Optimization | 2007-08-30 | Paper |
Vašek Chvátal: a very short introduction (on the occasion of his 60th birthday)
Graphs and Combinatorics | 2007-07-19 | Paper |
scientific article; zbMATH DE number 5158516 (Why is no real title available?)
| 2007-05-29 | Paper |
scientific article; zbMATH DE number 5158511 (Why is no real title available?)
| 2007-05-29 | Paper |
scientific article; zbMATH DE number 5158512 (Why is no real title available?)
| 2007-05-29 | Paper |
A note on Random Homomorphism from ArbitraryGraphs to Z
Electronic Notes in Discrete Mathematics | 2007-05-29 | Paper |
Channel Assignment on Nearly Bipartite and Bounded Treewidth Graphs
Electronic Notes in Discrete Mathematics | 2007-05-29 | Paper |
Bull-Reducible Berge Graphs are Perfect
Electronic Notes in Discrete Mathematics | 2007-05-29 | Paper |
Approximate min-max relations for odd cycles in planar graphs
Mathematical Programming. Series A. Series B | 2007-04-19 | Paper |
On six problems posed by Jarik Nešetřil
| 2007-03-05 | Paper |
Brambles, prisms and grids
| 2007-03-05 | Paper |
Concentration for self-bounding functions and an inequality of Talagrand
Random Structures \& Algorithms | 2007-02-07 | Paper |
Faster mixing and small bottlenecks
Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete | 2007-01-26 | Paper |
Algorithms and Data Structures
Lecture Notes in Computer Science | 2006-10-25 | Paper |
On the Co-P3 -Structure of Perfect Graphs
SIAM Journal on Discrete Mathematics | 2005-09-16 | Paper |
On the fractional chromatic index of a graph and its complement
Operations Research Letters | 2005-08-25 | Paper |
Vertex colouring edge partitions
Journal of Combinatorial Theory. Series B | 2005-08-05 | Paper |
List colouring when the chromatic number is close to the order of the graph
Combinatorica | 2005-07-05 | Paper |
The perfection and recognition of bull-reducible Berge graphs
RAIRO - Theoretical Informatics and Applications | 2005-06-07 | Paper |
(\(\Delta-k\))-critical graphs
Journal of Combinatorial Theory. Series B | 2005-03-08 | Paper |
Star coloring of graphs
Journal of Graph Theory | 2005-02-16 | Paper |
Finding odd cycle transversals.
Operations Research Letters | 2005-01-11 | Paper |
Stable skew partition problem
Discrete Applied Mathematics | 2004-11-23 | Paper |
Hadwiger's conjecture for line graphs
European Journal of Combinatorics | 2004-10-04 | Paper |
Excluding any graph as a minor allows a low tree-width 2-coloring
Journal of Combinatorial Theory. Series B | 2004-08-06 | Paper |
Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width
Journal of Algorithms | 2004-03-14 | Paper |
scientific article; zbMATH DE number 2044931 (Why is no real title available?)
| 2004-02-18 | Paper |
scientific article; zbMATH DE number 1775440 (Why is no real title available?)
| 2004-01-27 | Paper |
Channel assignment on graphs of bounded treewidth
Discrete Mathematics | 2004-01-05 | Paper |
A note on random homomorphism from arbitrary graphs to \(\mathbb{Z}\)
Discrete Mathematics | 2004-01-05 | Paper |
scientific article; zbMATH DE number 1984542 (Why is no real title available?)
| 2003-09-22 | Paper |
Random Regular Graphs of Non-Constant Degree: Connectivity and Hamiltonicity
Combinatorics, Probability and Computing | 2003-02-11 | Paper |
scientific article; zbMATH DE number 1944139 (Why is no real title available?)
| 2003-01-01 | Paper |
Asymptotically the list colouring constants are 1
Journal of Combinatorial Theory. Series B | 2002-12-10 | Paper |
Random Regular Graphs of Non-Constant Degree: Independence and Chromatic Number
Combinatorics, Probability and Computing | 2002-11-12 | Paper |
scientific article; zbMATH DE number 1789917 (Why is no real title available?)
| 2002-11-07 | Paper |
Recognizing planar strict quasi-parity graphs
Graphs and Combinatorics | 2002-08-08 | Paper |
Even pairs
| 2002-07-28 | Paper |
scientific article; zbMATH DE number 1512686 (Why is no real title available?)
| 2002-05-14 | Paper |
Forbidding holes and antiholes
| 2002-04-16 | Paper |
From conjecture to theorem
| 2002-04-16 | Paper |
scientific article; zbMATH DE number 1286500 (Why is no real title available?)
| 2002-03-04 | Paper |
The Erdős-Pósa property for odd cycles in highly connected graphs
Combinatorica | 2002-02-13 | Paper |
Approximately covering by cycles in planar graphs.
| 2002-01-30 | Paper |
Introducing directed tree width
| 2001-09-23 | Paper |
Graph colouring and the probabilistic method
Algorithms and Combinatorics | 2001-09-02 | Paper |
scientific article; zbMATH DE number 1512682 (Why is no real title available?)
| 2001-05-13 | Paper |
scientific article; zbMATH DE number 1472140 (Why is no real title available?)
| 2001-01-14 | Paper |
A gentle introduction to semi-definite programming
| 2001-01-01 | Paper |
scientific article; zbMATH DE number 1545651 (Why is no real title available?)
| 2000-12-19 | Paper |
Near-optimal list colorings
| 2000-12-19 | Paper |
Channel assignment and weighted coloring
| 2000-12-03 | Paper |
scientific article; zbMATH DE number 1420905 (Why is no real title available?)
| 2000-10-08 | Paper |
Clique minors in graphs and their complements
Journal of Combinatorial Theory. Series B | 2000-06-25 | Paper |
Fractional colouring and Hadwiger's conjecture
Journal of Combinatorial Theory. Series B | 2000-06-25 | Paper |
A description of claw-free perfect graphs
Journal of Combinatorial Theory. Series B | 2000-04-04 | Paper |
Optimal packings of edge-disjoint odd cycles
Discrete Mathematics | 2000-03-19 | Paper |
Critical subgraphs of a random graph
The Electronic Journal of Combinatorics | 2000-01-16 | Paper |
Mangoes and blueberries
Combinatorica | 1999-12-20 | Paper |
A strengthening of Brooks' theorem
Journal of Combinatorial Theory. Series B | 1999-12-20 | Paper |
scientific article; zbMATH DE number 1303525 (Why is no real title available?)
| 1999-11-08 | Paper |
Colouring proximity graphs in the plane
Discrete Mathematics | 1999-11-03 | Paper |
A bound on the total chromatic number
Combinatorica | 1999-09-14 | Paper |
scientific article; zbMATH DE number 1251573 (Why is no real title available?)
| 1999-08-19 | Paper |
scientific article; zbMATH DE number 1241392 (Why is no real title available?)
| 1999-08-17 | Paper |
The Size of the Giant Component of a Random Graph with a Given Degree Sequence
Combinatorics, Probability and Computing | 1999-07-19 | Paper |
Edge-disjoint odd cycles in graphs with small chromatic numbers
Annales de l’institut Fourier | 1999-07-12 | Paper |
scientific article; zbMATH DE number 1299964 (Why is no real title available?)
| 1999-06-10 | Paper |
scientific article; zbMATH DE number 1187148 (Why is no real title available?)
| 1999-04-08 | Paper |
Colouring a graph frugally
Combinatorica | 1999-03-14 | Paper |
Total Coloring With $\Delta + \mbox\lowercasepoly(\log \Delta)$ Colors
SIAM Journal on Computing | 1999-02-22 | Paper |
scientific article; zbMATH DE number 1246226 (Why is no real title available?)
| 1999-01-27 | Paper |
Edge coloring nearly bipartite graphs
Operations Research Letters | 1999-01-01 | Paper |
Edge coloring regular graphs of high degree
Discrete Mathematics | 1998-12-15 | Paper |
scientific article; zbMATH DE number 1057879 (Why is no real title available?)
| 1998-09-14 | Paper |
scientific article; zbMATH DE number 1189240 (Why is no real title available?)
| 1998-08-13 | Paper |
Path parity and perfection
Discrete Mathematics | 1998-01-12 | Paper |
Packing directed circuits
Combinatorica | 1998-01-11 | Paper |
The Gallai-Younger conjecture for planar graphs
Combinatorica | 1998-01-07 | Paper |
An algorithm for finding homogeneous pairs
Discrete Applied Mathematics | 1997-11-09 | Paper |
On planar perfectly contractile graphs
Graphs and Combinatorics | 1997-09-19 | Paper |
A bound on the strong chromatic index of a graph
Journal of Combinatorial Theory. Series B | 1997-05-05 | Paper |
Paths, Stars and the Number Three
Combinatorics, Probability and Computing | 1997-03-06 | Paper |
Perfect Matchings in Random r-regular, s-uniform Hypergraphs
Combinatorics, Probability and Computing | 1997-03-06 | Paper |
On the Variance of the Height of Random Binary Search Trees
SIAM Journal on Computing | 1996-09-15 | Paper |
Covering the edges of a random graph by cliques
Combinatorica | 1996-06-05 | Paper |
When Is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem?
SIAM Journal on Computing | 1996-03-18 | Paper |
Recognizing bull-free perfect graphs
Graphs and Combinatorics | 1996-02-20 | Paper |
Almost Every Graph can be Covered by Linear Forests
Combinatorics, Probability and Computing | 1996-02-12 | Paper |
A critical point for random graphs with a given degree sequence
Random Structures \& Algorithms | 1995-10-23 | Paper |
The dominating number of a random cubic graph
Random Structures \& Algorithms | 1995-10-17 | Paper |
Multicoloured Hamilton cycles
The Electronic Journal of Combinatorics | 1995-05-22 | Paper |
Rooted routing in the plane
Discrete Applied Mathematics | 1995-04-10 | Paper |
Fractionally colouring total graphs
Combinatorica | 1994-08-29 | Paper |
scientific article; zbMATH DE number 475585 (Why is no real title available?)
| 1994-06-28 | Paper |
scientific article; zbMATH DE number 508832 (Why is no real title available?)
| 1994-06-26 | Paper |
The Strongly Connected Components of 1-in, 1-out
Combinatorics, Probability and Computing | 1994-05-05 | Paper |
Complete multi-partite cutsets in minimal imperfect graphs
Journal of Combinatorial Theory. Series B | 1994-05-05 | Paper |
scientific article; zbMATH DE number 475595 (Why is no real title available?)
| 1994-01-13 | Paper |
scientific article; zbMATH DE number 475586 (Why is no real title available?)
| 1994-01-06 | Paper |
scientific article; zbMATH DE number 426349 (Why is no real title available?)
| 1993-11-07 | Paper |
Polychromatic Hamilton cycles
Discrete Mathematics | 1993-10-17 | Paper |
Star arboricity
Combinatorica | 1993-03-10 | Paper |
On total colourings of graphs
Journal of Combinatorial Theory. Series B | 1993-01-01 | Paper |
scientific article; zbMATH DE number 68367 (Why is no real title available?)
| 1992-10-06 | Paper |
Acyclic coloring of graphs
Random Structures \& Algorithms | 1992-06-25 | Paper |
Linear arboricity of random regular graphs
Random Structures \& Algorithms | 1992-06-25 | Paper |
Greedy Matching on the Line
SIAM Journal on Computing | 1990-01-01 | Paper |
Some classes of perfectly orderable graphs
Journal of Graph Theory | 1989-01-01 | Paper |
Building heaps fast
Journal of Algorithms | 1989-01-01 | Paper |
\(P_ 4\)-comparability graphs
Discrete Mathematics | 1989-01-01 | Paper |
Threshold tolerance graphs
Journal of Graph Theory | 1988-01-01 | Paper |
Edge-colouring random graphs
Journal of Combinatorial Theory. Series B | 1988-01-01 | Paper |
A note on even pairs
Discrete Mathematics | 1988-01-01 | Paper |
A semi-strong perfect graph theorem
Journal of Combinatorial Theory. Series B | 1987-01-01 | Paper |
A note on short cycles in digraphs
Discrete Mathematics | 1987-01-01 | Paper |
A note on even pairs
Discrete Mathematics | 1987-01-01 | Paper |
scientific article; zbMATH DE number 4053682 (Why is no real title available?)
| 1986-01-01 | Paper |
A note on the semi-strong perfect graph conjecture
Discrete Mathematics | 1985-01-01 | Paper |
Asymptotically Optimal Proper Conflict-Free Colouring
| N/A | Paper |
Peaceful Colourings
| N/A | Paper |
Linear bounds on treewidth in terms of excluded planar minors
| N/A | Paper |
Vertex Ranking of Degenerate Graphs
| N/A | Paper |
