Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

2002 | Buch

Colouring Preliminaries Kapitel lesen Erstes Kapitel lesen

Graph Colouring and the Probabilistic Method

verfasst von: Michael Molloy, Bruce Reed

Verlag: Springer Berlin Heidelberg

Buchreihe : Algorithms and Combinatorics

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

Over the past decade, many major advances have been made in the field of graph colouring via the probabilistic method. This monograph provides an accessible and unified treatment of these results, using tools such as the Lovasz Local Lemma and Talagrand's concentration inequality.
The topics covered include: Kahn's proofs that the Goldberg-Seymour and List Colouring Conjectures hold asymptotically; a proof that for some absolute constant C, every graph of maximum degree Delta has a Delta+C total colouring; Johansson's proof that a triangle free graph has a O(Delta over log Delta) colouring; algorithmic variants of the Local Lemma which permit the efficient construction of many optimal and near-optimal colourings.
This begins with a gentle introduction to the probabilistic method and will be useful to researchers and graduate students in graph theory, discrete mathematics, theoretical computer science and probability.

Inhaltsverzeichnis

Frontmatter

Preliminaries

Frontmatter
1. Colouring Preliminaries
Abstract
We will be discussing colouring the vertices and edges of graphs. A graph G is a set V = V (G) of vertices and a set E = E(G) of edges,each linking a pair of vertices, its endpoints (formally, an edge is an unordered pair of vertices and thus our graphs have no loops or multiple edges), which are adjacent. We assume the reader has a basic knowledge of graph theory. A k-colouring of the vertices of a graph G is an assignment of k colours (often the integers 1,..., k) to the vertices of G so that no two adjacent vertices get the same colour. The chromatic number of G, denoted χ(G), is the minimum k for which there is a k-colouring of the vertices of G. The set S j of vertices receiving colour j is a colour class and induces a graph with no edges, i.e. it is a stable set or independent set. So, a k-colouring of the vertices of G is simply a partition of V(G) into k stable sets and the chromatic number of G is the minimum number of stable sets into which the vertices of G can be partitioned.
Michael Molloy, Bruce Reed
2. Probabilistic Preliminaries
Abstract
We consider experiments which have only a finite number of possible outcomes. We call the set of all possible outcomes, the sample space and denote Ω. For example, our experiment may consist of rolling a six sided die and examining the top face, in which case Ω. = {1, 2, 3, 4, 5, 6}. Alternatively, our experiment may consist of flipping a coin three times in a row, then Ω = {HHH, HHT, HTH, THH, TTH, THT, HTT, TTT} where H stands for heads and T for tails. The reader probably has an intuitive notion of what an event is, which corresponds to this word’s use in everyday language. Formally, an event is a subset A of Ω. For example, we identify the event that the die roll is odd with the subset ({1, 3, 5}). Similarly, the event that the coin landed the same way up every time is the set ({HHH, TTT}).
Michael Molloy, Bruce Reed

Basic Probabilistic Tools

Frontmatter
3. The First Moment Method
Abstract
In this chapter, we introduce the First Moment Method1, which is the most fundamental tool of the probabilistic method. The essence of the first moment method can be summarized in this simple and surprisingly powerful statement:
Michael Molloy, Bruce Reed
4. The Lovász Local Lemma
Abstract
In this chapter, we introduce one of the most powerful tools of the probabilistic method: The Lovász Local Lemma. We present the Local Lemma by reconsidering the problem of 2-colouring a hypergraph.
Michael Molloy, Bruce Reed
5. The Chernoff Bound
Abstract
The First Moment Principle states that a random variable X is at most E(X) with positive probability. Often we require that X is near E(X) with very high probability. When this is the case, we say that X is concentrated. In this book, we will see a number of tools for proving that a random variable is concentrated, including Talagrand’s Inequality and Azuma’s Inequality. In this chapter, we begin with the simplest such tool, the Chernoff Bound.
Michael Molloy, Bruce Reed

Vertex Partitions

