2024
Vertex Ranking of Degenerate Graphs.
CoRR, 2024
2023
The speed and threshold of the biased perfect matching and Hamilton cycle games.
Discret. Appl. Math., June, 2023
Spanning trees in graphs of high minimum degree with a universal vertex II: A tight result.
J. Graph Theory, April, 2023
Spanning trees in graphs of high minimum degree with a universal vertex I: An asymptotic result.
J. Graph Theory, April, 2023
2021
Cops and robbers on oriented toroidal grids.
Theor. Comput. Sci., 2021
Tight Bounds on the Clique Chromatic Number.
Electron. J. Comb., 2021
The Speed and Threshold of the Biased Hamilton Cycle Game.
Proceedings of the XI Latin and American Algorithms, Graphs and Optimization Symposium, 2021
The Speed and Threshold of the Biased Perfect Matching Game.
Proceedings of the XI Latin and American Algorithms, Graphs and Optimization Symposium, 2021
Partitioning Into Prescribed Number of Cycles and Mod <i>k T</i>-join With Slack.
Proceedings of the XI Latin and American Algorithms, Graphs and Optimization Symposium, 2021
2020
A variant of the Erdős-Sós conjecture.
J. Graph Theory, 2020
Corrigendum to "Bisimplicial vertices in even-hole-free graphs".
J. Comb. Theory B, 2020
Almost All String Graphs are Intersection Graphs of Plane Convex Sets.
Discret. Comput. Geom., 2020
Notes on Tree- and Path-chromatic Number.
CoRR, 2020
A Lower Bound on the Average Degree Forcing a Minor.
Electron. J. Comb., 2020
2019
Notes on growing a tree in a graph.
Random Struct. Algorithms, 2019
Near-domination in graphs.
J. Comb. Theory A, 2019
Finding Maximal Sets of Laminar 3-Separators in Planar Graphs in Linear Time.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019
2018
Polyhedral results on the stable set problem in graphs containing even or odd pairs.
Math. Program., 2018
2017
Acyclic edge colourings of graphs with large girth.
Random Struct. Algorithms, 2017
Existence of Spanning ℱ-Free Subgraphs with Large Minimum Degree.
Comb. Probab. Comput., 2017
2016
A Short Proof That χ Can be Bounded ε Away from Δ + 1 toward ω.
J. Graph Theory, 2016
'Forcing a sparse minor' - CORRIGENDUM.
Comb. Probab. Comput., 2016
Comb. Probab. Comput., 2016
How to Determine if a Random Graph with a Fixed Degree Sequence Has a Giant Component.
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016
2015
Excluding a Substar and an Antisubstar.
SIAM J. Discret. Math., 2015
A Proof of a Conjecture of Ohba.
J. Graph Theory, 2015
Claw-Free Graphs, Skeletal Graphs, and a Stronger Conjecture on ω, Δ, and χ.
J. Graph Theory, 2015
Connectivity Preserving Iterative Compaction and Finding 2 Disjoint Rooted Paths in Linear Time.
CoRR, 2015
Connectivity Preserving Iterative Compression.
Proceedings of the 27th Canadian Conference on Computational Geometry, 2015
2014
For most graphs <i>H</i>, most <i>H</i>-free graphs have a linear homogeneous set.
Random Struct. Algorithms, 2014
Colouring graphs when the number of colours is almost the maximum degree.
J. Comb. Theory B, 2014
Removable paths and cycles with parity constraints.
J. Comb. Theory B, 2014
2013
Digraph Girth via Chromatic Number.
SIAM J. Discret. Math., 2013
A Linear-Time Algorithm for Finding a Complete Graph Minor in a Dense Graph.
SIAM J. Discret. Math., 2013
Asymptotics of the Chromatic Number for Quasi-Line Graphs.
J. Graph Theory, 2013
Choosability of Graphs with Bounded Order: Ohba's Conjecture and Beyond.
Electron. Notes Discret. Math., 2013
Oriented trees in digraphs.
Discret. Math., 2013
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, 2013
2012
Griggs and Yeh's Conjecture and L(p, 1)-labelings.
SIAM J. Discret. Math., 2012
The disjoint paths problem in quadratic time.
J. Comb. Theory B, 2012
Polynomial treewidth forces a large grid-like-minor.
Eur. J. Comb., 2012
Polynomial-time recognition of clique-width ≤3 graphs.
Discret. Appl. Math., 2012
Connectivity for Bridge-Addable Monotone Graph Classes.
Comb. Probab. Comput., 2012
A short proof that χ can be bounded ε away from Δ+1 towards ω
CoRR, 2012
2011
The edge-density for K<sub>2, t</sub> minors.
J. Comb. Theory B, 2011
Graph Coloring via The Probabilistic Method.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011
The Graph Minor Algorithm with Parity Conditions.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011
2010
Corrigendum to "Asymptotically optimal frugal colouring" [J. Combin. Theory Ser. B 100 (2) (2010) 226-246].
J. Comb. Theory B, 2010
Asymptotically optimal frugal colouring.
J. Comb. Theory B, 2010
Finding a maximum-weight induced k-partite subgraph of an i-triangulated graph.
Discret. Appl. Math., 2010
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010
An (almost) Linear Time Algorithm for Odd Cyles Transversal.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010
Recognizing a Totally Odd K<sub>4</sub>-subdivision, Parity 2-disjoint Rooted Paths and a Parity Cycle Through Specified Elements.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010
A Separator Theorem in Minor-Closed Classes.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010
2009
Theor. Comput. Sci., 2009
A linear-time algorithm to find a separator in a graph excluding a minor.
ACM Trans. Algorithms, 2009
Critical random graphs and the structure of a minimum spanning tree.
Random Struct. Algorithms, 2009
Removable cycles in non-bipartite graphs.
J. Comb. Theory B, 2009
On the odd-minor variant of Hadwiger's conjecture.
J. Comb. Theory B, 2009
Fractionally Edge Colouring Graphs with Large Maximum Degree in Linear Time.
Electron. Notes Discret. Math., 2009
A Characterization of Graphs with Fractional Total Chromatic Number Equal to Delta+2.
Electron. Notes Discret. Math., 2009
A general critical condition for the emergence of a giant component in random graphs with given degrees.
Electron. Notes Discret. Math., 2009
Tree-width of graphs without a 3×3 grid minor.
Discret. Appl. Math., 2009
Highly parity linked graphs.
Comb., 2009
Hadwiger's conjecture is decidable.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009
A nearly linear time algorithm for the half integral parity disjoint paths packing problem.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009
2008
On Planar Quasi-Parity Graphs.
SIAM J. Discret. Math., 2008
The evolution of the mixing rate of a simple random walk on the giant component of a random graph.
Random Struct. Algorithms, 2008
Bounding chi in terms of omega and delta for quasi-line graphs.
J. Graph Theory, 2008
A weaker version of Lovász' path removal conjecture.
J. Comb. Theory B, 2008
Bisimplicial vertices in even-hole-free graphs.
J. Comb. Theory B, 2008
List Colouring Constants of Triangle Free Graphs.
Electron. Notes Discret. Math., 2008
Fractional coloring and the odd Hadwiger's conjecture.
Eur. J. Comb., 2008
Skew partitions in perfect graphs.
Discret. Appl. Math., 2008
Fractionally total colouring G<sub>n, p</sub>.
Discret. Appl. Math., 2008
Planar graph bipartization in linear time.
Discret. Appl. Math., 2008
Partition into cliques for cubic graphs: Planar case, complexity and approximation.
Discret. Appl. Math., 2008
Degree constrained subgraphs.
Discret. Appl. Math., 2008
On the Maximum Degree of a Random Planar Graph.
Comb. Probab. Comput., 2008
A nearly linear time algorithm for the half integral disjoint paths packing.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008
L(2, 1)-labelling of graphs.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008
Optimization and Recognition for K 5-minor Free Graphs in Linear Time.
Proceedings of the LATIN 2008: Theoretical Informatics, 2008
A Simpler Linear Time Algorithm for Embedding Graphs into an Arbitrary Surface and the Genus of Graphs of Bounded Tree-Width.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008
2007
Approximate min-max relations for odd cycles in planar graphs.
Math. Program., 2007
Vašek Chvátal: A Very Short Introduction.
Graphs Comb., 2007
List Colouring Squares of Planar Graphs.
Electron. Notes Discret. Math., 2007
An upper bound for the chromatic number of line graphs.
Eur. J. Comb., 2007
The Erdös-Pósa Property For Long Circuits.
Comb., 2007
Vertex-Colouring Edge-Weightings.
Comb., 2007
Computing crossing number in linear time.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007
Domination in Cubic Graphs of Large Girth.
Proceedings of the Computational Geometry and Graph Theory, 2007
Fast Skew Partition Recognition.
Proceedings of the Computational Geometry and Graph Theory, 2007
Properly 2-Colouring Linear Hypergraphs.
Proceedings of the Approximation, 2007
2006
Concentration for self-bounding functions and an inequality of Talagrand.
Random Struct. Algorithms, 2006
2005
On the fractional chromatic index of a graph and its complement.
Oper. Res. Lett., 2005
(<i>Delta-k</i>)-critical graphs.
J. Comb. Theory B, 2005
Vertex colouring edge partitions.
J. Comb. Theory B, 2005
The perfection and recognition of bull-reducible Berge graphs.
RAIRO Theor. Informatics Appl., 2005
Proceedings of the Algorithms and Data Structures, 9th International Workshop, 2005
2004
On the Co-P<sub>3</sub>-Structure of Perfect Graphs.
SIAM J. Discret. Math., 2004
Finding odd cycle transversals.
Oper. Res. Lett., 2004
Excluding any graph as a minor allows a low tree-width 2-coloring.
J. Comb. Theory B, 2004
Hadwiger's conjecture for line graphs.
Eur. J. Comb., 2004
Discret. Appl. Math., 2004
Stable skew partition problem.
Discret. Appl. Math., 2004
List Colouring When The Chromatic Number Is Close To the Order Of The Graph.
Comb., 2004
2003
Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width.
J. Algorithms, 2003
The height of a random binary search tree.
J. ACM, 2003
Channel assignment on graphs of bounded treewidth.
Discret. Math., 2003
A note on random homomorphism from arbitrary graphs to Z.
Discret. Math., 2003
2002
Asymptotically the List Colouring Constants Are 1.
J. Comb. Theory B, 2002
Random Regular Graphs Of Non-Constant Degree: Independence And Chromatic Number.
Comb. Probab. Comput., 2002
Random Regular Graphs Of Non-Constant Degree: Connectivity And Hamiltonicity.
Comb. Probab. Comput., 2002
Polynomial time recognition of P4-structure.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002
2001
Recognizing Planar Strict Quasi-Parity Graphs.
Graphs Comb., 2001
Channel Assignment on Nearly Bipartite and Bounded Treewidth Graphs.
Electron. Notes Discret. Math., 2001
A note on Random Homomorphism from ArbitraryGraphs to Z.
Electron. Notes Discret. Math., 2001
Bull-Reducible Berge Graphs are Perfect.
Electron. Notes Discret. Math., 2001
The Erdos-Pósa Property for Odd Cycles in Highly Connected Graphs.
Comb., 2001
Colouring graphs when the number of colours is nearly the maximum degree.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001
Approximately covering by cycles in planar graphs.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001
2000
Near-optimal list colorings.
Random Struct. Algorithms, 2000
Channel assignment and weighted coloring.
Networks, 2000
Clique Minors in Graphs and Their Complements.
J. Comb. Theory B, 2000
Finding Skew Partitions Efficiently.
J. Algorithms, 2000
An Improved Algorithm for Finding Tree Decompositions of Small Width.
Int. J. Found. Comput. Sci., 2000
k-Colouring when k is close to Delta.
Electron. Notes Discret. Math., 2000
Optimal packings of edge-disjoint odd cycles.
Discret. Math., 2000
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000
Polynomial Time Recognition of Clique-Width \le \leq 3 Graphs (Extended Abstract).
Proceedings of the LATIN 2000: Theoretical Informatics, 2000
1999
Edge coloring nearly bipartite graphs.
Oper. Res. Lett., 1999
The list colouring constants.
J. Graph Theory, 1999
A note on vertex orders for stability number.
J. Graph Theory, 1999
A Strengthening of Brooks' Theorem.
J. Comb. Theory B, 1999
A Description of Claw-Free Perfect Graphs.
J. Comb. Theory B, 1999
Introducing Directed Tree Width.
Electron. Notes Discret. Math., 1999
Colouring proximity graphs in the plane.
Discret. Math., 1999
Critical Subgraphs of a Random Graph.
Electron. J. Comb., 1999
1998
Total Coloring With Delta + (log Delta) Colors.
SIAM J. Comput., 1998
Fractional Colouring and Hadwiger's Conjecture.
J. Comb. Theory B, 1998
The Size of the Giant Component of a Random Graph with a Given Degree Sequence.
Comb. Probab. Comput., 1998
A Bound on the Total Chromatic Number.
Comb., 1998
Further Algorithmic Aspects of the Local Lemma.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998
Colouring Graphs whose Chromatic Number Is Almost Their Maximum Degree.
Proceedings of the LATIN '98: Theoretical Informatics, 1998
Multicuts in Unweighted Graphs with Bounded Degree and Bounded Tree-Width.
Proceedings of the Integer Programming and Combinatorial Optimization, 1998
1997
A Bound on the Strong Chromatic Index of a Graph<sup>, </sup>.
J. Comb. Theory B, 1997
On Planar Perfectly Contractile Graphs.
Graphs Comb., 1997
Edge coloring regular graphs of high degree.
Discret. Math., 1997
Path parity and perfection.
Discret. Math., 1997
An Algorithm for Finding Homogeneous Pairs.
Discret. Appl. Math., 1997
Colouring a Graph Frugally.
Comb., 1997
On the mixing rate of the triangulation walk.
Proceedings of the Randomization Methods in Algorithm Design, 1997
1996
<i>beta</i>-Perfect Graphs.
J. Comb. Theory B, 1996
Paths, Stars and the Number Three.
Comb. Probab. Comput., 1996
Perfect Matchings in Random r-regular, s-uniform Hypergraphs.
Comb. Probab. Comput., 1996
The Gallai-Younger Conjecture for Planar Graphs.
Comb., 1996
Packing Directed Circuits.
Comb., 1996
1995
When is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem?
SIAM J. Comput., 1995
On the Variance of the Height of Random Binary Search Trees.
SIAM J. Comput., 1995
A Critical Point for Random Graphs with a Given Degree Sequence.
Random Struct. Algorithms, 1995
The Dominating Number of Random Cubic Graph.
Random Struct. Algorithms, 1995
Recognizing bull-free perfect graphs.
Graphs Comb., 1995
Right angle free subsets in the plane.
Graphs Comb., 1995
Rooted Routing in the Plane.
Discret. Appl. Math., 1995
Almost Every Graph can be Covered by [fracDelta2] Linear Forests.
Comb. Probab. Comput., 1995
Multicoloured Hamilton Cycles.
Electron. J. Comb., 1995
Covering the Edges of a Random Graph by Cliques.
Comb., 1995
1994
Induced Circuits in Planar Graphs.
J. Comb. Theory B, 1994
1993
On Total Colorings of Graphs.
J. Comb. Theory B, 1993
Complete Multi-partite Cutsets in Minimal Imperfect Graphs.
J. Comb. Theory B, 1993
Polychromatic Hamilton cycles.
Discret. Math., 1993
Fractionally colouring total graphs.
Comb., 1993
1992
The Strongly Connected Components of 1-in, 1-out.
Comb. Probab. Comput., 1992
Non-Interfering Network Flows.
Proceedings of the Algorithm Theory, 1992
Finding Approximate Separators and Computing Tree Width Quickly
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992
Mick Gets Some (the Odds Are on His Side)
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992
1991
Acyclic Coloring of Graphs.
Random Struct. Algorithms, 1991
Finding disjoint trees in planar graphs in linear time.
Proceedings of the Graph Structure Theory, 1991
Counterexamples to a conjecture of Las Vergnas and Meyniel.
Proceedings of the Graph Structure Theory, 1991
An extremal function for the achromatic number.
Proceedings of the Graph Structure Theory, 1991
1990
Greedy Matching on the Line.
SIAM J. Comput., 1990
Linear Arboricity of Random Regular Graphs.
Random Struct. Algorithms, 1990
Perfection, Parity, Planarity, and Packing Paths.
Proceedings of the 1st Integer Programming and Combinatorial Optimization Conference, 1990
1989
Some classes of perfectly orderable graphs.
J. Graph Theory, 1989
1988
Threshold tolerance graphs.
J. Graph Theory, 1988
Edge-colouring random graphs.
J. Comb. Theory B, 1988
1987
A semi-strong Perfect Graph theorem.
J. Comb. Theory B, 1987
A note on short cycles in diagraphs.
Discret. Math., 1987
1985
A note on the semi-strong perfect graph conjecture.
Discret. Math., 1985
