Bruce A. Reed

According to our database1, Bruce A. Reed authored at least 200 papers between 1985 and 2019.

Collaborative distances:
• Dijkstra number2 of four.
• Erdős number3 of two.

Book
In proceedings
Article
PhD thesis
Other

Bibliography

2019
Near-domination in graphs.
J. Comb. Theory, Ser. A, 2019

Cops and robbers on oriented toroidal grids.
CoRR, 2019

2018
Almost all string graphs are intersection graphs of plane convex sets.
CoRR, 2018

Almost All String Graphs are Intersection Graphs of Plane Convex Sets.
Proceedings of the 34th International Symposium on Computational Geometry, 2018

2017
Acyclic edge colourings of graphs with large girth.
Random Struct. Algorithms, 2017

Existence of Spanning ℱ-Free Subgraphs with Large Minimum Degree.
Combinatorics, Probability & Computing, 2017

Notes on Growing a Tree in a Graph.
CoRR, 2017

2016
A Short Proof That χ Can be Bounded ε Away from Δ + 1 toward ω.
Journal of Graph Theory, 2016

'Forcing a sparse minor' - CORRIGENDUM.
Combinatorics, Probability & Computing, 2016

Forcing a sparse minor.
Combinatorics, Probability & Computing, 2016

How to determine if a random graph with a fixed degree sequence has a giant component.
CoRR, 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. Discrete Math., 2015

A Proof of a Conjecture of Ohba.
Journal of Graph Theory, 2015

Claw-Free Graphs, Skeletal Graphs, and a Stronger Conjecture on ω, Δ, and χ.
Journal of 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 H, most H-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, Ser. B, 2014

Removable paths and cycles with parity constraints.
J. Comb. Theory, Ser. B, 2014

Acyclic edge colourings of graphs with large girth.
CoRR, 2014

2013
Digraph Girth via Chromatic Number.
SIAM J. Discrete Math., 2013

A Linear-Time Algorithm for Finding a Complete Graph Minor in a Dense Graph.
SIAM J. Discrete Math., 2013

Asymptotics of the Chromatic Number for Quasi-Line Graphs.
Journal of Graph Theory, 2013

Choosability of Graphs with Bounded Order: Ohba's Conjecture and Beyond.
Electronic Notes in Discrete Mathematics, 2013

Oriented trees in digraphs.
Discrete Mathematics, 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. Discrete Math., 2012

The disjoint paths problem in quadratic time.
J. Comb. Theory, Ser. B, 2012

Polynomial treewidth forces a large grid-like-minor.
Eur. J. Comb., 2012

Polynomial-time recognition of clique-width ≤3 graphs.
Discrete Applied Mathematics, 2012

Connectivity for Bridge-Addable Monotone Graph Classes.
Combinatorics, Probability & Computing, 2012

Claw-free graphs, skeletal graphs, and a stronger conjecture on $ω$, $Δ$, and $χ$
CoRR, 2012

A Proof of a Conjecture of Ohba
CoRR, 2012

A short proof that χ can be bounded ε away from Δ+1 towards ω
CoRR, 2012

A linear-time algorithm for finding a complete graph minor in a dense graph
CoRR, 2012

2011
The edge-density for K2, t minors.
J. Comb. Theory, Ser. B, 2011

Asymptotics of the chromatic number for quasi-line graphs
CoRR, 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, Ser. B, 2010

Asymptotically optimal frugal colouring.
J. Comb. Theory, Ser. B, 2010

Finding a maximum-weight induced k-partite subgraph of an i-triangulated graph.
Discrete Applied Mathematics, 2010

Odd cycle packing.
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 K4-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
Coloring Artemis graphs.
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, Ser. B, 2009

On the odd-minor variant of Hadwiger's conjecture.
J. Comb. Theory, Ser. B, 2009

Fractionally Edge Colouring Graphs with Large Maximum Degree in Linear Time.
Electronic Notes in Discrete Mathematics, 2009

A Characterization of Graphs with Fractional Total Chromatic Number Equal to Delta+2.
Electronic Notes in Discrete Mathematics, 2009

A general critical condition for the emergence of a giant component in random graphs with given degrees.
Electronic Notes in Discrete Mathematics, 2009

