Add sections on cliques, choosability to graph digest

1 files changed, 40 insertions, 0 deletions

diff --git a/content/graph_theory.tex b/content/graph_theory.tex
index 569bbd2..7349666 100644
--- a/content/graph_theory.tex
+++ b/content/graph_theory.tex
@@ -28,6 +28,14 @@ $\Delta(G)$ is the maximum degree in $G$.
 
 $G$ is $k$-regular $\iff \forall v \in V(G) : d(v) = k$
 
+\subsection*{Induced Subgraphs}
+
+Subgraph $H \subset G$ is \emph{induced} if:
+
+$\forall u, v \in V(H) : uv \in E(H) \iff uv \in E(G)$
+
+i.e. every induced subgraph may be generated by deleting vertices and their incident edges from $G$.
+
 \subsection*{Handshake Lemma}
 
 $$2|E| = \sum_{v \in V} d(v)$$
@@ -145,14 +153,46 @@ For graph $G$ the following is equivalent:
 	\item $K_5$, $K_{3,3}$ aren't topological minors of $G$
 \end{enumerate}
 
+
 \section*{Colorings}
 
+\vspace*{-4mm}
+\begin{align*}
+\chi(G) :&= \min_{k \in \N} : G \text{ has proper $k$-vertex coloring} \\
+\chi'(G) :&= \min_{k \in \N} : G \text{ has proper $k$-edge coloring}
+\end{align*}
+
+$k$-regular bipartite $G$ has proper $k$-edge-coloring.
+
+\subsection*{Cliques}
+
+A \emph{clique} is a subgraph of $G$ that is a complete graph.
+The \emph{clique number} $\omega(G)$ is the maximum order of a clique in $G$.
+
+\spacing
+
+$G$ is \emph{perfect} if $\forall$ induced $H \subseteq G : \chi(H) = \omega(H)$.
+
+Bipartite graphs are perfect with $\chi = \omega = 2$.
+
 \subsection*{$5$-Color Theorem}
 
 Every planar graph is $5$-colorable.
 
 \subsection*{List coloring}
 
+$\forall v \in V(G)$ let $L(v) \subseteq \N$ be a list of colors.
+
+$G$ is \emph{$L$-list-colorable} if $\exists$ a proper coloring $c$ s.t. $\forall v \in V(G) : c(v) \in L(v)$.
+
+\spacing
+
+$G$ is \emph{$k$-list-colorable} or \emph{$k$-choosable} if it is $L$-list-colorable for all lists of $k$ colors.
+
+\subsubsection*{Choosability}
+
+\emph{Choosability} $ch(G) := \min_{k\in\N}\{ G$ is $k$-choosable$\}$
+
 \subsubsection*{Thomassen's $5$-List-Color Theorem}
 
 Every planar graph is $5$-choosable.