• Let $G$ = $(V,E)$ be a graph and $C$ a set of “colors”

• $G$ is $k$-colorable $\Rightarrow$ $G$ is $\ell$-colorable for any $\ell$ $\ge$ $k$.

• Chromatic number (kormatično število) of $G$:

  $\chi (G)$ = min$\{$k : $G$ is $k$-vertex-colorable$\}$

• $\chi$ $(K_n) = n$.
• $\chi$ $(C_{2n}) = 2$
• $\chi$ $(C_{2n+1}) = 3$.
• If $H$ $\le$ $G$, then $\chi$ $(H)$ $\le$ $\chi$ $(G)$.

• Clearly, $\chi (G) = 1$ if and only if $G$ $\cong$ $K^C_n$.

PROOF: ... think of color classes as bipartition sets ...

• We know that graphs with $\chi \le 2$ cannot have cycles of odd length We will now show that the converse holds as well:

• PROOF. WLOG: $G$ is connected.

• Choose $v$ $\in$ $V (G)$. For $u \in V(G)$ let:

  • $c(u)$ = "blue" if $d(v,u)$ is even;
  • $c(u)$ = "red" if $d(v,u)$ is odd.
• If this is not a proper coloring, then there are two adjacent vertices $x, y$ that are both at even or both at odd distance from $v$.
• Find shortest paths $P_x$, $P_y$ from $v$ to $x$ and to $y$. Then $P_x(xy)P^{−1}_y$ is a closed walk of odd length.

• To complete the proof, we need to show the following:
• Exercise.: If a graph contains a closed walk of odd length, then it also contains a cycle of odd length.

This proves the following characterization of bipartite graphs.

• Since $\chi(K_n)$ = $n$, it follows that $\chi(G)\ge$ $\omega(G)$.

• WLOG: $G$ is connected.

• We already know that $\omega$ $(G)$ $\le$ $\chi$ $(G)$. So we need to show two things:

  • $\chi$ $(G) \le (G)+1$.
  • If $G$ $\not{\cong}$ $K_n$ or $C_{2m+1}$, then $\chi (G) \le \Delta (G)$.

• Finding a $(\Delta+1)$-coloring is easy:

  • Let ${1,...,\Delta+1}$ be the set of colors. Order the vertices of $G$ in some linear order. Color the first vertex with color $1$.
  • Suppose that we have already colored the first $m$ vertices. Let $v$ be the next vertex, and let $c \in {1,...,\Delta+1}$ be the smallest integer that does not appear as a color of some neighbor of $v$. Color v with the color $c$.
  • Repeat this procedure until all vertices are colored.

• In the rest of the proof, we may assume that $G \not{\cong} K_n$ or $C_{2m+1}$. It remains to show, that we may change the $(\Delta+1)$-coloring in such a way that one of the colors “disappears”.
• For the rest of the proof: $\Delta+1$ = “green”.
• Let $S$ = “the set of green vertices”.
• If there is $v \in S$ such that one of the non-green colors does not appear among its neighbors, then we may use this color for $v$. Apply this throughout $S$. This procedure is called “killing unessential greens”.

• After unessential greens are “killed”, we get a $(\Delta+1)$-coloring in which each green vertex $v$ has valence $\Delta$, and no two neighbors of $v$ are of the same color.

The second procedure allow us to “push” the green color from any $v \in S$ to any other $x \in V(G)$ along any path $P$ from $v$ to $x$.

• Kill unessential $(\Delta+1)$s. If $S = \emptyset$ or $S ={x}$, then stop.
• Let $u$ be the first vertex on the path from $v$ to $x$. Let $c$ be the color of $u$. Since we killed unessential greens, no green neighbours of $u$ have any other neighbours of color $c$.

• Change the color of green neighbors of $u$ to $c$, and change the color of $u$ to green.

• Go to step 1 with $u$ in place of $v$, and with $P$ being the part of old $P$ from $u$ to $x$

This procedure changed the color of some old green vertices, and cyclically rotated the colors along $P$.

• Let $x$ be a vertex of smallest valence. For each green $v$, choose a shortest path from $v$ to $x$, and push the green color to $x$. Now $x$ is the only green vertex.
• If $val(x) < \Delta$, then there is a non-green color which does not appear among neighbors of $x$. Hence we can kill the green color at $x$, and finish.
• It follows: We may thus assume that $G$ is regular (all vertices have valence $\Delta$).

• The proof now splits into two cases:

  • $G$ is $3$-connected;
  • $G$ is not $3$-connected.

• Suppose $G$ is $3$-connected.
• Since $G$ is not complete, there exist $x \not{\sim} y$. Push the green color from all green vertices to $x$.
• Since there in no green color in $N(y)$, there exist $u,v \in N(y)$ of the same color.

• Consider the graph $G' = G − u − v$. Since $G$ is $3$-connected, $G'$ is connected. Choose a shortest path from $x$ to $y$ in $G'$ and push the green color from $x$ to $y$ along this path.

• This results in a proper coloring of $G$ where the only green vertex is $y$, where $u$ and $v$ (two neighbors of $y$) have the same color. Therefore, the green color of $y$ can be “killed”, giving a $\Delta$-coloring of $G$.

• Suppose now that $G$ is not $3$-connected.
• The rest of the proof of is by induction on $n =|V(G)|$. By inspection, we see that the theorem holds for $n \le 4$. Assume now that $n \ge 5$ and that theorem holds for all graphs with less than $n$ vertices.
• If $\Delta (G) = 1$, then $G \cong K^C_n$ , and so $\chi(G) = 1$.
• If $\Delta (G) = 2$, then $G \cong C_n$ or $P_n$, and the theorem holds.
• Assume henceforth that $\Delta(G)\ge 3$.