Frontmatter
6. Hadwiger’s Conjecture
Abstract
Kostochka [98] and Thomason [149] have shown that if G has a K k -minor.
Michael Molloy, Bruce Reed
7. A First Glimpse of Total Colouring
Abstract
In Part II, we introduced three probabilistic tools and saw an application of each of them. In the last chapter, we saw a more complicated application of one of them, the First Moment Method. In this chapter, we will illustrate the power of combining the other two, the Local Lemma and the Chernoff Bound, by discussing their application to total colouring.
Michael Molloy, Bruce Reed
8. The Strong Chromatic Number
Abstract
Consider a graph G on kr vertices. We say that G is strongly r-colourable if for any partition of V (G) into parts V 1,..., V k, each of size r, G has a r-colouring such that every colour class contains exactly one vertex from each part (and so every part contains exactly one vertex of each colour). Equivalently, G is strongly r-colourable if for any graph G′ which is the union of k disjoint r-cliques on the same vertex set, χ(G U G) = r. A well-known conjecture of Erdős, recently proven by Fleischner and Steibitz [58], states that the union of a Hamilton cycle on 3n vertices and n vertex disjoint triangles on the same vertex set has chromatic number 3. In other words, C 3 n is strongly 3-colourable. Strongly r-colourable graphs are of interest partially because of their relationship to this problem, and also because they have other applications (see for example, Exercise 8.1).
Michael Molloy, Bruce Reed
9. Total Colouring Revisited
Abstract
In Chap. 7, we constructed total colourings by first choosing an edge colouring and then choosing a vertex colouring which didn’t significantly conflict with it. We then obtained a total colouring by modifying the edge colouring so as to eliminate the conflicts. In this chapter, we take the opposite approach, first choosing a vertex colouring and then choosing an edge colouring which does not conflict at all with the vertex colouring, thereby obtaining a total colouring.
Michael Molloy, Bruce Reed

A Naive Colouring Procedure

Frontmatter
10. Talagrand’s Inequality and Colouring Sparse Graphs
Abstract
In Chap. 5 we saw the Chernoff Bound, our first example of a concentration bound. Typically, this bound is used to show that a random variable is very close to its expected value with high probability. Such tools are extremely valuable to users of the probabilistic method as they allow us to show that with high probability, a random experiment behaves approximately as we “expect” it to.
Michael Molloy, Bruce Reed
11. Azuma’s Inequality and a Strengthening of Brooks’ Theorem
Abstract
In this chapter, we introduce a new tool for proving bounds on concentration. It differs from the tools we have mentioned so far, in that it can be applied to a sequence of dependent trials. To see a concrete example of such a situation, imagine that we are colouring the vertices of a graph one by one, assigning to each vertex a colour chosen uniformly from those not yet assigned to any of its coloured neighbours. This ensures that the colouring obtained is indeed a proper colouring, and analyzing such a random process may yield good bounds on the minimum number of colours required to obtain vertex colourings with certain properties. However, our choices at each vertex are now no longer independent of those made at the other vertices.
Michael Molloy, Bruce Reed

An Iterative Approach

Frontmatter
12. Graphs with Girth at Least Five
Abstract
In Chap. 10, we saw that the chromatic number of a triangle-free graph with maximum degree Δ (sufficiently large) is at most
Michael Molloy, Bruce Reed
13. Triangle-Free Graphs
Abstract
In Chap. 12 we proved that graphs with girth at least 5, i.e. graphs with no triangles or 4-cycles, have chromatic number at most In this chapter, we will present Johansson’s stronger result [86] that the same bound holds even for triangle-free graphs.
Michael Molloy, Bruce Reed
14. The List Colouring Conjecture
Abstract
In this chapter we present a second application of an iterative variant of the Naive Colouring Procedure: Kahn’s proof that the List Colouring Conjecture is asymptotically correct, i.e. that for any graph G of maximum degree Δ, X ℓ ′ (G) = Δ + o(Δ) [89].
Michael Molloy, Bruce Reed

A Structural Decomposition

Frontmatter
15. The Structural Decomposition
Abstract
In this chapter we will obtain a decomposition theorem for general graphs similar to that obtained in Chap. 11 for minimal counterexamples to the Beutelspacher-Hering Conjecture. That is, we will partition V (G) into sets D1,..., D ι and S where the D i are “dense clique-like” sets and all the vertices in S are sparse.
Michael Molloy, Bruce Reed
16. ω, Δ and χ
Abstract
In this chapter, we continue our analysis of the relationship between ω, Δ, and χ. To do so, we need to modify our naive colouring procedure so as to take advantage of the decomposition result described in the last chapter. The analysis of this variant of the Naive Colouring Procedure requires a strengthening of Talagrand’s Inequality obtained by McDiarmid.
Michael Molloy, Bruce Reed
17. Near Optimal Total Colouring I: Sparse Graphs
Abstract
In the next two chapters, we present the main result of [119]:
  • Theorem 17.1 There exists an absolute constant C such that every graph with maximum degree ∈ has total chromatic number at most ∈ + C.
