aboutsummaryrefslogtreecommitdiff
path: root/content
diff options
context:
space:
mode:
authorAdrian Kummerlaender2018-02-10 23:00:52 +0100
committerAdrian Kummerlaender2018-02-10 23:00:52 +0100
commitf0589d7ffe3d8e6b2217426b0650c7ec39bf2702 (patch)
treeab7a28f7726fc6f10687e07197a172d2aecfa99f /content
parentbdf1860017d71ad4d531e4b140d3fd2935c038ca (diff)
downloadmath_reference_sheets-f0589d7ffe3d8e6b2217426b0650c7ec39bf2702.tar
math_reference_sheets-f0589d7ffe3d8e6b2217426b0650c7ec39bf2702.tar.gz
math_reference_sheets-f0589d7ffe3d8e6b2217426b0650c7ec39bf2702.tar.bz2
math_reference_sheets-f0589d7ffe3d8e6b2217426b0650c7ec39bf2702.tar.lz
math_reference_sheets-f0589d7ffe3d8e6b2217426b0650c7ec39bf2702.tar.xz
math_reference_sheets-f0589d7ffe3d8e6b2217426b0650c7ec39bf2702.tar.zst
math_reference_sheets-f0589d7ffe3d8e6b2217426b0650c7ec39bf2702.zip
Add sections on cliques, choosability to graph digest
Diffstat (limited to 'content')
-rw-r--r--content/graph_theory.tex40
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.