• Suppose that $G$ has a cut-vertex $\{v\}$, and let $X_1,...,X_m$ be the components of $G − v$.

• By induction, each $X_i + v$ is $\Delta(G)$-colorable. By renaming colors in each $X_i$ if necessary, we may assume that in all $X_i$, the vertex $v$ has the same color. This gives a $\Delta(G)$-coloring of $G$.

• Suppose now that $G$ has a vertex-cut of size two:$\{x,y\}$.

• In a similar way as in case $\kappa = 1$ we may use induction to show that $G$ is $\Delta$-colorable.
• Homework H2: Finish the proof of the theorem in this case.

• Let $G$ be a graph on $n$ vertices with at least one edge. Construct a new graph $G^{+}$ on $2n+1$ vertices in the following way:
• $V(G^{+}) = V(G) \cup \{v':v \in V(G)\} \cup \{\infty\}$ (a disjoint union).
• $E(G^{+}) = E(G) \cup \{v'u:vu \in E(G)\} \cup \{v' \infty:v \in V(G)\}$.
• Homework H3: Show that $\chi (G^{+}) = \chi(G)+1$.
• Example: The graph, obtained in this way from $C_5$ is called the $Gr\ddot{o}tch$ $graph$.

• Let $G = (V,E)$ be a graph and $C$ a set of “colors”. We define edge-colorings in a similar way as vertex-colorings:

• The minimal integer $k$ for which $G$ is $k$-edge-colorable is called the chromatic index (kormatični indeks) of $G$.

• Note that $\chi'(G) = \chi(L(G))$.

• There is an obvious natural lower bound: $\chi' (G) \ge \Delta (G)$.
• The upper bound is given by Vizing’s theorem.

• We skip the proof.

• Graphs with $\chi'(G) = \Delta(G)$ are graphs of class 1, the others are of class 2.
• $C_{2m}$ is of class $1$, $C_{2m+1}$ is of class $2$.
• Hypercubes are of class $1$
• The Petersen graph is of class $2$.
• In general, determining $\chi'$ is difficult.
• For some graphs, this task is easier. For example, bipartite graphs.

• By contradiction: Let $k$ be a positive integer. Among all graphs with $\Delta = k$ choose a counterexample with the least number of edges.

• Choose an edge $e =xy$, such that $\Delta(G − e) = \Delta(G)$ (What if such and edge does not exist?).

• By hypothesis, $\chi'(G − e) = \Delta(G − e) = k$. Color the edges with $k$ colors.

• There is a color $\alpha$, which does not appear at $x$, and a color $\beta$, which does not appear at $y$.

• If $\alpha = \beta$, color $e$ with $\alpha$.

• Assume now that $\alpha \ne \beta$.
• Consider the subgraph $H$ induced by the edges of colors $\alpha$ and $\beta$. Clearly $\Delta(H) \le 2$, so the connected components of $H$ are paths or cycles.

• Note that swappings colors $\alpha$ and $\beta$ in any component of $H$ gives a different proper coloring.
• Since all paths from $x$ to $y$ are of odd length ($G$ is bipartite!), $x$ and $y$ are in different components of $H$. Swap the colors $\alpha$ and $\beta$ in a component containing $x$.

• Finally, color $e$ with $\beta$.

• A regular graph of valence $3$ is called cubic graph (kubičen graf).

• Homework H3: Show that every connected cubic graph with $\chi' = 3$ is $2$-edge-connected.

• On the other hand, it is not easy to find $2$-edge-connected cubic graphs with $\chi' = 4$.

• Such a graph is called a snark. (The name comes from a poem “The hunting of the Snark” by Lewis Carol.)

• The smallest such graph is the Petersen graph.

• Constructing new families of snarks is still a difficult task.

• Consider a proper edge-coloring of $G$. Consider the set $M$ of edges colored with a fixed color. No vertex of $G$ is incident with more than one edge from $M$.

• Vertices, that are incident with some $e \in M$ are saturated (nasičen).

• If every vertex of $G$ is saturated, then the matching is perfect (popolno prirejanje).

• A matching is maximal if it is the largest among all matching.

• Maximal matchings are related to “stable sets”, “vertex covers” and “edge covers”

• $\nu (G)$ := “the size of a maximal matching $G$”;
• $\alpha (G)$ := “the size of a largest stable set $G$”;
• $\tau (G)$ := “the size of a smallest vertex cover of $G$”;
• $\rho (G)$ := “the size of a smallest edge cover of $G$”.

We skip the proofs.

• It is often difficult to decide, what is the size of a largest matching. For bipartite graphs, we have the following nice result:

• Here $N(S)$ is the set of vertices that are adjacent to some vertex in $S$.

• PROOF. One direction is obvious.
• For the other direction, we need the $K\ddot{o}nig-Egervary$ theorem. Suppose that there is no matching in which every $v \in X$ is saturated. Then $\nu (G) < |X|$.
• By the $K\ddot{o}nig-Egervary$ theorem, $\nu (G) = \tau (G)$. Therefore, there is a vertex cover $K$ with $|K| < |X|$.
• Let $S =X \setminus K$. Then $N(S)\subseteq Y \cap K$, and so

H1 Finish the proof of the Brooks theorem in the case where the vertex-connectivity of the graph is $2$.

H2 Show that $\chi(G^{+}) = \chi(G)+1$.

H3 Show that every connected cubic graph with $\chi' = 3$ is $2$-edge-connected.