The Diameter of the Minimum Spanning Tree of a Complete Graph (2008)
Louigi Addario-berry, Nicolas Broutin, Bruce Reed
} be independent identically distributed weights for the edges of Kn. If Xi � = Xj for i � = j, then
List Colouring Squares of Planar Graphs (2008)
Havet, Frédéric, Heuvel, Jan Van Den, McDiarmid, Colin, Reed, Bruce
In 1977, Wegner conjectured that the chromatic number of the square of every planar graph $G$ with maximum degree $\Delta\ge8$ is at most $\lfloor\frac32 \Delta\bigr+1$. We show that it is at most...
In cellular telephone networks, sets of radio channels (colors) must be assigned to transmitters (vertices) while avoiding interference. Often, the transmitters are laid out like vertices of a...
In cellular telephone networks, sets of radio channels (colors) must be assigned to transmitters (vertices) while avoiding interference. Often, the transmitters are laid out like vertices of a...
Approximate Min-Max Relations for Odd (2008)
Samuel Fiorini, Nadia Hardy, Bruce Reed, Adrian Vetta
Abstract We study the ratio between the minimum size of an odd cycle vertex transversal and the maximum size of a collection of vertex-disjoint odd cycles in a planar graph. We show that this ratio...
Fast separation in a graph with an excluded minor † (2008)
Let G be an n-vertex m-edge graph with weighted vertices. A pair of vertex sets A, B ⊆ V (G) is a 2
Domination in Cubic Graphs of Large Girth (2008)
Abstract We prove that connected � cubic graphs of order n and girth g have domination number at most 0.32127n + O. � n g Keywords domination number; minimum degree; girth; cubic graph The...
1 Introduction Probabilistic Analysis of Algorithms (2008)
Rather than analyzing the worst case performance of algorithms, one can investigate their performance
An Optimal Algorithm for Finding Clique-Cross Partitions (2008)
Hazel Everett, Sulamita Klein, Bruce Reed
We consider the problem of determining whether or not the vertices of a graph can be partitioned into four disjoint cliques A; B; C; D such that vertices of A are not adjacent to vertices of C and...
List colouring squares of planar graphs (2008)
Havet, Frederic, Van Den Heuvel, Jan, Mcdiarmid, Colin, Reed, Bruce
In 1977, Wegner conjectured that the chromatic number of the square of every planar graph~$G$ with maximum degree $\Delta\ge8$ is at most $\bigl\lfloor\frac32\,\Delta\bigr\rfloor+1$. We show that it...
List colouring squares of planar graphs (2008)
Havet, Frederic, Van Den Heuvel, Jan, Mcdiarmid, Colin, Reed, Bruce
In 1977, Wegner conjectured that the chromatic number of the square of every planar graph~$G$ with maximum degree $\Delta\ge8$ is at most $\bigl\lfloor\frac32\,\Delta\bigr\rfloor+1$. We show that it...
L(p,1)-labelling of graphs (2008)
Havet, Frederic, Reed, Bruce, Sereni, Jean-Sébastien
An $L(p,1)$-labelling of a graph is a function $f$ from the vertex set to the positive integers such that $|f(x)-f(y)|\geq p$ if $\dist(x,y)=1$ and $|f(x)-f(y)|\geq p$ if $\dist(x,y)=2$, where...
L(p,1)-labelling of graphs (2008)
Havet, Frederic, Reed, Bruce, Sereni, Jean-Sébastien
An $L(p,1)$-labelling of a graph is a function $f$ from the vertex set to the positive integers such that $|f(x)-f(y)|\geq p$ if $\dist(x,y)=1$ and $|f(x)-f(y)|\geq p$ if $\dist(x,y)=2$, where...
On the Mixing Rate of the Triangulation Walk (Abstract) (2007)
Let Tn denote the set of triangulations of a convex polygon K with n sides. We study the random walk on Tn whose transitions are "flips " of one of the n \Gamma 3 internal diagonals...
Rooted Routing in the Plane (2007)
We describe an algorithm due to Reed. Robertson, Schrijver and Seymour, that finds vertex disjoint paths in a planar graph given the endpoints. When the number of required paths is fixed the...
Asymptotically the list colouring constants are 1 (2007)
In this paper we prove the following result about vertex list colourings, which shows that a conjecture from [9] is asymptotically correct. Let G be a graph with the sets of lists S(v), satisfying...
Guillaume Fertin, Bruce Reed, Irin Upres-ea
A star coloring of an undirected graph G is a proper vertex coloring of G (i.e., no two neighbors are assigned the same color) such that any path of length 3 in G is not bicolored. The star chromatic...
Hugh Hind, Michael Molloy, Bruce Reed
We prove that any graph with maximum degree suciently large, has a proper vertex colouring using +1 colours such that each colour class appears at most log 5 times in the neighbourhood of any vertex....
Let Gr denote a graph chosen uniformly at random from the set of r-regular graphs with vertex set {1, 2,..., n} where 3 co. We prove that with probability tending to 1 as n- o, Gr is r-connected and...
Let G r denote a graph chosen uniformly at random from the set of r-regular graphs with vertex set f1; 2; : : : ; ng where 3 r n 1 ; r! 1 ( > 0 can be an arbitrarily small constant) We prove that...
Michael Molloy, Bruce Reed, Equipe Combinatoire
We consider for graphs of maximum degree , the problem of determining whether (G)> k for various values of k. We obtain sharp theorems characterizing when the barrier to k colourability must be a...
Near-optimal list colourings (2007)
Michael Molloy, Bruce Reed, Cnrs Ime-usp
Abstract We show that a simple variant of a naive colouring procedure can be used to list colour the edges of a k-uniform linear hypergraph of maximum degree \Delta provided every vertex has a list...
Determining the minimum number of colours required to colour the vertices of a given graph so that every pair of adjacent vertices receive dierent colours is a notoriously dicult problem. In fact,...
Gruia C Alinescu, Cristina G. Fernandes, Bruce Reed
The Multicut problem can be defined as: given a graph G and a collection of pairs of distinct vertices (s i; t i) of G, find a minimum set of edges of G whoseremoval disconnects each s i from the...
Total Colouring With +poly(log ) (2007)
Hugh Hind, Michael Molloy, Bruce Reed
We provide a polynomial time algorithm which nds a total colouring of any graph with maximum degree , suciently large, using at most + 8 log 8 colours. This improves the best previous upper bound on...
ICM 2002 Vol. III 587-603 (2007)
List Colouring Of, Bruce Reed, Benny Sudakov
Ohba has conjectured [9] that if the graph G has 2(G)+1 or fewer vertices then the list chromatic number and chromatic number of G are equal. In this paper we prove that this conjecture is...
Domination in cubic graphs of large girth (2007)
Rautenbach, Dieter, Reed, Bruce
Preprint / Technische Universität Ilmenau, Institut für Mathematik ; 07-07
The Evolution of the Mixing Rate (2007)
Fountoulakis, Nikolaos, Reed, Bruce
In this paper we present a study of the mixing time of a random walk on the largest component of a supercritical random graph, also known as the giant component. We identify local obstructions that...
Bounding χ in terms of ω and ∆ for quasi-line graphs (extended abstract) (2007)
Let G be a finite simple graph. Then χ(G) is its chromatic number, ∆(G) is its maximum degree, and ω(G) is its clique number. For any graph G, χ(G) ≥ ω(G). On the other hand, it is easy to...
Coloring Artemis graphs (2007)
Benjamin Lévêque, Frédéric Maffray, Bruce Reed, Nicolas Trotignon
We consider the class of graphs that contain no odd hole, no antihole, and no “prism ” (a graph consisting of two disjoint triangles with three disjoint paths between them). We give an algorithm...
Coloring Artemis graphs (2007)
Benjamin Lévêque, Frédéric Maffray, Bruce Reed, Nicolas Trotignon
We consider the class of graphs that contain no odd hole, no antihole, and no “prism ” (a graph consisting of two disjoint triangles with three disjoint paths between them). We give an algorithm...
The edge-density for K2,t minors (2007)
Maria Chudnovsky, Bruce Reed, Paul Seymour
Let H be a graph. If G is an n-vertex simple graph that does not contain H as a minor, what is the maximum number of edges that G can have? This is at most linear in n, but the exact expression is...
On the odd-minor variant of Hadwiger’s conjecture (2006)
Jim Geelen, Bert Gerards, Bruce Reed, Paul Seymour, Adrian Vetta
A Kl-expansion consists of l vertex-disjoint trees, every two of which are joined by an edge. We call such an expansion odd if its vertices can be two-coloured so that the edges of the trees are...
The edges of the complete graph Kn are coloured so that no colour appears more than k = k(n) times, k = ⌈n/(Alnn)⌉, for some sufficiently large A. We show that there is always a Hamiltonian cycle...
Coloring Artemis graphs (2005)
Lévêque, Benjamin, Maffray, Frédéric, Reed, Bruce, Trotignon, Nicolas
We consider the class A of graphs that contain no odd hole, no antihole, and no "prism" (a graph consisting of two disjoint triangles with three disjoint paths between them). We show that the...
Coloring Artemis graphs (2005)
Lévêque, Benjamin, Maffray, Frédéric, Reed, Bruce, Trotignon, Nicolas
We consider the class A of graphs that contain no odd hole, no antihole, and no "prism" (a graph consisting of two disjoint triangles with three disjoint paths between them). We show that the...
Coloring Artemis graphs (2005)
Lévêque, Benjamin, Maffray, Frédéric, Reed, Bruce, Trotignon, Nicolas
We consider the class A of graphs that contain no odd hole, no antihole, and no ``prism'' (a graph consisting of two disjoint triangles with three disjoint paths between them). We show that the...
Coloring Artemis graphs (2005)
Lévêque, Benjamin, Maffray, Frédéric, Reed, Bruce, Trotignon, Nicolas
We consider the class A of graphs that contain no odd hole, no antihole, and no "prism" (a graph consisting of two disjoint triangles with three disjoint paths between them). We show that the...
Coloring Artemis graphs (2005)
Lévêque, Benjamin, Maffray, Frédéric, Reed, Bruce, Trotignon, Nicolas
We consider the class A of graphs that contain no odd hole, no antihole, and no "prism" (a graph consisting of two disjoint triangles with three disjoint paths between them). We show that the...
Maria Chudnovsky, Frédéric Havet, Projet Mascotte, Bruce Reed, Laboratoite Is, Paul Seymour
A hole in a graph is an induced subgraph which is a cycle of length at least four. A hole is called even if it has an even number of vertices. An even-hole-free graph is a graph with no even holes. A...
Planar graph bipartization in linear time (2005)
Samuel Fiorini, Nadia Hardy, Bruce Reed, Adrian Vetta
Abstract. For each constant k, we present a linear time algorithm that, given a planar graph G, either finds a minimum odd cycle vertex transversal in G or guarantees that there is no transversal of...
Excluding any graph as a minor allows a low tree-width 2-coloring (2004)
Matt Devos, Guoli Ding, Bogdan Oporowski, Daniel P. Sanders, Bruce Reed, Paul Seymour, ...
Abstract. This article proves the conjecture of Thomas that, for every graph G, there is an integer k such that every graph with no minor isomorphic to G has a 2-coloring of either its vertices or...
On the Fractional Chromatic Index of a Graph and its Complement (2004)
David Avis, Caterina De Simone, Bruce Reed
The chromatic index χ e(G) ofanundirected graph G is the minimum number of matchings needed to partition its edge set. Let Δ(G) denote the maximum vertex degree of G, and let G denote the...
The Odd Case of Hadwiger's Conjecture (2004)
Jim Geelan, Bert Gerards, Luis Goddyn, Bruce Reed, Paul Seymour
y,
Star Coloring of Graphs (2004)
Fertin, Guillaume, Raspaud, André, Reed, Bruce
A star coloring of an undirected graph G is a proper vertex coloring of G (i.e., no two neighbors are assigned the same color) such that any path of length 3 in G is not bicolored. The star chromatic...
Star Coloring of Graphs (2004)
Fertin, Guillaume, Raspaud, André, Reed, Bruce
A star coloring of an undirected graph G is a proper vertex coloring of G (i.e., no two neighbors are assigned the same color) such that any path of length 3 in G is not bicolored. The star chromatic...
List colouring of graphs with at most $\big(2-o(1)\big)\chi$ vertices (2003)
Ohba has conjectured \cite{ohb} that if the graph $G$ has $2\chi(G)+1$ or fewer vertices then the list chromatic number and chromatic number of $G$ are equal. In this paper we prove that this...
Giant components for two expanding graph processes (2002)
Luc Devroye, Colin McDiarmid, Bruce Reed
We discuss the emergence of giant components in two random graph models (one directed, one undirected). Our study of these models was motivated by an interest in finding a random model of the...
Random regular graphs of non-constant degree (2002)
Colin Cooper, Alan Frieze, Bruce Reed
Let G r denote a graph chosen uniformly at random from the set of r-regular graphs with vertex set f1; 2; : : : ; ng where 3 r c 0 n for some small constant c 0. We prove that with probability...
Graph Colouring via the Probabilistic Method (2002)
Bruce Reed, Equipe Combinatoire Cnrs
Colouring a graph with the minimum number of colours is a classical problem in graph theory and has many applications. For instance, think of a cellular phone network on which each vertex (phone)...
The Erdős-Pósa property for odd cycles in highly connected graphs (2001)
In [9] Thomassen proved that a 2 39k-connected grapheither contains k vertex disjoint odd cycles or an odd cycle cover containing at most 2k − 2 vertices, i.e. he showed that the Erdős–Pósa...
Excluding Any Graph as a Minor Allows a Low Tree-Width 2-Coloring (2001)
Excluding Any, Graph As, A Minor, Allows A Low, Matt Devos, Guoli Ding, ...
This article proves the conjecture of Thomas that, for every graph G, there is an integer k such that every graph with no minor isomorphic to G has a 2-coloring of either its vertices or its edges...
On star coloring of graphs (2001)
Guillaume Fertin, André Raspaud, Bruce Reed
In this paper, we deal with the notion of star coloring of graphs. A star coloring of an undirected graph G is a proper vertex coloring of G (i.e., no two neighbors are assigned the same color) such...
On star coloring of graphs (2001)
Guillaume Fertin, André Raspaud, Bruce Reed
In this paper, we deal with the notion of star coloring of graphs. A star coloring of an undirected graph G is a proper vertex coloring of G (i.e., no two neighbors are assigned the same color) such...
LIST COLOURING WHEN THE CHROMATIC NUMBER IS CLOSE TO THE ORDER OF THE GRAPH (2001)
Ohba has conjectured [7] thatifGhas 2χ(G)+1 or fewer vertices then the list chromatic number and chromatic number of G are equal. In this short note we prove the weaker version of the conjecture...
A Bound on the Strong Chromatic Index (2000)
Of A Graph, Bruce Reed, Equipe Combinatoire, Pierre Marie Curie
Abstract We show that the strong chromatic index of a graph with maximum degree \Delta is at most (2\Gamma ffl)\Delta 2, for some ffl? 0. This answers a question of Erd""os and...
Colin Cooper, Alan Frieze, Michael Molloy, Bruce Reed
Perfect matchings in random r\Gamma regular, s\Gamma uniform hypergraphs.
THE DOMINATING NUMBER OF A RANDOM (2000)
Cubic Graph, Bruce Reed, Equipe Combinatoire, Pierre Marie Curie
Abstract We show that if G is a random 3-regular graph on n vertices, then its dominatingnumber, D(G), almost surely satisfies:2636n ^ D(G) ^:3126n.
Colouring Graphs whose Chromatic Number Is Almost Their Maximum Degree (2000)
In fact, determining whether three colours will suffice was one of the original six problems that Karp reduced Satisfiability to in his seminal 1972 paper [6].
An Improved Algorithm For Finding Tree Decompositions Of Small Width (2000)
We present a modification of Bodlaender's linear time algorithm that, for constant k, determines whether an input graph G has treewidth k and, if so, constructs a tree decomposition of G of...
Random Regular Graphs of Non-Constant Degree (2000)
Colin Cooper, Alan Frieze, Bruce Reed
Let G r denote graph chosen uniformly at random from the set of r-regular graphs with vertex set f1; 2; : : : ; ng and 3 r c 0 n for some small constant c 0 . We prove that with probability tending...
Perfect Matchings in Random R-Regular, S-Uniform Hypergraphs. (2000)
Colin Cooper, Alan Frieze, Michael Molloy, Bruce Reed
this paper is to prove the following result. Theorem 1 Suppose r; s are xed positive integers, r 3, then lim
An Improved Algorithm for Finding Tree Decompositions of Small Width (2000)
Ljubomir Perkovi'c And, Bruce Reed, Equipe Combinatoire Cnrs
. We present a modification of Bodlaender's linear time algorithm that, for constant k, determines whether an input graph G = (V; E) has treewidth k and, if so, constructs a tree decomposition...
In this paper we prove the following result about vertex list colourings, which shows that a conjecture of the first author (1999, J. Graph Theory 31, 149–153) is asymptotically correct.Let G be a...
Coloring the square of a planar graph (1999)
Frédéric Havet, Colin Mcdiarmid, Bruce Reed
In 1977, Wegner conjectured that the chromatic number of the square of every planar graph G with maximum degree ∆ ≥ 8 is at most ⌈ 3 2 ∆ ⌉ + 1. We show that it is at most ∆ (1 + o(1)).
On the mixing rate of the triangulation walk (1999)
Abstract Let Tn denote the set of triangulations of a convex polygon K with n sides. We study the random walk on Tn whose transitions are "flips " of one of the n \Gamma 3 internal...
Critical subgraphs of a random graph (1999)
Michael Molloy, Bruce Reed, Equipe Combinatoire
We prove that the threshold for a random graph to have a k-core is equal to the threshold for having a subgraph which meets a neccesary condition of Gallai for being k-critical. 1991 Mathematics...
On the mixing rate of the triangulation walk (1999)
Let T n denote the set of triangulations of a convex polygon K with n sides. We study the random walk on T n whose transitions are \ ips" of one of the n 3 internal diagonals of the current...
Critical Subgraphs of a Random Graph (1999)
Michael Molloy, Bruce Reed, Equipe Combinatoire
We prove that the threshold for a random graph to have a k-core is equal to the threshold for having a subgraph which meets a necessary condition of Gallai for being k-critical. 1991 Mathematics...
Critical Subgraphs of a Random Graph (1999)
Michael Molloy, Bruce Reed, Equipe Combinatoire
We prove that the threshold for a random graph to have a k-core is equal to the threshold for having a subgraph which meets a necessary condition of Gallai for being k-critical. 1991 Mathematics...
Bruce Reed, Equipe Combinatoire Cnrs, Place Jussieu, Robin Thomas
AgraphHis a minor of a graph G if H can be obtained from a subgraph of G by contracting edges. Let t ≥ 1beaninteger,andletGbe a graph on n vertices with no minor isomorphic to Kt+1. Kostochka...
Probabilistic analysis of algorithms (1998)
Rather than analyzing the worst case performance of algorithms, one can investigate their performance on typical instances of a given size. This is the approach we investigate in this paper. Of...
Further algorithmic aspects of the local lemma (1998)
Michael Molloy, Bruce Reed, Equipe Combinatoire
We provide a method to produce an ecient algorithm to nd an object whose existence is guaranteed by the Lovasz Local Lemma. We feel that this method will apply to the vast majority of applications of...
The size of the giant component of a random graph with a given degree sequence (1998)
Michael Molloy, Bruce Reed, Equipe Combinatoire
Given a sequence of non-negative real numbers 0; 1; : : : which sum to 1, we consider a random graph having approximately i n vertices of degree i. In [12] the authors essentially show that if P i(i...
A bound on the total chromatic number (1998)
Michael Molloy, Bruce Reed, Equipe Combinatoire
We prove that the total chromatic number of any graph with maximum degree \Delta is at most \Delta plus an absolute constant. In particular, we show that for \Delta sufficiently large, the total...
Multicuts in Unweighted Graphs with Bounded Degree and Bounded Tree-Width (1998)
Gruia Calinescu, Cristina G. Fernandes, Bruce Reed
The Multicut problem can be defined as: given a graph G and a collection of pairs of distinct vertices (s i ; t i ) of G, find a minimum set of edges of G whose removal disconnects each s i from the...
A Pseudo-Random Method for List Colouring (1998)
Michael Molloy, Bruce Reed, Cnrs Ime-usp
We show that a simple variant of a naive colouring algorithm can be used to list colour the edges of a k-uniform linear hypergraph of maximum degree provided every vertex has a list of at least...
Clique Minors In Graphs And Their Complements (1998)
A graph H is a minor of a graph G if H can be obtained from a subgraph of G by contracting edges. Let t 1 be an integer, and let G be a graph on n vertices with no minor isomorphic to K t+1 ....
A Strengthening of Brooks' Theorem (1998)
Bruce Reed, Paris Sao Paulo, France Brasil
We show that for suÆcently large , any graph with maximum degree at most and no cliques of size has a 1 colouring. 1 The Result It is easy to see that if the maximum degree of G is , then the...
Colouring Graphs whose Chromatic Number Is Almost Their Maximum Degree (1998)
this paper we present two companion positive results:
The List Colouring Constants (1998)
this paper, we examine a natural condition on the set of lists which allows us to ensure that acceptable colourings exists for much shorter lists. To begin, we return to the simpler bound + 1 on l...
Mangoes and Blueberries (1998)
: We prove the following conjecture of Erd}os and Hajnal: For every integer k there is an f(k) such that if for a graph G, every subgraph H of G with an even number of vertices has a stable set...
Further Algorithmic Aspects of the Local Lemma (1998)
Michael Molloy, Bruce Reed, Equipe Combinatoire
this paper we 1. Provide a general set of conditions, similar to those of the Local Lemma, such that for any problem satisfying these conditions we can not only guarantee the existence of the desired...
Multicuts in Unweighted Graphs with Bounded Degree and Bounded Tree-Width (1998)
Gruia Calinescu, Cristina G. Fernandes, Bruce Reed
. The Multicut problem is defined as follows: given a graph G and a collection of pairs of distinct vertices (s i ; t i ) of G, find a smallest set of edges of G whose removal disconnects each s i...
On the Mixing Rate of the Triangulation Walk (1998)
Let Tn denote the set of triangulations of a convex polygon K with n sides. We study the random walk on Tn whose transitions are "flips" of one of the n-3 internal diagonals of the current...
Multicuts in Unweighted Graphs and Digraphs with Bounded Degree and Bounded Tree-Width (1998)
Gruia Calinescu, Cristina G. Fernandes, Bruce Reed
this paper. Also, we show that Directed Edge Multicut is NP-hard in digraphs with treewidth one and maximum in and out degree three. Other hardness results indicate why we cannot eliminate any of the...
A bound on the strong chromatic index of a graph (1997)
Michael Molloy, Bruce Reed, Equipe Combinatoire
We show that the strong chromatic index of a graph with maximum degree is at most (2 ) 2, for some > 0. This answers a question of Erd}os and Nesetril. 1
Bruce Reed, Equipe Combinatoire, Place Jussieu, Neil Robertson, Paul Seymour, ...
92-J-1965, and partially performed under a consulting agreement with Bellcore.
A critical point for random graphs with a given degree sequence (1995)
Michael Molloy, Bruce Reed, Equipe Combinatoire
Given a sequence of non-negative real numbers 0; 1; : : : which sum to 1, we consider random graphs having approximately i n vertices of degree i. Essentially, we show that if P i(i \Gamma 2) i? 0...
The dominating number of a random cubic graph (1995)
Michael Molloy, Bruce Reed, Equipe Combinatoire
We show that if G is a random 3-regular graph on n vertices, then its dominating number, D(G), almost surely satises:2636n D(G) :3126n. In this paper, we consider the dominating number of a random...
Multicoloured Hamilton Cycles (1995)
Michael Albert, Alan Frieze, Bruce Reed
The edges of the complete graph K n are coloured so that no colour appears more than dcne times, where c! 1=32 is a constant. We show that if n is sufficiently large then there is a Hamiltonian cycle...
Multicoloured Hamilton Cycles (1995)
Michael Albert, Alan Frieze, Bruce Reed
The edges of the complete graph K n are coloured so that no colour appears more than dcne times, where c < 1=32 is a constant. We show that if n is sufficiently large then there is a Hamiltonian...
When is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem? (1995)
Alan Frieze, Richard M. Karp, Bruce Reed
We consider the probabilistic relationship between the value of a random asymmetric traveling salesman problem ATSP (M) and the value of its assignment relaxation AP (M ). We assume here that the...
Multicoloured Hamilton Cycles (1995)
Michael Albert, Alan Frieze, Bruce Reed
The edges of the complete graph K n are coloured so that no colour appears more than dcne times, where c ! 1=32 is a constant. We show that if n is sufficiently large then there is a Hamiltonian...
Multicoloured Hamilton Cycles (1995)
Michael Albert, Alan Frieze, Bruce Reed
The edges of the complete graph Kn are coloured so that no colour appears more than ⌈cn ⌉ times, where c<1/32 is a constant. We show that if n is sufficiently large then there is a Hamiltonian...
When is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem (1995)
We consider the probabilistic relationship between the value of a random asymmetric traveling salesman problem AT SP (M) and the value of its assignment relaxation AP (M). We assume here that the...
Hadwiger’s conjecture for line graphs (1993)
Bruce Reed, Equipe Combinatoire, Paul Seymour
We prove that Hadwiger’s conjecture holds for line graphs. Equivalently, we show that for every loopless graph G (possibly with parallel edges) and every integer k ≥ 0, either G is...
When is the Assignment Bound Tight for the Asymmetric Traveling-Salesman Problem? (1992)
Alan Frieze, Richard M. Karp, Bruce Reed
We consider the probabilistic relationship between the value of a random asymmetric traveling salesman problem ATSP (M) and the value of its assignment relaxation AP (M ). We assume here that the...
A semi-strong perfect graph theorem / (1986)
Written for the School of Computer Science.
Vita.
Thesis (M.A.) - California State University, Fresno.
Typescript.
Typescript (photocopy).
Vita.
Typescript.
Finding odd cycle transversals (0000)
We present an O(mn) algorithm to determine whether a graph G with m edges and n vertices has an odd cycle transversal of order at most k, for any fixed k. We also obtain an algorithm that...
Finding odd cycle transversals
We present an O(mn) algorithm to determine whether a graph G with m edges and n vertices has an odd cycle transversal of order at most k, for any fixed k. We also obtain an algorithm that...