Tree-width of graphs without a 3×3 grid minor.
Discrete Applied Mathematics, 2009

Combinatorica, 2009

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Asymptotically optimal frugal colouring.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 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. Discrete 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.
Journal of Graph Theory, 2008

A weaker version of Lovász' path removal conjecture.
J. Comb. Theory, Ser. B, 2008

Bisimplicial vertices in even-hole-free graphs.
J. Comb. Theory, Ser. B, 2008

List Colouring Constants of Triangle Free Graphs.
Electronic Notes in Discrete Mathematics, 2008

Fractional coloring and the odd Hadwiger's conjecture.
Eur. J. Comb., 2008

Skew partitions in perfect graphs.
Discrete Applied Mathematics, 2008

Fractionally total colouring Gn, p.
Discrete Applied Mathematics, 2008

Planar graph bipartization in linear time.
Discrete Applied Mathematics, 2008

Partition into cliques for cubic graphs: Planar case, complexity and approximation.
Discrete Applied Mathematics, 2008

Degree constrained subgraphs.
Discrete Applied Mathematics, 2008

On the Maximum Degree of a Random Planar Graph.
Combinatorics, Probability & Computing, 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 and Combinatorics, 2007

Asymptotics of the chromatic number for quasi-line graphs.
Electronic Notes in Discrete Mathematics, 2007

List Colouring Squares of Planar Graphs.
Electronic Notes in Discrete Mathematics, 2007

An upper bound for the chromatic number of line graphs.
Eur. J. Comb., 2007

The Erdös-Pósa Property For Long Circuits.
Combinatorica, 2007

Vertex-Colouring Edge-Weightings.
Combinatorica, 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

(Delta-k)-critical graphs.
J. Comb. Theory, Ser. B, 2005

Vertex colouring edge partitions.
J. Comb. Theory, Ser. B, 2005

The perfection and recognition of bull-reducible Berge graphs.
ITA, 2005

Fractionally total colouring Gn, p.
Electronic Notes in Discrete Mathematics, 2005

Planar graph bipartization in linear time.
Electronic Notes in Discrete Mathematics, 2005

Degree constrained subgraphs.
Electronic Notes in Discrete Mathematics, 2005

Coloring Artemis graphs
CoRR, 2005

Heap Building Bounds.
Proceedings of the Algorithms and Data Structures, 9th International Workshop, 2005

Approximate Min-max Relations for Odd Cycles in Planar Graphs.
Proceedings of the Integer Programming and Combinatorial Optimization, 2005

2004
On the Co-P3-Structure of Perfect Graphs.
SIAM J. Discrete Math., 2004

Finding odd cycle transversals.
Oper. Res. Lett., 2004

Star coloring of graphs.
Journal of Graph Theory, 2004

Excluding any graph as a minor allows a low tree-width 2-coloring.
J. Comb. Theory, Ser. B, 2004

Eur. J. Comb., 2004

Preface.
Discrete Applied Mathematics, 2004

Stable skew partition problem.
Discrete Applied Mathematics, 2004

List Colouring When The Chromatic Number Is Close To the Order Of The Graph.
Combinatorica, 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.
Discrete Mathematics, 2003

A note on random homomorphism from arbitrary graphs to Z.
Discrete Mathematics, 2003

2002
Asymptotically the List Colouring Constants Are 1.
J. Comb. Theory, Ser. B, 2002

Random Regular Graphs Of Non-Constant Degree: Independence And Chromatic Number.
Combinatorics, Probability & Computing, 2002

Random Regular Graphs Of Non-Constant Degree: Connectivity And Hamiltonicity.
Combinatorics, Probability & Computing, 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 and Combinatorics, 2001

Channel Assignment on Nearly Bipartite and Bounded Treewidth Graphs.
Electronic Notes in Discrete Mathematics, 2001

A note on Random Homomorphism from ArbitraryGraphs to Z.
Electronic Notes in Discrete Mathematics, 2001

Bull-Reducible Berge Graphs are Perfect.
Electronic Notes in Discrete Mathematics, 2001

The Erdos-Pósa Property for Odd Cycles in Highly Connected Graphs.
Combinatorica, 2001

On Star Coloring of Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 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, Ser. 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.
Electronic Notes in Discrete Mathematics, 2000

