Hostname: page-component-7b9c58cd5d-sk4tg Total loading time: 0 Render date: 2025-03-14T23:51:06.773Z Has data issue: false hasContentIssue false
  • English
  • Français

Colouring Random 4-Regular Graphs

Published online by Cambridge University Press:  01 March 2007

LINGSHENG SHI  and
NICHOLAS WORMALD
LINGSHENG SHI
Affiliation:
Department of Combinatorics and Optimization, University of Waterloo, Waterloo ON, CanadaN2L 3G1 (e-mail: lshi@math.tsinghua.edu.cn, nwormald@uwaterloo.ca)
NICHOLAS WORMALD
Affiliation:
Department of Combinatorics and Optimization, University of Waterloo, Waterloo ON, CanadaN2L 3G1 (e-mail: lshi@math.tsinghua.edu.cn, nwormald@uwaterloo.ca)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We show that a random 4-regular graph asymptotically almost surely (a.a.s.) has chromatic number 3. The proof uses an efficient algorithm which a.a.s. 3-colours a random 4-regular graph. The analysis includes use of the differential equation method, and exponential bounds on the tail of random variables associated with branching processes. A substantial part of the analysis applies to random d-regular graphs in general.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 16 , Issue 2 , March 2007 , pp. 309 - 344
Copyright
Copyright © Cambridge University Press 2006

References

[1]Achlioptas, D. and Moore, C. (2003) Almost all graphs with average degree 4 are 3-colourable. J. Comput. System Sci. 67 441–471.CrossRefGoogle Scholar
[2]Achlioptas, D. and Naor, A. (2005) The two possible values of the chromatic number of a random graph. Ann. of Math. 162 1335–1351.CrossRefGoogle Scholar
[3]Bollobás, B. (1985) Random Graphs, Academic Press, New York.Google Scholar
[4]Díaz, J., Serna, M. and Wormald, N. C. Computation of the bisection width for random d-regular graphs. Theoret. Comput. Sci., to appear.Google Scholar
[5]Janson, S., Łuczak, T. and Ruciński, A. (2000) Random Graphs, Wiley, New York.CrossRefGoogle Scholar
[6]Molloy, M. and Reed, B. (1998) The size of the giant component of a random graph with a given degree sequence. Combin. Probab. Comput. 7 295–305.CrossRefGoogle Scholar
[7]Shi, L. and Wormald, N. Colouring random d-regular graphs. Combin. Probab. Comput. (to appear).Google Scholar
[8]Spencer, J. and Wormald, N. Birth control for giants. Combinatorica (to appear).Google Scholar
[9]Wormald, N. C. (1981) The asymptotic distribution of short cycles in random regular graphs. J. Combin. Theory Ser. B 31 168–182.CrossRefGoogle Scholar
[10]Wormald, N. C. (1995) Differential equations for random processes and random graphs. Ann. Appl. Probab. 5 1217–1235.CrossRefGoogle Scholar
[11]Wormald, N. C. (1999) The differential equation method for random graph processes and greedy algorithms. In Lectures on Approximation and Randomized Algorithms (Karoński, M. and Prömel, H., eds), PWN, Warsaw, pp. 73–155.Google Scholar
[12]Wormald, N. C. (1999) Models of random regular graphs. In Surveys in Combinatorics (Lamb, J. D. and Preece, D. A., eds), pp. 239–298.Google Scholar
[13]Wormald, N. C. (2004) Random graphs and asymptotics. Section 8.2 in Handbook of Graph Theory (Gross, J. L. and Yellen, J., eds), CRC, Boca Raton, pp. 817–836.Google Scholar