Book contents
- Frontmatter
- Contents
- Preface to the first edition
- Preface to the second edition
- 1 Graphs
- 2 Trees
- 3 Colorings of graphs and Ramsey's theorem
- 4 Turán's theorem and extremal graphs
- 5 Systems of distinct representatives
- 6 Dilworth's theorem and extremal set theory
- 7 Flows in networks
- 8 De Bruijn sequences
- 9 Two (0, 1, ⋆) problems: addressing for graphs and a hash-coding scheme
- 10 The principle of inclusion and exclusion; inversion formulae
- 11 Permanents
- 12 The Van der Waerden conjecture
- 13 Elementary counting; Stirling numbers
- 14 Recursions and generating functions
- 15 Partitions
- 16 (0, 1)-Matrices
- 17 Latin squares
- 18 Hadamard matrices, Reed–Muller codes
- 19 Designs
- 20 Codes and designs
- 21 Strongly regular graphs and partial geometries
- 22 Orthogonal Latin squares
- 23 Projective and combinatorial geometries
- 24 Gaussian numbers and q-analogues
- 25 Lattices and Möbius inversion
- 26 Combinatorial designs and projective geometries
- 27 Difference sets and automorphisms
- 28 Difference sets and the group ring
- 29 Codes and symmetric designs
- 30 Association schemes
- 31 (More) algebraic techniques in graph theory
- 32 Graph connectivity
- 33 Planarity and coloring
- 34 Whitney Duality
- 35 Embeddings of graphs on surfaces
- 36 Electrical networks and squared squares
- 37 Pólya theory of counting
- 38 Baranyai's theorem
- Appendix 1 Hints and comments on problems
- Appendix 2 Formal power series
- Name Index
- Subject Index
3 - Colorings of graphs and Ramsey's theorem
Published online by Cambridge University Press: 05 June 2012
- Frontmatter
- Contents
- Preface to the first edition
- Preface to the second edition
- 1 Graphs
- 2 Trees
- 3 Colorings of graphs and Ramsey's theorem
- 4 Turán's theorem and extremal graphs
- 5 Systems of distinct representatives
- 6 Dilworth's theorem and extremal set theory
- 7 Flows in networks
- 8 De Bruijn sequences
- 9 Two (0, 1, ⋆) problems: addressing for graphs and a hash-coding scheme
- 10 The principle of inclusion and exclusion; inversion formulae
- 11 Permanents
- 12 The Van der Waerden conjecture
- 13 Elementary counting; Stirling numbers
- 14 Recursions and generating functions
- 15 Partitions
- 16 (0, 1)-Matrices
- 17 Latin squares
- 18 Hadamard matrices, Reed–Muller codes
- 19 Designs
- 20 Codes and designs
- 21 Strongly regular graphs and partial geometries
- 22 Orthogonal Latin squares
- 23 Projective and combinatorial geometries
- 24 Gaussian numbers and q-analogues
- 25 Lattices and Möbius inversion
- 26 Combinatorial designs and projective geometries
- 27 Difference sets and automorphisms
- 28 Difference sets and the group ring
- 29 Codes and symmetric designs
- 30 Association schemes
- 31 (More) algebraic techniques in graph theory
- 32 Graph connectivity
- 33 Planarity and coloring
- 34 Whitney Duality
- 35 Embeddings of graphs on surfaces
- 36 Electrical networks and squared squares
- 37 Pólya theory of counting
- 38 Baranyai's theorem
- Appendix 1 Hints and comments on problems
- Appendix 2 Formal power series
- Name Index
- Subject Index
Summary
We shall first look at a few so-called coloring problems for graphs.
A proper coloring of a graph G is a function from the vertices to a set C of ‘colors’ (e.g. C = {1, 2, 3, 4}) such that the ends of every edge have distinct colors. (So a graph with a loop will admit no proper colorings.) If |C| = k, we say that G is k-colored.
The chromatic number χ(G) of a graph G is the minimal number of colors for which a proper coloring exists.
If χ(G) = 2 (or χ(G) = 1, which is the case when and only when G has no edges), then G is called bipartite. A graph with no odd polygons (equivalently, no closed paths of odd length) is bipartite as the reader should verify.
The famous ‘Four Color Theorem’ (K. Appel and W. Haken, 1977) states that if G is planar, then χ(G) ≤ 4.
Clearly χ(Kn) = n. If k is odd then χ(Pk) = 3. In the following theorem, we show that, with the exception of these examples, the chromatic number is at most equal to the maximum degree (R. L. Brooks, 1941).
Theorem 3.1.Let d ≥ 3 and let G be a graph in which all vertices have degree ≤ d and such that Kd+1 is not a subgraph of G. Then χ(G) ≤ d.
Proof 1: As is the case in many theorems in combinatorial analysis, one can prove the theorem by assuming that it is not true, then considering a minimal counterexample (in this case a graph with the minimal number of vertices) and arriving at a contradiction.
- Type
- Chapter
- Information
- A Course in Combinatorics , pp. 24 - 36Publisher: Cambridge University PressPrint publication year: 2001