Publications of Bruce Reed

BACK TO COATI PUBLICATION INDEX

Publications of Bruce Reed

Books and proceedings

B. Reed and C. Linhares-Sales, editors. Recent advances in algorithms and combinatorics, CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, 11. Springer-Verlag, New York, 2003. [bibtex-entry]
M. Molloy and B. Reed. Graph colouring and the probabilistic method, volume 23 of Algorithms and Combinatorics. Springer-Verlag, Berlin, 2002. [bibtex-entry]
J. L. Ramìrez Alfonsìn and B. Reed, editors. Perfect graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons Ltd., Chichester, 2001. [bibtex-entry]
M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, and B. Reed, editors. Probabilistic methods for algorithmic discrete mathematics, volume 16 of Algorithms and Combinatorics. Springer-Verlag, Berlin, 1998. [bibtex-entry]

Articles in journal or book's chapters

Frédéric Havet, Bruce Reed, Maya Stein, and David R Wood. A variant of the Erdös-Sós conjecture. Journal of Graph Theory, 94(1):131-158, May 2020. [WWW ] [PDF ] [bibtex-entry]
Bruce Reed, X. Cai, G. Perarnau, and A. B. Watts. Acyclic edge colourings of graphs with large girth. Random Structures & Algorithms, 50(4):511 - 533, July 2017. [WWW ] [bibtex-entry]
Bruce Reed, Felix Joos, Guillem Perarnau, and Dieter Rautenbach. How to determine if a random graph with a fixed degree sequence has a giant component. Probability Theory and Related Fields, January 2017. [WWW ] [bibtex-entry]
Bruce Reed and G. Perarnau. Existence of Spanning â±-Free Subgraphs with Large Minimum Degree. Combinatorics, Probability and Computing, 26(03):448 - 467, May 2017. [WWW ] [bibtex-entry]
Bruce Reed, Jonas Witt, and Marco E. Lübbecke. Polyhedral results on the stable set problem in graphs containing even or odd pairs. Mathematical Programming, June 2017. [WWW ] [bibtex-entry]
L. Addario-Berry, F. Havet, C. Linhares Sales, B. Reed, and S. Thomassé. Oriented trees in digraphs. Discrete Mathematics, 313(8):967-974, 2013. [WWW ] [bibtex-entry]
F. Havet, B. Reed, and J.-S. Sereni. Griggs and Yeh's conjecture and $L(p,1)$-labellings. SIAM Journal on Discrete Mathematics, 26(1):145-168, 2012. [WWW ] [PDF ] [Abstract] [bibtex-entry]
L. Addario-Berry, W.S. Kennedy, A.D. King, Z. Li, and B. Reed. Finding the maximum-weight induced $k$-partite subgraph of an $i$-triangulated graph. Discrete Applied Mathematics, 158(7):765-770, April 2010. [WWW ] [Abstract] [bibtex-entry]
L. Addario-Berry, N. Broutin, and B. Reed. Critical random graphs and the structure of a minimum spanning tree. Random Structures and Algorithms, 35:323--347, 2009. [WWW ] [PDF ] [Abstract] [bibtex-entry]
L. Addario-Berry and B. Reed. Minima in branching random walks. Annals of Probability, 37:1044--1079, 2009. [WWW ] [PDF ] [Abstract] [bibtex-entry]
E. Birmelé, J. A. Bondy, and B. Reed. Tree-width of graphs without a 3 by 3 grid minor. Discrete Applied Mathematics, 157:2577--2598, 2009. [WWW ] [PDF ] [Abstract] [bibtex-entry]
J. Geelen, B. Gerards, B. Reed, P. Seymour, and A. Vetta. On the odd-minor variant of Hadwiger's conjecture. Journal of Combinatorial Theory Ser. B, 99:20--29, 2009. [WWW ] [PDF ] [Abstract] [bibtex-entry]
K. Kawarabayashi, O. Lee, and B. Reed. Removable cycles in non-bipartite graphs. Journal of Combinatorial Theory Ser. B, 99:30--38, 2009. [WWW ] [Abstract] [bibtex-entry]
K. Kawarabayashi and B. Reed. Highly parity linked graphs. Combinatorica, 29:215--225, 2009. [WWW ] [Abstract] [bibtex-entry]
B. Lévêque, F. Maffray, B. Reed, and N. Trotignon. Coloring Artemis graphs. Theoretical Computer Science, 410:2234--2240, 2009. [WWW ] [PDF ] [Abstract] [bibtex-entry]
L. Addario-Berry, M. Chudnovsky, F. Havet, B. Reed, and P. Seymour. Bisimplicial vertices in even-hole-free graphs. Journal of Combinatorial Theory Ser. B, 98(6):1119--1164, 2008. [PDF ] [Abstract] [bibtex-entry]
L. Addario-Berry, K. Dalal, and B. Reed. Degree-Constrained Subgraphs. Discrete Applied Mathematics, 156:1168-1174, 2008. [bibtex-entry]
L. Addario-Berry and B. Reed. Horizons of Combinatorics, volume 17 of Bolyai Society Mathematical Studies, chapter Ballot Theorems, Old and New, pages 9-35. Springer, 2008. [bibtex-entry]
M. Cerioli, L. Faria, T. Ferreira, C. Martinhon, F. Protti, and B. Reed. Partition into cliques for cubic graphs: Planar case, complexity and approximation. Discrete Applied Mathematics, 156:2270-2278, 2008. [bibtex-entry]
S. Fiorini, N. Hardy, B. Reed, and A. Vetta. Planar graph bipartization in linear time. Discrete Applied Mathematics, 156:1175-1180, 2008. [Abstract] [bibtex-entry]
N. Fountoulakis and B. Reed. The evolution of the mixing rate of a simple random walk on the giant component of a random graph. Random Structures and Algorithms, 33:68-86, 2008. [bibtex-entry]
K. Kawarabayashi, O. Lee, B. Reed, and P. Wollan. A weaker version of Lovasz' path removable conjecture. Journal of Combinatorial Theory (Series B), 98:972-979, 2008. [bibtex-entry]
K. Kawarabayashi and B. Reed. Fractional coloring and the odd Hadwiger's conjecture. European Journal of Combinatorics, 29(2):411-417, 2008. [Abstract] [bibtex-entry]
C. Linhares-Sales, F. Maffray, and B. Reed. On Planar Quasi-Parity Graphs. SIAM Journal of Discrete Mathematics, 22:329-347, 2008. [bibtex-entry]
C. McDiarmid and B. Reed. On the maximum degree of a random planar graph. Combinatorics, Probability and Computing, 17:591-601, 2008. [bibtex-entry]
C. Meagher and B. Reed. Fractionally total colouring ${G}_{n,p}$. Discrete Applied Mathematics, 156:1112-1124, 2008. [bibtex-entry]
B. Reed. Skew Partitions in Perfect Graphs. Discrete Applied Mathematics, 156:1150-1156, 2008. [bibtex-entry]
L. Addario-Berry, K. Dalal, C. McDiarmid, B. Reed, and A. Thomason. Vertex Colouring Edge Weightings. Combinatorica, 27:1-12, 2007. [bibtex-entry]
E. Birmelé, J. A. Bondy, and B. Reed. The Erdos-Posa property for long circuits. Combinatorica, 27:135-145, 2007. [bibtex-entry]
S. Fiorini, N. Hardy, B. Reed, and A. Vetta. Approximate min-max relations for odd cycles in planar graphs. Mathematical Programming Ser. B, 110(1):71--91, 2007. [bibtex-entry]
N. Fountoulakis and B. Reed. Faster Mixing and Small Bottlenecks. Probability Theory and Related Fields, 137:475-486, 2007. [bibtex-entry]
J. Bang-Jensen, B. Reed, M. Schacht, R. Sámal, B. Toft, and U. Wagner. Topics in Discrete Mathematics, Dedicated to Jarik Nesetril on the Occasion of his 60th birthday, volume 26 of Algorithms and Combinatorics, chapter On six problems posed by Jarik Nesetril, pages 613--627. Springer, Berlin, M. Klazar, J. Kratochvil, M. Loebl, J. Matousek, R. Thomas and P. Valtr edition, 2006. [bibtex-entry]
C. McDiarmid and B. Reed. Concentration for self-bounding functions and an inequality of talagrand. Random Structures and Algorithms, 29:549--557, 2006. [bibtex-entry]
L. Addario-Berry, R. E. L. Aldred, K. Dalal, and B. Reed. Vertex colouring edge partitions. J. Combin. Theory Ser. B, 94(2):237--244, 2005. [bibtex-entry]
D. Avis, C. De Simone, and B. Reed. On the fractional chromatic index of a graph and its complement. Oper. Res. Lett., 33(4):385--388, 2005. [bibtex-entry]
H. Everett, C. M. H. de Figueiredo, S. Klein, and B. Reed. The perfection and recognition of bull-reducible Berge graphs. Theor. Inform. Appl., 39(1):145--160, 2005. [bibtex-entry]
B. Farzad, M. Molloy, and B. Reed. $(\Delta-k)$-critical graphs. J. Combin. Theory Ser. B, 93(2):173--185, 2005. [bibtex-entry]
B. Reed and B. Sudakov. List colouring when the chromatic number is close to the order of the graph. Combinatorica, 25(1):117--123, 2005. [bibtex-entry]
S. Dantas, C. M. H. de Figueiredo, S. Klein, S. Gravier, and B. Reed. Stable skew partition problem. Discrete Appl. Math., 143(1-3):17--22, 2004. [bibtex-entry]
M. DeVos, G. Ding, B. Oporowski, D. P. Sanders, B. Reed, P. Seymour, and D. Vertigan. Excluding any graph as a minor allows a low tree-width 2-coloring. J. Combin. Theory Ser. B, 91(1):25--41, 2004. [bibtex-entry]
G. Fertin, A. Raspaud, and B. Reed. Star coloring of graphs. J. Graph Theory, 47(3):163--182, 2004. [bibtex-entry]
C. T. Hoàng and B. Reed. On the co-$P\sb 3$-structure of perfect graphs. SIAM J. Discrete Math., 18(3):571--576 (electronic), 2004/05. [bibtex-entry]
B. Reed and P. Seymour. Hadwiger's conjecture for line graphs. European J. Combin., 25(6):873--876, 2004. [bibtex-entry]
B. Reed, K. Smith, and A. Vetta. Finding odd cycle transversals. Oper. Res. Lett., 32(4):299--301, 2004. [bibtex-entry]
B. Reed, S. W. Song, and J. L. Szwarcfiter. Preface [Brazilian Symposium on Graphs, Algorithms and Combinatorics]. Discrete Appl. Math., 141(1-3):1, 2004.
Note: Held in Fortaleza, 2001. [bibtex-entry]
G. Calinescu, C. G. Fernandes, and B. Reed. Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width. J. Algorithms, 48(2):333--359, 2003. [bibtex-entry]
M. Loebl, J. Nesetril, and B. Reed. A note on random homomorphism from arbitrary graphs to $\mathbb Z$. Discrete Math., 273(1-3):173--181, 2003.
Note: EuroComb'01 (Barcelona). [bibtex-entry]
C. McDiarmid and B. Reed. Channel assignment on graphs of bounded treewidth. Discrete Math., 273(1-3):183--192, 2003.
Note: EuroComb'01 (Barcelona). [bibtex-entry]
B. Reed. The height of a random binary search tree. J. ACM, 50(3):306--332 (electronic), 2003. [bibtex-entry]
B. Reed. Algorithmic aspects of tree width. In Recent advances in algorithms and combinatorics, volume 11 of CMS Books Math./Ouvrages Math. SMC, pages 85--107. Springer, New York, 2003. [bibtex-entry]
C. Cooper, A. Frieze, B. Reed, and O. Riordan. Random regular graphs of non-constant degree: independence and chromatic number. Combin. Probab. Comput., 11(4):323--341, 2002. [bibtex-entry]
C. Cooper, A. Frieze, and B. Reed. Random regular graphs of non-constant degree: connectivity and Hamiltonicity. Combin. Probab. Comput., 11(3):249--261, 2002. [bibtex-entry]
L. Devroye, C. McDiarmid, and B. Reed. Giant components for two expanding graph processes. In Mathematics and computer science, II (Versailles, 2002), Trends Math., pages 161--173. Birkhäuser, Basel, 2002. [bibtex-entry]
B. Reed and B. Sudakov. Asymptotically the list colouring constants are 1. J. Combin. Theory Ser. B, 86(1):27--37, 2002. [bibtex-entry]
H. Everett, C. M. H. de Figueiredo, C. Linhares-Sales, F. Maffray, O. Porto, and B. Reed. Even pairs. In Perfect graphs, Wiley-Intersci. Ser. Discrete Math. Optim., pages 67--92. Wiley, Chichester, 2001. [bibtex-entry]
R. Hayward and B. Reed. Forbidding holes and antiholes. In Perfect graphs, Wiley-Intersci. Ser. Discrete Math. Optim., pages 113--137. Wiley, Chichester, 2001. [bibtex-entry]
C. Linhares-Sales, F. Maffray, and B. Reed. Recognizing planar strict quasi-parity graphs. Graphs Combin., 17(4):745--757, 2001. [bibtex-entry]
D. Rautenbach and B. Reed. The Erdos-Pósa property for odd cycles in highly connected graphs. Combinatorica, 21(2):267--278, 2001.
Note: Paul Erdos and his mathematics (Budapest, 1999). [bibtex-entry]
B. Reed. A gentle introduction to semi-definite programming. In Perfect graphs, Wiley-Intersci. Ser. Discrete Math. Optim., pages 233--259. Wiley, Chichester, 2001. [bibtex-entry]
B. Reed. From conjecture to theorem. In Perfect graphs, Wiley-Intersci. Ser. Discrete Math. Optim., pages 13--24. Wiley, Chichester, 2001. [bibtex-entry]
C. Berge and B. Reed. Optimal packings of edge-disjoint odd cycles. Discrete Math., 211(1-3):197--202, 2000. [bibtex-entry]
C. McDiarmid and B. Reed. Channel assignment and weighted coloring. Networks, 36(2):114--117, 2000. [bibtex-entry]
L. Perkovic and B. Reed. An improved algorithm for finding tree decompositions of small width. Internat. J. Found. Comput. Sci., 11(3):365--371, 2000.
Note: Selected papers from the Workshop on Theoretical Aspects of Computer Science (WG 99), Part 1 (Ascona). [bibtex-entry]
B. Reed and R. Thomas. Clique minors in graphs and their complements. J. Combin. Theory Ser. B, 78(1):81--85, 2000. [bibtex-entry]
C. Berge and B. Reed. Edge-disjoint odd cycles in graphs with small chromatic number. Ann. Inst. Fourier (Grenoble), 49(3):783--786, 1999.
Note: Symposium à la Mémoire de François Jaeger (Grenoble, 1998). [bibtex-entry]
Hugh Hind, M. Molloy, and B. Reed. Total coloring with $\Delta+{\rm poly}(\log\Delta)$ colors. SIAM J. Comput., 28(3):816--821 (electronic), 1999. [bibtex-entry]
F. Maffray and B. Reed. A description of claw-free perfect graphs. J. Combin. Theory Ser. B, 75(1):134--156, 1999. [bibtex-entry]
C. McDiarmid and B. Reed. Colouring proximity graphs in the plane. Discrete Math., 199(1-3):123--137, 1999. [bibtex-entry]
M. Molloy and B. Reed. Graph colouring via the probabilistic method. In Graph theory and combinatorial biology (Balatonlelle, 1996), volume 7 of Bolyai Soc. Math. Stud., pages 125--155. János Bolyai Math. Soc., Budapest, 1999. [bibtex-entry]
M. Molloy and B. Reed. Critical subgraphs of a random graph. Electron. J. Combin., 6:Research Paper 35, 13 pp. (electronic), 1999. [bibtex-entry]
M. Molloy, B. Reed, and William Steiger. On the mixing rate of the triangulation walk. In Randomization methods in algorithm design (Princeton, NJ, 1997), volume 43 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 179--190. Amer. Math. Soc., Providence, RI, 1999. [bibtex-entry]
B. Reed. Mangoes and blueberries. Combinatorica, 19(2):267--296, 1999. [bibtex-entry]
B. Reed. Edge coloring nearly bipartite graphs. Oper. Res. Lett., 24(1-2):11--14, 1999. [bibtex-entry]
B. Reed. The list colouring constants. J. Graph Theory, 31(2):149--153, 1999. [bibtex-entry]
B. Reed. A strengthening of Brooks' theorem. J. Combin. Theory Ser. B, 76(2):136--149, 1999. [bibtex-entry]
A. M. Frieze and B. Reed. Probabilistic analysis of algorithms. In Probabilistic methods for algorithmic discrete mathematics, volume 16 of Algorithms Combin., pages 36--92. Springer, Berlin, 1998. [bibtex-entry]
M. Molloy and B. Reed. The size of the giant component of a random graph with a given degree sequence. Combin. Probab. Comput., 7(3):295--305, 1998. [bibtex-entry]
M. Molloy and B. Reed. A bound on the total chromatic number. Combinatorica, 18(2):241--280, 1998. [bibtex-entry]
B. Reed. $\omega,\ \Delta$, and $\chi$. J. Graph Theory, 27(4):177--212, 1998. [bibtex-entry]
B. Reed and P. Seymour. Fractional colouring and Hadwiger's conjecture. J. Combin. Theory Ser. B, 74(2):147--152, 1998. [bibtex-entry]
H. Everett, S. Klein, and B. Reed. An algorithm for finding homogeneous pairs. Discrete Appl. Math., 72(3):209--218, 1997. [bibtex-entry]
H. Hind, M. Molloy, and B. Reed. Colouring a graph frugally. Combinatorica, 17(4):469--482, 1997. [bibtex-entry]
C. Linhares-Sales, F. Maffray, and B. Reed. On planar perfectly contractile graphs. Graphs Combin., 13(2):167--187, 1997. [bibtex-entry]
M. Molloy and B. Reed. A bound on the strong chromatic index of a graph. J. Combin. Theory Ser. B, 69(2):103--109, 1997. [bibtex-entry]
L. Perkovic and B. Reed. Edge coloring regular graphs of high degree. Discrete Math., 165/166:567--578, 1997.
Note: Graphs and combinatorics (Marseille, 1995). [bibtex-entry]
C. Cooper, A. Frieze, M. Molloy, and B. Reed. Perfect matchings in random $r$-regular, $s$-uniform hypergraphs. Combin. Probab. Comput., 5(1):1--14, 1996. [bibtex-entry]
B. Reed. Paths, stars and the number three. Combin. Probab. Comput., 5(3):277--295, 1996. [bibtex-entry]
B. Reed, N. Robertson, P. Seymour, and R. Thomas. Packing directed circuits. Combinatorica, 16(4):535--554, 1996. [bibtex-entry]
M. Albert, A. Frieze, and B. Reed. Multicoloured Hamilton cycles. Electron. J. Combin., 2:Research Paper 10, approx. 13 pp. (electronic), 1995. [bibtex-entry]
M. Albert, A. Frieze, and B. Reed. Comments on: ``Multicoloured Hamilton cycles'' [Electron. J. Combin. \bf 2 (1995), Research Paper 10, 13 pp. (electronic); MR1327570 (96b:05058)]. Electron. J. Combin., 2:Research Paper 10, Comment 1, 1 HTML document (electronic), 1995. [bibtex-entry]
L. Devroye and B. Reed. On the variance of the height of random binary search trees. SIAM J. Comput., 24(6):1157--1162, 1995. [bibtex-entry]
A. Frieze, R. M. Karp, and B. Reed. When is the assignment bound tight for the asymmetric traveling-salesman problem?. SIAM J. Comput., 24(3):484--493, 1995. [bibtex-entry]
A. Frieze and B. Reed. Covering the edges of a random graph by cliques. Combinatorica, 15(4):489--497, 1995. [bibtex-entry]
B. Gamble, W. Pulleyblank, B. Reed, and B. Shepherd. Right angle free subsets in the plane. Graphs Combin., 11(2):121--129, 1995. [bibtex-entry]
C. McDiarmid and B. Reed. Almost every graph can be covered by $\lceil{\Delta/2}\rceil$ linear forests. Combin. Probab. Comput., 4(3):257--268, 1995. [bibtex-entry]
M. Molloy and B. Reed. The dominating number of a random cubic graph. Random Structures Algorithms, 7(3):209--221, 1995. [bibtex-entry]
B. Reed. Rooted routing in the plane. Discrete Appl. Math., 57(2-3):213--227, 1995.
Note: Combinatorial optimization 1992 (CO92) (Oxford). [bibtex-entry]
B. Reed and N. Sbihi. Recognizing bull-free perfect graphs. Graphs Combin., 11(2):171--178, 1995. [bibtex-entry]
C. McDiarmid, B. Reed, A. Schrijver, and B. Shepherd. Induced circuits in planar graphs. J. Combin. Theory Ser. B, 60(2):169--176, 1994. [bibtex-entry]
B. Bollobás, B. Reed, and A. Thomason. An extremal function for the achromatic number. In Graph structure theory (Seattle, WA, 1991), volume 147 of Contemp. Math., pages 161--165. Amer. Math. Soc., Providence, RI, 1993. [bibtex-entry]
G. Cornuéjols and B. Reed. Complete multi-partite cutsets in minimal imperfect graphs. J. Combin. Theory Ser. B, 59(2):191--198, 1993. [bibtex-entry]
A. Frieze and B. Reed. Polychromatic Hamilton cycles. Discrete Math., 118(1-3):69--74, 1993. [bibtex-entry]
K. Kilakos and B. Reed. Fractionally colouring total graphs. Combinatorica, 13(4):435--440, 1993. [bibtex-entry]
C. McDiarmid and B. Reed. On total colourings of graphs. J. Combin. Theory Ser. B, 57(1):122--130, 1993. [bibtex-entry]
B. Reed. Rooted routing in the plane. CWI Quarterly, 6(3):241--255, 1993. [bibtex-entry]
B. Reed. Counterexamples to a conjecture of Las Vergnas and Meyniel. In Graph structure theory (Seattle, WA, 1991), volume 147 of Contemp. Math., pages 157--159. Amer. Math. Soc., Providence, RI, 1993. [bibtex-entry]
N. Alon, C. McDiarmid, and B. Reed. Star arboricity. Combinatorica, 12(4):375--380, 1992. [bibtex-entry]
A. Frieze, C. McDiarmid, and B. Reed. On a conjecture of Bondy and Fan. Ars Combin., 33:329--336, 1992. [bibtex-entry]
K. Kilakos and B. Reed. A semi-integral total colouring. In Sets, graphs and numbers (Budapest, 1991), volume 60 of Colloq. Math. Soc. János Bolyai, pages 429--438. North-Holland, Amsterdam, 1992. [bibtex-entry]
B. Reed and C. McDiarmid. The strongly connected components of $1$-in, $1$-out. Combin. Probab. Comput., 1(3):265--274, 1992. [bibtex-entry]
N. Alon, C. McDiarmid, and B. Reed. Acyclic coloring of graphs. Random Structures Algorithms, 2(3):277--288, 1991. [bibtex-entry]
A. Frieze, C. McDiarmid, and B. Reed. Greedy matching on the line. SIAM J. Comput., 19(4):666--672, 1990. [bibtex-entry]
C. McDiarmid and B. Reed. Linear arboricity of random regular graphs. Random Structures Algorithms, 1(4):443--445, 1990. [bibtex-entry]
A. M. Frieze, B. Jackson, C. J. H. McDiarmid, and B. Reed. Edge-colouring random graphs. J. Combin. Theory Ser. B, 45(2):135--149, 1988. [bibtex-entry]
C. L. Monma, B. Reed, and W. T. Trotter, Jr.. Threshold tolerance graphs. J. Graph Theory, 12(3):343--362, 1988. [bibtex-entry]
C. T. Hoàng and B. Reed. A note on short cycles in digraphs. Discrete Math., 66(1-2):103--107, 1987. [bibtex-entry]
B. Reed. A semistrong perfect graph theorem. J. Combin. Theory Ser. B, 43(2):223--240, 1987. [bibtex-entry]
B. Reed. A note on the semistrong perfect graph conjecture. Discrete Math., 54(1):111--112, 1985. [bibtex-entry]