Optimal packings of edge-disjoint odd cycles.
Discrete Mathematics, 2000

How tall is a tree?
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Finding Skew Partitions Efficiently.
Proceedings of the LATIN 2000: Theoretical Informatics, 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.
Journal of Graph Theory, 1999

A note on vertex orders for stability number.
Journal of Graph Theory, 1999

A Strengthening of Brooks' Theorem.
J. Comb. Theory, Ser. B, 1999

A Description of Claw-Free Perfect Graphs.
J. Comb. Theory, Ser. B, 1999

Introducing Directed Tree Width.
Electronic Notes in Discrete Mathematics, 1999

Colouring proximity graphs in the plane.
Discrete Mathematics, 1999

Critical Subgraphs of a Random Graph.
Electr. J. Comb., 1999

Mangoes and Blueberries.
Combinatorica, 1999

An Improved Algorithm for Finding Tree Decompositions of Small Width.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 1999

1998
Total Coloring With Delta + (log Delta) Colors.
SIAM J. Comput., 1998

ω, Δ, and χ.
Journal of Graph Theory, 1998

J. Comb. Theory, Ser. B, 1998

The Size of the Giant Component of a Random Graph with a Given Degree Sequence.
Combinatorics, Probability & Computing, 1998

A Bound on the Total Chromatic Number.
Combinatorica, 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, .
J. Comb. Theory, Ser. B, 1997

On Planar Perfectly Contractile Graphs.
Graphs and Combinatorics, 1997

Edge coloring regular graphs of high degree.
Discrete Mathematics, 1997

Path parity and perfection.
Discrete Mathematics, 1997

An Algorithm for Finding Homogeneous Pairs.
Discrete Applied Mathematics, 1997

Colouring a Graph Frugally.
Combinatorica, 1997

On the mixing rate of the triangulation walk.
Proceedings of the Randomization Methods in Algorithm Design, 1997

1996
beta-Perfect Graphs.
J. Comb. Theory, Ser. B, 1996

Paths, Stars and the Number Three.
Combinatorics, Probability & Computing, 1996

Perfect Matchings in Random r-regular, s-uniform Hypergraphs.
Combinatorics, Probability & Computing, 1996

The Gallai-Younger Conjecture for Planar Graphs.
Combinatorica, 1996

Packing Directed Circuits.
Combinatorica, 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 and Combinatorics, 1995

Right angle free subsets in the plane.
Graphs and Combinatorics, 1995

Rooted Routing in the Plane.
Discrete Applied Mathematics, 1995

Almost Every Graph can be Covered by [fracDelta2] Linear Forests.
Combinatorics, Probability & Computing, 1995

Multicoloured Hamilton Cycles.
Electr. J. Comb., 1995

Covering the Edges of a Random Graph by Cliques.
Combinatorica, 1995

1994
Induced Circuits in Planar Graphs.
J. Comb. Theory, Ser. B, 1994

1993
On Total Colorings of Graphs.
J. Comb. Theory, Ser. B, 1993

Complete Multi-partite Cutsets in Minimal Imperfect Graphs.
J. Comb. Theory, Ser. B, 1993

Polychromatic Hamilton cycles.
Discrete Mathematics, 1993

Fractionally colouring total graphs.
Combinatorica, 1993

1992
The Strongly Connected Components of 1-in, 1-out.
Combinatorics, Probability & Computing, 1992

Star arboricity.
Combinatorica, 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

When is the Assignment Bound Tight for the Asymmetric Traveling Salesman Problem?
Proceedings of the 2nd Integer Programming and Combinatorial Optimization Conference, 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.
Journal of Graph Theory, 1989

Building Heaps Fast.
J. Algorithms, 1989

P4-comparability graphs.
Discrete Mathematics, 1989

1988
Threshold tolerance graphs.
Journal of Graph Theory, 1988

Edge-colouring random graphs.
J. Comb. Theory, Ser. B, 1988

1987
A semi-strong Perfect Graph theorem.
J. Comb. Theory, Ser. B, 1987

A note on even pairs.
Discrete Mathematics, 1987

A note on short cycles in diagraphs.
Discrete Mathematics, 1987

1985
A note on the semi-strong perfect graph conjecture.
Discrete Mathematics, 1985