Combinatorics, Probability & Computing, Volume 16, 2007

Volume 16, Number 1, January 2007

Pierre Charbit, Stéphan Thomassé, Anders Yeo:
The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments. 1-4
Amin Coja-Oghlan, Andreas Goerdt, André Lanka:
Strong Refutation Heuristics for Random k-SAT. 5-28
Devdatt P. Dubhashi, Johan Jonasson, Desh Ranjan:
Positive Influence and Negative Dependence. 29-41
Leslie Ann Goldberg, Mark Jerrum:
The Complexity of Ferromagnetic Ising with Local Fields. 43-61
Kevin Hutson, Thomas M. Lewis:
The Expected Length of a Minimal Spanning Tree of a Cylinder Graph. 63-83
Bill Jackson:
Zero-Free Intervals for Flow Polynomials of Near-Cubic Graphs. 85-108
Peter Keevash, Dhruv Mubayi, Benny Sudakov, Jacques Verstraëte:
Rainbow Turán Problems. 109-126
Jan Remy, Alexander Souza, Angelika Steger:
On an Online Spanning Tree Problem in Randomly Weighted Graphs. 127-144
C. R. Subramanian:
List Set Colouring: Bounds and Algorithms. 145-158
Ádám Timár:
Cutsets in Infinite Graphs. 159-166
Alexandr V. Kostochka, Gexin Yu:
Ore-type graph packing problems. 167-169
Norman Biggs:
Topics in Algebraic Graph Theory, by Lowell W. Beineke and Robin J. Wilson (Academic Consultant: Peter J. Cameron), Encyclopedia of Mathematics and its Applications 102, CUP 2005, 257pp., GBP 50.00/$95.00. 171-172

Noga Alon, Vera Asodi:
Edge Colouring with Delays. 173-191
Joseph E. Bonin, Omer Giménez:
Multi-Path Matroids. 193-217
Mei-Chu Chang:
Additive and Multiplicative Structure in Matrix Spaces. 219-238
Bill Cuckler:
Hamiltonian Cycles in Regular Tournaments. 239-249
G. E. Farr:
On the Ashkin-Teller Model and Tutte-Whitney Functions. 251-260
Abraham D. Flaxman, Alan M. Frieze, Juan Vera:
Adversarial Deletion in a Scale-Free Random Graph Process. 261-270
Dalibor Froncek, Janja Jerebic, Sandi Klavzar, Petr Kovár:
Strong Isometric Dimension, Biclique Coverings, and Sperner's Theorem. 271-275
Daniela Kühn, Deryk Osthus:
Maximizing Several Cuts Simultaneously. 277-283
William D. May, John C. Wierman:
The Application of Non-Crossing Partitions to Improving Percolation Threshold Bounds. 285-307
Lingsheng Shi, Nicholas C. Wormald:
Colouring Random 4-Regular Graphs. 309-344

Brian H. Bowditch:
The Angel Game in the Plane. 345-362
András Máthé:
The Angel of Power 2 Wins. 363-374
Tom Bohman, Alan M. Frieze, Tomasz Luczak, Oleg Pikhurko, Clifford D. Smyth, Joel Spencer, Oleg Verbitsky:
First-Order Definability of Trees and Sparse Random Graphs. 375-400
Peter J. Cameron, Koko Kalambay Kayibi:
Orbital Chromatic and Flow Roots. 401-407
Hemanshu Kaul, Alexandr V. Kostochka:
Extremal Graphs for a Graph Packing Theorem of Sauer and Spencer. 409-416
R. Marchand, E. Zohoorian Azad:
Limit Law of the Length of the Standard Right Factor of a Lyndon Word. 417-434
Martin Möhle:
On a Class of Non-Regenerative Sampling Distributions. 435-444
Eran Ofek:
On the Expansion of the Giant Component in Percolated (n, d, lambda) Graphs. 445-457
Lingsheng Shi, Nicholas C. Wormald:
Colouring Random Regular Graphs. 459-494
Jeff Kahn, G. I. L. Kalai:
Thresholds and Expectation Thresholds. 495-502

Luke Pebody:
Reconstructing Odd Necklaces. 503-514
Amin Coja-Oghlan:
Colouring Semirandom Graphs. 515-552
Harout K. Aydinian, Péter L. Erdös:
All Maximum Size Two-Part Sperner Systems: In Short. 553-555
Colin Cooper, Martin E. Dyer, Catherine S. Greenhill:
Sampling Regular Graphs and a Peer-to-Peer Network. 557-593
Jurek Czyzowicz, Dariusz R. Kowalski, Euripides Markou, Andrzej Pelc:
Searching for a Black Hole in Synchronous Tree Networks. 595-619
Svante Linusson, Johan Wästlund:
Completing a (k - 1)-Assignment. 621-629
Svante Janson, Joel Spencer:
A Point Process Describing the Component Sizes in the Critical Window of the Random Graph Evolution. 631-658
Richard Dudley:
The Generic Chaining: Upper and Lower Bounds of Stochastic Processes, by Michel Talagrand , Springer-Verlag, 2005. 659-660

Béla Csaba:
On the Bollobás-Eldridge Conjecture for Bipartite Graphs. 661-691
Dvir Falik, Alex Samorodnitsky:
Edge-Isoperimetric Inequalities and Influences. 693-712
Abraham D. Flaxman, Alan M. Frieze, Juan Carlos Vera:
On the Average Case Performance of Some Greedy Approximation Algorithms For the Uncapacitated Facility Location Problem. 713-732
Alan M. Frieze, Michael Krivelevich, Clifford D. Smyth:
On the Chromatic Number of Random Graphs with a Fixed Degree Sequence. 733-746
Norbert Hegyvári, François Hennecart, Alain Plagne:
Answer to a Question by Burr and Erdös on Restricted Addition, and Related Results. 747-756
Svante Janson:
On a Random Graph Related to Quantum Theory. 757-766
János Körner, Blerina Sinaimeri:
On Cancellative Set Families. 767-773
Tomasz Schoen:
Difference Covers. 775-787
Mark Walters:
Extensions of the Polynomial Hales-Jewett Theorem. 789-803
Raphael Yuster:
Packing Cliques in Graphs with Independence Number 2. 805-817

Alexander Gnedin, Jim Pitman:
Poisson Representation of a Ewens Fragmentation Process. 819-827
Pierre Charbit, Stéphan Thomassé:
Graphs with Large Girth Not Embeddable in the Sphere. 829-832
Vojtech Rödl, Mathias Schacht:
Regular Partitions of Hypergraphs: Regularity Lemmas. 833-885
Vojtech Rödl, Mathias Schacht:
Regular Partitions of Hypergraphs: Counting Lemmas. 887-901
Mike A. Steel, László A. Székely:
Teasing Apart Two Trees. 903-922
Amin Coja-Oghlan:
On the Laplacian Eigenvalues of G_{n, p}. 923-946
Joanna A. Ellis-Monaghan, Irasema Sarmiento:
Distance Hereditary Graphs and the Interlace Polynomial. 947-973

Last update Wed May 22 17:24:54 2013 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page