FoldUnfold Table of Contents Ramsey Numbers Ramsey Numbers Definition: The Ramsey Number, $R(s,t)$ is the least positive integer $n$ such that for any edge $2$-colouring of $E(K_n)$, there exists either a $K_s$ or a $K_t$ with a monochromatic colouring. For example, the Ramsey number $R(3, 3) = 6$. We can prove this by seeing if $R(3, 3) \leq 6$. First, suppose that $R(3, … [Read more...]

## Graph Matchings

FoldUnfold Table of Contents Graph Matchings Graph Matchings Definition: For a graph $G = (V(G), E(G))$, a Matching is a subset $M \subset E(G)$ where no two edges in $M$ share a vertex. For example, suppose that we have a graph $G$ where $E(G) = \{ \{a, b\}, \{a, c\}, \{a, d \}, \{b, c \}, \{c, d \}, \{c, e \}, \{e , f \}$ we know that if $M = \{ \{ a, b \}, \{c, d \}, … [Read more...]

## Vizing’s Theorem

FoldUnfold Table of Contents Vizing's Theorem Vizing's Theorem Theorem 1 (Vizing's Theorem): For any (simple) graph $G$ where $\chi ' (G)$ is the smallest integer $k$ for a good edge $k$-colouring and $\Delta (G)$ is the maximum degree in $G$, then $\Delta (G) \leq \chi ' (G) \leq \Delta (G) + 1$. We will not prove this theorem, however this tells us that for any simple … [Read more...]

## Edge Colouring and Chromatic Indexes

FoldUnfold Table of Contents Edge Colouring and Chromatic Indexes Edge Colouring and Chromatic Indexes We have already looked at Vertex Colouring and Chromatic Numbers, and now we are going to examine edge colouring and the analogous chromatic index. Suppose that we wanted to colour the edges of a graph such that no vertex contains two edges of the same colour. Of course, … [Read more...]

## Bounds for X(G)

FoldUnfold Table of Contents Bounds for X(G) Upper / Lower Bounds for X(G) Bounds for X(G) We are now going to look at some possible bounds for determining the chromatic number of a graph. For very large graphs, determining the chromatic number is often very difficult. These upper and lower bounds are often very important in determining $\chi$ for a graph $G$, since we can … [Read more...]