Bruce A. Reed

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

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

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

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, Ser. B, 2020

Almost All String Graphs are Intersection Graphs of Plane Convex Sets.
Discret. Comput. Geom., 2020

Tight Bounds on The Clique Chromatic Number.
CoRR, 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, Ser. A, 2019

Cops and robbers on oriented toroidal grids.
CoRR, 2019

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

Forcing a sparse minor.
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, Ser. B, 2014

Removable paths and cycles with parity constraints.
J. Comb. Theory, Ser. 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

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, Ser. 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, Ser. 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, 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.
Discret. Appl. Math., 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 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
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.
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, Ser. B, 2008

Bisimplicial vertices in even-hole-free graphs.
J. Comb. Theory, Ser. 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

Partition into cliques for cubic graphs: Planar case, complexity and approximation.
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

Asymptotics of the chromatic number for quasi-line graphs.
Electron. Notes Discret. Math., 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, Ser. B, 2005

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

The perfection and recognition of bull-reducible Berge graphs.
RAIRO Theor. Informatics Appl., 2005

Fractionally total colouring G<sub>n, p</sub>.
Electron. Notes Discret. Math., 2005

Planar graph bipartization in linear time.
Electron. Notes Discret. Math., 2005

Degree constrained subgraphs.
Electron. Notes Discret. Math., 2005

Heap Building Bounds.
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

Star coloring of graphs.
J. Graph Theory, 2004

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

Hadwiger's conjecture for line graphs.
Eur. J. Comb., 2004

Preface.
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, Ser. 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, 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.
Electron. Notes Discret. Math., 2000

Optimal packings of edge-disjoint odd cycles.
Discret. Math., 2000

How tall is a tree?
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, Ser. B, 1999

A Description of Claw-Free Perfect Graphs.
J. Comb. Theory, Ser. 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

Mangoes and Blueberries.
Comb., 1999

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

ω, Δ, and χ.
J. Graph Theory, 1998

Fractional Colouring and Hadwiger's Conjecture.
J. Comb. Theory, Ser. 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, Ser. 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, Ser. 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, 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.
Discret. Math., 1993

Fractionally colouring total graphs.
Comb., 1993

1992
The Strongly Connected Components of 1-in, 1-out.
Comb. Probab. Comput., 1992

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

Building Heaps Fast.
J. Algorithms, 1989

P4-comparability graphs.
Discret. Math., 1989

1988
Threshold tolerance graphs.
J. 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.
Discret. Math., 1987

A note on short cycles in diagraphs.
Discret. Math., 1987

1985
A note on the semi-strong perfect graph conjecture.
Discret. Math., 1985


  Loading...