Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-09T18:01:54.858Z Has data issue: false hasContentIssue false
  • English
  • Français

The t-Improper Chromatic Number of Random Graphs

Published online by Cambridge University Press:  09 September 2009

ROSS J. KANG  and
COLIN McDIARMID
ROSS J. KANG
Affiliation:
School of Computer Science, McGill University, Montréal, Québec, H2A 2A7, Canada (e-mail: rosskang@cs.mcgill.ca)
COLIN McDIARMID
Affiliation:
Department of Statistics, University of Oxford, 1 South Parks Road, Oxford OX1 3TG, UK (e-mail: cmcd@stats.ox.ac.uk)
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 consider the t-improper chromatic number of the Erdős–Rényi random graph Gn,p. The t-improper chromatic number χt(G) is the smallest number of colours needed in a colouring of the vertices in which each colour class induces a subgraph of maximum degree at most t. If t = 0, then this is the usual notion of proper colouring. When the edge probability p is constant, we provide a detailed description of the asymptotic behaviour of χt(Gn,p) over the range of choices for the growth of t = t(n).

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 19 , Issue 1 , January 2010 , pp. 87 - 98
Copyright
Copyright © Cambridge University Press 2009

References

[1]Andrews, J. A. and Jacobson, M. S. (1985) On a generalization of chromatic number. In Proc. Sixteenth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton 1985), Congr. Numer. 4733–48.Google Scholar
[2]Bollobás, B. (1988) The chromatic number of random graphs. Combinatorica 8 49–55.CrossRefGoogle Scholar
[3]Bollobás, B. (2001) Random Graphs, 2nd edn, Vol. 73 of Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge.CrossRefGoogle Scholar
[4]Bollobás, B. and Thomason, A. (2000) The structure of hereditary properties and colourings of random graphs. Combinatorica. 20 (2)173–202.Google Scholar
[5]Cowen, L. J., Cowen, R. H. and Woodall, D. R. (1986) Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency. J. Graph Theory 10 187–195.CrossRefGoogle Scholar
[6]Cowen, L., Goddard, W. and Jesurum, C. E. (1997) Defective coloring revisited. J. Graph Theory 24 205–219.3.0.CO;2-T>CrossRefGoogle Scholar
[7]Dembo, A. and Zeitouni, O. (1998) Large Deviations Techniques and Applications, 2nd edn, Vol. 38 of Applications of Mathematics (New York), Springer, New York.CrossRefGoogle Scholar
[8]Eaton, N. and Hull, T. (1999) Defective list colorings of planar graphs. Bull. Inst. Combin. Appl. 25 79–87.Google Scholar
[9]Fountoulakis, N., Kang, R. J. and McDiarmid, C. (2008) The t-stability number of a random graph. Submitted; arxiv.0809.0141: [math.CO].Google Scholar
[10]Grimmett, G. R. and McDiarmid, C. J. H. (1975) On colouring random graphs. Math. Proc. Cambridge Philos. Soc. 77 313–324.CrossRefGoogle Scholar
[11]Harary, F. (1985) Conditional colorability in graphs. In Graphs and Applications (Boulder 1982), Wiley–Interscience, pp. 127–136.Google Scholar
[12]Harary, F. and Jones, K. F. (1985) Conditional colorability II: Bipartite variations. In Proc. Sundance Conference on Combinatorics and Related Topics (Sundance 1985), Congr. Numer. 50205–218.Google Scholar
[13]Janson, S., Łuczak, T. and Rucinski, A. (2000) Random Graphs, Wiley–Interscience Series in Discrete Mathematics and Optimization, Wiley–Interscience, New York.CrossRefGoogle Scholar
[14]Kang, R. J. (2008) Improper colourings of graphs. PhD thesis, University of Oxford. ora.ouls.ox.ac.uk/objects/uuid:a93d8303-0eeb-4d01-9b77-364113b81a63.Google Scholar
[15]Kang, R. J. and McDiarmid, C. J. H. (2007) The t-improper chromatic number of random graphs. In Proc 4th European Conference on Combinatorics, Graph Theory and Applications (Seville 2007), Electron. Notes Discrete Math. 29419–425.Google Scholar
[16]Kang, R. J., Müller, T. and Sereni, J.-S. (2008) Improper colouring of (random) unit disk graphs. Discrete Math. 308 1438–1454.CrossRefGoogle Scholar
[17]Lovász, L. (1966) On decompositions of graphs. Studia Sci. Math. Hungar. 1 237–238.Google Scholar
[18]Łuczak, T. (1991) The chromatic number of random graphs. Combinatorica 11 45–54.CrossRefGoogle Scholar
[19]McDiarmid, C. (1998) Concentration. In Probabilistic Methods for Algorithmic Discrete Mathematics, Vol. 16 of Algorithms Combin., Springer, Berlin, pp. 195–248.CrossRefGoogle Scholar
[20]Matula, D. and Kučera, L. (1990) An expose-and-merge algorithm and the chromatic number of a random graph. In Random Graphs '87 (Poznań 1987), Wiley, Chichester, pp. 175–187.Google Scholar
[21]Scheinerman, E. R. (1992) Generalized chromatic numbers of random graphs. SIAM J. Discrete Math. 5 74–80.CrossRefGoogle Scholar
[22]Škrekovski, R. (1999) List improper colourings of planar graphs. Combin. Probab. Comput. 8 293–299.CrossRefGoogle Scholar