Conference's articles

N. Fountoulakis and B. Reed. A general critical condition for the emergence of a giant component in random graphs with given degrees. In European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2009), volume 34 of Electronic Notes on Discrete Mathematics, Bordeaux, France, pages 639--645, September 2009. [bibtex-entry]
K. Kawarabayashi and B. Reed. Hadwiger's Conjecture is decidable. In 41th ACM Symposium on Theory of Computing (STOC 2009), pages 445--454, 2009. [WWW ] [PDF ] [Abstract] [bibtex-entry]
K. Kawarabayashi and B. Reed. A nearly linear time algorithm for the half integral parity disjoint paths packing problem. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithm (SODA 2009), pages 1183--1192, January 2009. [WWW ] [PDF ] [Abstract] [bibtex-entry]
S. Kennedy, C. Meagher, and B. Reed. Fractionally Edge Colouring Graphs with Large Maximum Degree in Linear Time. In European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2009), volume 34 of Electronic Notes on Discrete Mathematics, Bordeaux, France, pages 47--51, September 2009. [Abstract] [bibtex-entry]
F. Havet, B. Reed, and J.-S. Sereni. L(2,1)-labelling of graphs. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithm (SODA 2008), pages 621-630, January 2008. [WWW ] [PDF ] [Abstract] [bibtex-entry]
K. Kawarabayashi and B. Reed. A nearly linear time algorithm for the half integral disjoint paths packing. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithm (SODA 2008), pages 446-454, 2008. [PDF ] [Abstract] [bibtex-entry]
Z. Li and B. Reed. Optimization and Recognition for ${K}_5$-minor Free Graphs in Linear Time. In Proceedings of LATIN, pages 206-215, 2008. [bibtex-entry]
O. Amini and B. Reed. List Colouring Constants of Triangle Free Graphs. In IV Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS 07), Puerto Varas, Chile, pages 6p, November 2007. [WWW ] [PDF ] [Abstract] [bibtex-entry]
E. Birmele, J. A. Bondy, and B. Reed. Brambles, Prisms and Grids. In Proceedings of a Conference in Memory of Claude Berge, Graph Theory in Paris, Basel, pages 37-44, 2007. Birkhauser. [bibtex-entry]
A. Chattopadhyay and B. Reed. Properly 2-Colouring Linear Hypergraphs. In 11th Intl. Workshop on Randomization and Computation (RANDOM 2007), volume 4627 of Lecture Notes in Computer Science, Princeton University, NJ, USA, pages 395-408, 2007. Springer. [PDF ] [bibtex-entry]
F. Havet, J. van den Heuvel, C. McDiarmid, and B. Reed. List colouring squares of planar graphs. In European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2007), volume 29 of Electronic Notes in Discrete Mathematics, Sevilla, Spain, pages 515-519, September 2007. [PDF ] [bibtex-entry]
K. Kawarabayashi and B. Reed. Computing crossing number in linear time.. In 39th ACM Symposium on Theory of Computing (STOC 2007), San Diego, CA, USA, pages 382-390, June 2007. [bibtex-entry]
A. King and B. Reed. Asymptotics of the chromatic number for quasi-line graphs. In European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2007), volume 29 of Electronic Notes in Discrete Mathematics, Sevilla, Spain, pages 327-331, September 2007. [bibtex-entry]
L. Addario-Berry, K. Dalal, and B. Reed. Degree constrained subgraphs. In Proceedings of GRACO2005, volume 19 of Electron. Notes Discrete Math., Amsterdam, pages 257--263 (electronic), 2005. Elsevier. [bibtex-entry]
S. Fiorini, N. Hardy, B. Reed, and A. Vetta. Planar graph bipartization in linear time. In Proceedings of GRACO2005, volume 19 of Electron. Notes Discrete Math., Amsterdam, pages 265--271 (electronic), 2005. Elsevier. [bibtex-entry]
S. Fiorini, N. Hardy, B. Reed, and A. Vetta. Approximate min-max relations for odd cycles in planar graphs. In Integer programming and combinatorial optimization, volume 3509 of Lecture Notes in Comput. Sci., Berlin, pages 35--50, 2005. Springer. [bibtex-entry]
Z. Li and B. Reed. Heap building bounds. In Algorithms and data structures, volume 3608 of Lecture Notes in Comput. Sci., Berlin, pages 14--23, 2005. Springer. [bibtex-entry]
C. Meagher and B. Reed. Fractionally total colouring $G\sb {n,p}$. In Proceedings of GRACO2005, volume 19 of Electron. Notes Discrete Math., Amsterdam, pages 297--303 (electronic), 2005. Elsevier. [bibtex-entry]
B. Reed and B. Sudakov. List colouring of graphs with at most $(2-o(1))\chi$ vertices. In Proceedings of the International Congress of Mathematicians, Vol. III (Beijing, 2002), Beijing, pages 587--603, 2002. Higher Ed. Press. [bibtex-entry]
H. Everett, C. M. H. de Figueiredo, S. Klein, and B. Reed. Bull-reducible Berge graphs are perfect. In Comb01---Euroconference on Combinatorics, Graph Theory and Applications, volume 10 of Electron. Notes Discrete Math., Amsterdam, pages 3 pp. (electronic), 2001. Elsevier. [bibtex-entry]
G. Fertin, A. Raspaud, and B. Reed. On star coloring of graphs. In Graph-theoretic concepts in computer science (Boltenhagen, 2001), volume 2204 of Lecture Notes in Comput. Sci., Berlin, pages 140--153, 2001. Springer. [bibtex-entry]
C. McDiarmid and B. Reed. Channel assignment on nearly bipartite and bounded treewidth graphs. In Comb01---Euroconference on Combinatorics, Graph Theory and Applications, volume 10 of Electron. Notes Discrete Math., Amsterdam, pages 4 pp. (electronic), 2001. Elsevier. [bibtex-entry]
M. Molloy and B. Reed. Colouring graphs when the number of colours is nearly the maximum degree. In Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, New York, pages 462--470 (electronic), 2001. ACM. [bibtex-entry]
D. Rautenbach and B. Reed. Approximately covering by cycles in planar graphs. In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (Washington, DC, 2001), Philadelphia, PA, pages 402--406, 2001. SIAM. [bibtex-entry]
M. Molloy and B. Reed. $k$-colouring when $k$ is close to $\Delta$. In 6th International Conference on Graph Theory (Marseille, 2000), volume 5 of Electron. Notes Discrete Math., Amsterdam, pages 4 pp. (electronic), 2000. Elsevier. [bibtex-entry]
M. Molloy and B. Reed. Near-optimal list colorings. In Proceedings of the Ninth International Conference ``Random Structures and Algorithms'' (Poznan, 1999), volume 17, pages 376--402, 2000. [bibtex-entry]
B. Reed. How tall is a tree?. In Proceedings of the Thiry-Second Annual ACM Symposium on Theory of Computing, New York, pages 479--483 (electronic), 2000. ACM. [bibtex-entry]
M. Molloy and B. Reed. Further algorithmic aspects of the local lemma. In STOC '98 (Dallas, TX), New York, pages 524--529, 1999. ACM. [bibtex-entry]
L. Perkovic and B. Reed. An improved algorithm for finding tree decompositions of small width. In Graph-theoretic concepts in computer science (Ascona, 1999), volume 1665 of Lecture Notes in Comput. Sci., Berlin, pages 148--154, 1999. Springer. [bibtex-entry]
B. Reed. Introducing directed tree width. In 6th Twente Workshop on Graphs and Combinatorial Optimization (Enschede, 1999), volume 3 of Electron. Notes Discrete Math., Amsterdam, pages 8 pp. (electronic), 1999. Elsevier. [bibtex-entry]
Gruia Calinescu, Cristina G. Fernandes, and B. Reed. Multicuts in unweighted graphs with bounded degree and bounded tree-width. In Integer programming and combinatorial optimization (Houston, TX, 1998), volume 1412 of Lecture Notes in Comput. Sci., Berlin, pages 137--152, 1998. Springer. [bibtex-entry]
Hazel Everett, Sulamita Klein, and B. Reed. An optimal algorithm for finding clique-cross partitions. In Proceedings of the Twenty-ninth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1998), volume 135, pages 171--177, 1998. [bibtex-entry]
M. Molloy and B. Reed. Colouring graphs where chromatic number is almost their maximum degree. In LATIN'98: theoretical informatics (Campinas, 1998), volume 1380 of Lecture Notes in Comput. Sci., Berlin, pages 216--225, 1998. Springer. [bibtex-entry]
M. Molloy and B. Reed. A critical point for random graphs with a given degree sequence. In Proceedings of the Sixth International Seminar on Random Graphs and Probabilistic Methods in Combinatorics and Computer Science, ``Random Graphs '93'' (Poznan, 1993), volume 6, pages 161--179, 1995. [bibtex-entry]
C. McDiarmid, B. Reed, A. Schrijver, and B. Shepherd. Noninterfering network flows. In Algorithm theory---SWAT '92 (Helsinki, 1992), volume 621 of Lecture Notes in Comput. Sci., Berlin, pages 245--257, 1992. Springer. [bibtex-entry]
C. L. Monma, B. Reed, and W. T. Trotter, Jr.. A generalization of threshold graphs with tolerances. In Proceedings of the seventeenth Southeastern international conference on combinatorics, graph theory, and computing (Boca Raton, Fla., 1986), volume 55, pages 187--197, 1986. [bibtex-entry]

Internal reports

L. Addario-Berry, F. Havet, C. Linhares Sales, B. Reed, and S. Thomassé. Oriented trees in digraphs. Research Report 7502, INRIA, 01 2011. [WWW ] [PDF ] [Abstract] [bibtex-entry]
F. Havet, B. Reed, and J.-S. Sereni. $L(p,1)$-labelling of graphs. Research Report RR-6673, INRIA, October 2008. [PDF ] [Abstract] [bibtex-entry]
F. Havet, J. van den Heuvel, C. McDiarmid, and B. Reed. List Colouring Squares of Planar Graphs. Research Report RR-6586, INRIA, July 2008. [Abstract] [bibtex-entry]

BACK TO COATI PUBLICATION INDEX

Last modified: Sat Jan 29 19:00:46 2022