Michael Molloy, Bruce Reed
18. Near Optimal Total Colouring II: General Graphs
Abstract
In the previous chapter, we proved that for any constant ∈ > 0, graphs in which every vertex is ∈Δ-sparse have a Δ + C(∈) total colouring. In this chapter, we will show how to modify that proof to handle graphs that include dense vertices, thereby proving Theorem 17.1. To do so, we make use of the decomposition from Chap. 15.
Michael Molloy, Bruce Reed

Sharpening our Tools

Frontmatter
19. Generalizations of the Local Lemma
Abstract
As we have seen, the Local Lemma allows us to use a local analysis to obtain a global result. From this perspective, a drawback of the version presented in Chap. 4 is that it requires global bounds p and d. These global bounds can make it difficult to apply the Local Lemma if, for example, the probabilities of the bad events vary widely. In this chapter we will discuss a few useful generalizations of the Local Lemma, each of which incorporates varying probabilities of the bad events.
Michael Molloy, Bruce Reed
20. A Closer Look at Talagrand’s Inequality
Abstract
When presenting Talagrand’s Inequality in Chap. 10, we sacrificed power for simplicity. The original inequality provided by Talagrand is much more general than those we stated, but it is somewhat unwieldy. In this chapter, we will see Talagrand’s original inequality, and we will show how to derive from it the weaker inequalities of Chap. 10. In order to give the reader a better idea of how the full inequality can be used, we will present a few other weakenings that can be derived from it, each one a generalization of those that we already know.
Michael Molloy, Bruce Reed

Colour Assignment via Fractional Colouring

Frontmatter
21. Finding Fractional Colourings and Large Stable Sets
Abstract
In this preliminary chapter, we introduce the notion of a fractional colouring. We then present some results on finding large stable sets and fractional colourings of certain special graphs. These results give some of the flavour of the approach taken in the remainder of this part of the book. Although the approach described in the next two chapters is similar, the technical complications will increase dramatically.
Michael Molloy, Bruce Reed
22. Hard-Core Distributions on Matchings
Abstract
In the preceding chapter, we analyzed two distributions on stable sets. In the first, each stable set was equally likely. In the second, each maximum stable set was equally likely. Our analyses allowed us to find large stable sets and fractional colourings using few colours. In both cases, the analysis involved showing that certain properties held in the neighbourhood of a vertex, regardless of what the stable set looked like further away from the vertex. This makes these two distributions attractive candidates for use in conjunction with the Local Lemma, for their local analysis leads to global results.
Michael Molloy, Bruce Reed
23. The Asymptotics of Edge Colouring Multigraphs
Abstract
As we mentioned in Chap. 1, one of the most celebrated conjectures concerning edge colouring is the Goldberg-Seymour Conjecture which states that for any multigraph G: χe , (G) ≤ max(Δ + 1, ⌈χ e * (G)⌉).
Michael Molloy, Bruce Reed

Algorithmic Aspects

Frontmatter
24. The Method of Conditional Expectations
Abstract
Throughout this chapter, we consider hypergraphs for which the expected number of monochromatic edges in a uniformly random 2-colouring is less than one. To begin, we present an efficient algorithm, due to Erdős and Selfridge [46] for finding proper 2-colourings of such hypergraphs.
Michael Molloy, Bruce Reed
25. Algorithmic Aspects of the Local Lemma
Abstract
In this chapter, we discuss finding proper 2-colourings of hypergraphs where each edge intersects a bounded number of other edges.
Michael Molloy, Bruce Reed
Backmatter
Metadaten
Titel
Graph Colouring and the Probabilistic Method
verfasst von
Michael Molloy
Bruce Reed
Copyright-Jahr
2002
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-04016-0
Print ISBN
978-3-642-04015-3
DOI
https://doi.org/10.1007/978-3-642-04016-0