Bruce Reed

Q: What Schools Are Affiliated With Bruce Reed

Bruce Reed is affiliated with the following schools: University of Waterloo, McGill University, Princeton University, Carnegie Mellon University

Bruce Reed 's AcademicInfluence.com Rankings

Bruce Reed

Mathematics

#4048

World Rank

#5832

Historical Rank

Measure Theory

#1328

World Rank

#1673

Historical Rank

mathematics Degrees

Download Badge

Mathematics

Bruce Reed 's Degrees

PhD Mathematics Princeton University

Why Is Bruce Reed Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Bruce Alan Reed FRSC is a Canadian mathematician and computer scientist, a former Canada Research Chair in Graph Theory at McGill University. His research is primarily in graph theory. He is a distinguished research fellow of the Institute of Mathematics in the Academia Sinica, Taiwan, and an adjunct professor at the University of Victoria in Canada.

(See a Problem?)

Bruce Reed 's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

A Critical Point for Random Graphs with a Given Degree Sequence (1995) (2219)
The Size of the Giant Component of a Random Graph with a Given Degree Sequence (1998) (778)
Graph Colouring and the Probabilistic Method (2001) (475)
Finding odd cycle transversals (2004) (379)
Mick gets some (the odds are on his side) (satisfiability) (1992) (373)
Algorithmic Aspects of Tree Width (2003) (306)
Acyclic Coloring of Graphs (1991) (235)
Finding approximate separators and computing tree width quickly (1992) (215)
Further algorithmic aspects of the local lemma (1998) (198)
The disjoint paths problem in quadratic time (2012) (185)
Paths, Stars and the Number Three (1996) (178)
Surveys in Combinatorics, 1997: Tree Width and Tangles: A New Connectivity Measure and Some Applications (1997) (174)
A Bound on the Strong Chromatic Index of a Graph, (1997) (168)
Packing directed circuits (1996) (167)
Minima in branching random walks (2007) (146)
Star coloring of graphs (2004) (127)
Degree constrained subgraphs (2005) (123)
Channel assignment and weighted coloring (2000) (123)
Vertex colouring edge partitions (2005) (121)
Computing crossing number in linear time (2007) (108)
Excluding any graph as a minor allows a low tree-width 2-coloring (2004) (105)
The height of a random binary search tree (2003) (104)
Vertex-Colouring Edge-Weightings (2007) (102)
P4-comparability graphs (1989) (100)
A Bound on the Total Chromatic Number (1998) (99)
Recent advances in algorithms and combinatorics (2003) (95)
Multicoloured Hamilton Cycles (1995) (89)
A Strengthening of Brooks' Theorem (1999) (80)
A Simpler Linear Time Algorithm for Embedding Graphs into an Arbitrary Surface and the Genus of Graphs of Bounded Tree-Width (2008) (78)
An Improved Algorithm for Finding Tree Decompositions of Small Width (1999) (76)
A Separator Theorem in Minor-Closed Classes (2010) (75)
Polynomial Time Recognition of Clique-Width ≤ 3 Graphs (2000) (72)
On the odd-minor variant of Hadwiger's conjecture (2009) (69)
List Colouring Squares of Planar Graphs (2007) (68)
A semi-strong Perfect Graph theorem (1987) (68)
Perfect Matchings in Random r-regular, s-uniform Hypergraphs (1996) (67)
Building Heaps Fast (1989) (65)
Introducing Directed Tree Width (1999) (65)
Colouring a graph frugally (1997) (64)
The Erdős–Pósa Property For Long Circuits (2007) (63)
Polynomial Time Recognition of Clique-Width \le \leq 3 Graphs (Extended Abstract) (2000) (63)
ω, Δ, and χ (1998) (63)
Bisimplicial vertices in even-hole-free graphs (2008) (62)
Polychromatic Hamilton cycles (1993) (60)
Mangoes and Blueberries (1999) (59)
Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width (2003) (59)
Finding disjoint trees in planar graphs in linear time (1991) (55)
Ballot Theorems, Old and New (2008) (54)
Finding Skew Partitions Efficiently (2000) (54)
The evolution of the mixing rate of a simple random walk on the giant component of a random graph (2008) (52)
Random Regular Graphs of Non-Constant Degree: Connectivity and Hamiltonicity (2002) (51)
A Description of Claw-Free Perfect Graphs (1999) (50)
Some classes of perfectly orderable graphs (1989) (49)
The list colouring constants (1999) (49)
A note on short cycles in diagraphs (1987) (49)
On the Variance of the Height of Random Binary Search Trees (1995) (48)
The Erdős–Pósa Property for Odd Cycles in Highly Connected Graphs (2001) (47)
Polynomial-time recognition of clique-width ≤3 graphs (2012) (46)
A Proof of a Conjecture of Ohba (2012) (46)
Fractional Colouring and Hadwiger's Conjecture (1998) (45)
Partition into cliques for cubic graphs: Planar case, complexity and approximation (2008) (44)
An upper bound for the chromatic number of line graphs (2007) (43)
An (almost) linear time algorithm for odd cycles transversal (2010) (41)
Recognizing bull-free perfect graphs (1995) (41)
Colouring graphs when the number of colours is almost the maximum degree (2014) (41)
List Colouring When The Chromatic Number Is Close To the Order Of The Graph (2004) (40)
Edge coloring regular graphs of high degree (1997) (40)
L(2,1)-labelling of graphs (2008) (38)
Star arboricity (1992) (37)
Hadwiger's conjecture for line graphs (2004) (37)
A Simple Algorithm for the Graph Minor Decomposition - Logic meets Structural Graph Theory (2013) (37)
Griggs and Yeh's Conjecture and L(p, 1)-labelings (2012) (37)
On Total Colorings of Graphs (1993) (36)
Asymptotically the List Colouring Constants Are 1 (2002) (36)
A linear-time algorithm to find a separator in a graph excluding a minor (2009) (36)
On the Maximum Degree of a Random Planar Graph (2008) (36)
On Star Coloring of Graphs (2001) (35)
Faster Mixing and Small Bottlenecks (2006) (35)
Bounding ? in terms of ? and ? for quasi-line graphs (2008) (34)
Oriented trees in digraphs (2013) (34)
On the mixing rate of the triangulation walk (1997) (34)
The edge-density for K2, t minors (2011) (34)
Planar graph bipartization in linear time (2005) (34)
Fractionally colouring total graphs (1993) (33)
Polynomial treewidth forces a large grid-like-minor (2008) (32)
Threshold tolerance graphs (1988) (31)
beta-Perfect Graphs (1996) (31)
Colouring graphs when the number of colours is nearly the maximum degree (2001) (30)
Brambles, Prisms and Grids (2006) (29)
Odd cycle packing (2010) (28)
Channel assignment on graphs of bounded treewidth (2003) (28)
Concentration for self‐bounding functions and an inequality of Talagrand (2006) (28)
Colouring proximity graphs in the plane (1999) (28)
Highly parity linked graphs (2009) (28)
Rooted Routing in the Plane (1993) (28)
The Graph Minor Algorithm with Parity Conditions (2011) (27)
Critical random graphs and the structure of a minimum spanning tree (2009) (27)
Near-optimal list colorings (2000) (27)
A weaker version of Lovász' path removal conjecture (2008) (27)
Approximate Min-max Relations for Odd Cycles in Planar Graphs (2005) (27)
Random Regular Graphs of Non-Constant Degree: Independence and Chromatic Number (2002) (26)
An extremal function for the achromatic number (1991) (26)
Forcing a sparse minor (2014) (24)
Covering the edges of a random graph by cliques (1995) (24)
The Dominating Number of Random Cubic Graph (1995) (23)
Path parity and perfection (1997) (23)
Hadwiger's conjecture is decidable (2009) (23)
Bounding χ in terms of ω and Δ for quasi‐line graphs (2008) (22)
Finding a maximum-weight induced k-partite subgraph of an i-triangulated graph (2010) (22)
The gallai-younger conjecture for planar graphs (1996) (22)
Fast Skew Partition Recognition (2008) (21)
Recognizing a totally odd K4-subdivision, parity 2-disjoint rooted paths and a parity cycle through specified elements (2010) (21)
How to determine if a random graph with a fixed degree sequence has a giant component (2016) (21)
Asymptotically optimal frugal colouring (2009) (21)
A nearly linear time algorithm for the half integral disjoint paths packing (2008) (20)
When is the Assignment Bound Tight for the Asymmetric Traveling Salesman Problem? (1995) (19)
The Diameter of the Minimum Spanning Tree of a Complete Graph (2006) (19)
Connectivity for Bridge-Addable Monotone Graph Classes (2011) (18)
Near optimal list colorings (2000) (17)
Fast separation in a graph with an excluded minor (2004) (17)
The Evolution of the Mixing Rate (2007) (17)
Optimization and Recognition for K 5-minor Free Graphs in Linear Time (2008) (17)
Linear Arboricity of Random Regular Graphs (1990) (16)
List Colouring of Graphs with at Most (2 — o(l)) x Vertices (2002) (15)
Induced Circuits in Planar Graphs (1994) (15)
An Algorithm for Finding Homogeneous Pairs (1997) (14)
On Planar Perfectly Contractile Graphs (1997) (14)
A note on even pairs (1987) (14)
A note on random homomorphism from arbitrary graphs to Z (2003) (14)
A variant of the Erdős‐Sós conjecture (2016) (13)
Complete Multi-partite Cutsets in Minimal Imperfect Graphs (1993) (13)
Ballot theorems for random walks with finite variance (2008) (13)
Colouring Graphs whose Chromatic Number Is Almost Their Maximum Degree (1998) (13)
A note on vertex orders for stability number (1999) (12)
Digraph Girth via Chromatic Number (2013) (12)
Colourings with Bounded Monochromatic Components in Graphs of Given Circumference (2016) (12)
A nearly linear time algorithm for the half integral parity disjoint paths packing problem (2009) (12)
Almost All F-Free Graphs Have The Erdos-Hajnal Property (2010) (12)
Skew partitions in perfect graphs (2008) (11)
(Delta-k)-critical graphs (2005) (11)
Optimal packings of edge-disjoint odd cycles (2000) (11)
List colouring squares of planar graphs (extended abstract) (2007) (11)
Multicuts in Unweighted Graphs with Bounded Degree and Bounded Tree-Width (1998) (11)
Approximate min–max relations for odd cycles in planar graphs (2007) (11)
Edge-colouring random graphs (1988) (10)
Choosability of Graphs with Bounded Order: Ohba's Conjecture and Beyond (2013) (10)
Concentration for self-bounding functions and an inequality of Talagrand (2006) (10)
Critical Subgraphs of a Random Graph (1999) (10)
A Short Proof That χ Can be Bounded ε Away from Δ + 1 toward ω (2016) (10)
Total Coloring With $\Delta + \mbox\lowercasepoly(\log \Delta)$ Colors (1999) (10)
Perfection, Parity, Planarity, and Packing Paths (1990) (9)
Asymptotics of the Chromatic Number for Quasi‐Line Graphs (2007) (9)
Greedy Matching on the Line (1990) (8)
A Linear-Time Algorithm for Finding a Complete Graph Minor in a Dense Graph (2012) (8)
How tall is a tree? (2000) (8)
Spanning Trees in Graphs of High Minimum Degree with a Universal Vertex I: An Approximate Asymptotic Result (2019) (8)
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms: Preface (2006) (8)
For most graphs H, most H‐free graphs have a linear homogeneous set (2014) (8)
Non-Interfering Network Flows (1992) (8)
Tree-width of graphs without a 3×3 grid minor (2009) (8)
Existence of Spanning ℱ-Free Subgraphs with Large Minimum Degree (2016) (7)
A Lower Bound on the Average Degree Forcing a Minor (2019) (7)
Claw‐Free Graphs, Skeletal Graphs, and a Stronger Conjecture on ω, Δ, and χ (2012) (7)
Stable skew partition problem (2004) (7)
List Colouring Constants of Triangle Free Graphs (2008) (7)
Heap Building Bounds (2005) (7)
Properly 2-Colouring Linear Hypergraphs (2007) (7)
Acyclic edge colourings of graphs with large girth (2014) (7)
Edge coloring nearly bipartite graphs (1999) (6)
Probabilistic Analysis of Algorithms (1998) (6)
Fractional coloring and the odd Hadwiger's conjecture (2008) (6)
Giant Components for Two Expanding Graph Processes (2002) (6)
Spanning Trees in Graphs of High Minimum Degree which have a Universal Vertex II: A Tight Result (2019) (6)
Edge coloring, polyhedra and probability (1998) (6)
Domination in Cubic Graphs of Large Girth (2008) (6)
Recognizing Planar Strict Quasi-Parity Graphs (2001) (5)
On a random walk that grows its own tree (2021) (5)
‘Forcing a sparse minor’ — CORRIGENDUM (2015) (5)
Coloring Artemis graphs (2005) (5)
An Optimal Algorithm for Finding Clique-Cross Partitions (1998) (5)
A Characterization of Graphs with Fractional Total Chromatic Number Equal to Delta+2 (2009) (5)
Triangle-Free Graphs (2002) (4)
Finding Maximal Sets of Laminar 3-Separators in Planar Graphs in Linear Time (2018) (4)
A Variant of the Erd\H{o}s-S\'os Conjecture (2016) (4)
Almost All String Graphs are Intersection Graphs of Plane Convex Sets (2018) (4)
On the Co-P3-Structure of Perfect Graphs (2005) (4)
A Characterization of Graphs with Fractional Total Chromatic Number Equal to ∆ + 2 (2011) (4)
Spanning trees in graphs of high minimum degree with a universal vertex II: A tight result (2019) (3)
A logarithmic bound for the chromatic number of the associahedron (2018) (3)
N ov 2 01 2 A short proof that χ can be bounded ǫ away from ∆ + 1 towards ω (2012) (3)
Right angle free subsets in the plane (1995) (3)
Existence of spanning $\mathcal{F}$-free subgraphs with large minimum degree (2014) (3)
Non-interfering dipaths in planar digraphs (1991) (3)
Polynomial time recognition of P4-structure (2002) (3)
Corrigendum to "Asymptotically optimal frugal colouring" [J. Combin. Theory Ser. B 100 (2) (2010) 226-246] (2010) (3)
Clique Minors in Graphs and Their Complements (2000) (3)
The perfection and recognition of bull-reducible Berge graphs (2005) (3)
On the fractional chromatic index of a graph and its complement (2005) (3)
Removable cycles in non-bipartite graphs (2009) (3)
A general critical condition for the emergence of a giant component in random graphs with given degrees (2009) (3)
Almost Every Graph can be Covered by Linear Forests (1995) (2)
Cops and robbers on oriented toroidal grids (2019) (2)
Tight Bounds on The Clique Chromatic Number (2020) (2)
Building your path to escape from home (2017) (2)
Notes on growing a tree in a graph (2017) (2)
Excluding a Substar and an Antisubstar (2015) (2)
Connectivity Preserving Iterative Compaction and Finding 2 Disjoint Rooted Paths in Linear Time (2015) (2)
Corrigendum to "Bisimplicial vertices in even-hole-free graphs" (2020) (2)
Edge-disjoint odd cycles in graphs with small chromatic number (1999) (2)
The Strongly Connected Components of 1-in, 1-out (1992) (2)
Polyhedral results on the stable set problem in graphs containing even or odd pairs (2018) (2)
Connectivity of Addable Monotone Graph Classes (2007) (2)
Vašek Chvátal: A Very Short Introduction (2007) (2)
Near-domination in graphs (2017) (1)
Fractionally total colouring Gn, p (2005) (1)
The First Moment Method (2002) (1)
A general ballot theorem (2008) (1)
A note on the semi-strong perfect graph conjecture (1985) (1)
Algorithmic Aspects of the Local Lemma (2002) (1)
Claw-free graphs, skeletal graphs, and a stronger conjecture on $\omega$, $\Delta$, and $\chi$ (2012) (1)
Graph coloring via the probabilistic method (2011) (1)
On Planar Quasi-Parity Graphs (2008) (1)
The Strong Chromatic Number (2002) (1)
Graphs with Girth at Least Five (2002) (1)
Fractionally Edge Colouring Graphs with Large Maximum Degree in Linear Time (2009) (1)
The Speed and Threshold of the Biased Perfect Matching Game (2020) (1)
Almost All String Graphs are Intersection Graphs of Plane Convex Sets (2020) (1)
Connectivity Preserving Iterative Compression (2015) (0)
Removable paths and cycles with parity constraints (2014) (0)
The Speed and Threshold of the Biased Hamilton Cycle Game (2020) (0)
Tree-widthofgraphswithouta3 3gridminor (2009) (0)
Total Coloring With Delta + (log Delta) Colors (1998) (0)
Tree decompositions and linear time algorithms (2012) (0)
Other Grants and Activities - Action Soleil Levant (2002) (0)
The Lovász Local Lemma (2002) (0)
Separators, Brambles, Tree Decompositions and Excluding Clique Minors (2012) (0)
The speed and threshold of the biased perfect matching and Hamilton cycle games (2023) (0)
Hard-Core Distributions on Matchings (2002) (0)
New Results - Graph colourings and applications (2006) (0)
Total coloring with Delta plus poly(log Delta) colors (1998) (0)
Polyhedral results on the stable set problem in graphs containing even or odd pairs (2017) (0)
The Structural Decomposition (2002) (0)
2 Proof of Theorem 1 : Main ideas (2008) (0)
Channel Assignment on Nearly Bipartite and Bounded Treewidth Graphs (2001) (0)
Partitioning Into Prescribed Number of Cycles and Mod k T-join With Slack (2021) (0)
k-Colouring when k is close to Delta (2000) (0)
Graph Minors I : Rooted Routing (2013) (0)
Talagrand’s Inequality and Colouring Sparse Graphs (2002) (0)
Spanning trees in graphs of high minimum degree with a universal vertex I: An asymptotic result (2019) (0)
Near-optimal List Colourings 1 a Colouring Problem and a Colouring Pro- Cedure (2000) (0)
Multicuts in Unweighted Graphs withBounded Degree and Bounded Tree-WidthGruia C alinescu (1998) (0)
Near Optimal Total Colouring II: General Graphs (2002) (0)
Almost All H-Free Graphs Have the Erdý Property (2010) (0)
Finding Fractional Colourings and Large Stable Sets (2002) (0)
Total Colouring Revisited (2002) (0)
Hadwiger’s Conjecture (2002) (0)
Notes on Tree- and Path-chromatic Number (2020) (0)
Finding Skew Partitions Efficiently 1 (2000) (0)
Bull-Reducible Berge Graphs are Perfect (2001) (0)
Probabilistic Combinatorics: Recent Progress and New Frontiers (2005) (0)
List colouring of graphs with at most $\big(2-o(1)\big)\chi$ vertices (2003) (0)
Near Optimal Total Colouring I: Sparse Graphs (2002) (0)
Preface (2004) (0)
The Chernoff Bound (2002) (0)
The List Colouring Conjecture (2002) (0)
Probabilistic and Extremal Combinatorics Organizers (2009) (0)
A note on Random Homomorphism from ArbitraryGraphs to Z (2001) (0)
C O ] 4 F eb 2 01 4 A Proof of a Conjecture of Ohba (2014) (0)
Azuma’s Inequality and a Strengthening of Brooks’ Theorem (2002) (0)
The Method of Conditional Expectations (2002) (0)
Counterexamples to a conjecture of Las Vergnas and Meyniel (1991) (0)
Recognizing a totally odd K 4-subdivision , parity 2-disjoint rooted paths and a parity cycle through specified elements ( extended abstract ) ∗ (2009) (0)
Excluding a near-clique and a near-anticlique (2012) (0)
A short proof that $\chi$ can be bounded $\epsilon$ away from $\Delta+1$ towards $\omega$ (2012) (0)
A Closer Look at Talagrand’s Inequality (2002) (0)
Distance Problems with Dependent Uncertainties (1998) (0)
The Asymptotics of Edge Colouring Multigraphs (2002) (0)
A First Glimpse of Total Colouring (2002) (0)
Approximately covering by cycles in planar graphs (2001) (0)
A Density Version of the Corradi-Hajnal Theorem (2014) (0)
ON GROWING A TREE IN A GRAPH À (2017) (0)
Generalizations of the Local Lemma (2002) (0)

This paper list is powered by the following services:

Other Resources About Bruce Reed

en.wikipedia.org

What Schools Are Affiliated With Bruce Reed ?

Bruce Reed is affiliated with the following schools:

Bruce Reed 's Academic­Influence.com Rankings