Skip to main content
Contents Index Dark Mode Prev Up Next \( {\labelitemi}{$\diamond$}
\def\arraystretch{1.5}
\newcommand{\contentsfinish}{}
\newcommand{\separator}{\begin{center}\rule{\columnwidth}{\arrayrulewidth}\end{center}}
\newcommand{\tosay}[1]{\begin{center}\text{\fbox{\scriptsize{#1}}}\end{center}}
\renewcommand{\cftsecfont}{}
\renewcommand{\cftsecpagefont}{}
\renewcommand{\descriptionlabel}[1]{\hspace{\labelsep}\smallcaps{#1}}
\def\oldequation{\equation}
\def\endoldequation{\endequation}
\newcommand{\nl}{
}
\newcommand{\runin}[1]{\textls[50]{\otherscshape #1}}
\renewcommand{\sectionmark}[1]{}
\renewcommand{\subsectionmark}[1]{}
\renewcommand{\sectionmark}[1]{\markboth{{\thesection}.\ \smallcaps{#1}}{\thesection.\ \smallcaps{#1}}}
\renewcommand{\subsectionmark}[1]{}
\renewcommand{\sectionmark}[1]{\markboth{{\scriptsize\thesection}.\ \smallcaps{#1}}{}}
\renewcommand{\subsectionmark}[1]{}
\newcommand{\makedefaultsection}[2][true]{
}
\newcommand{\timestamp}{{\color{red}Last updated: {\currenttime\ (UTC), \today}}}
\renewcommand{\le}{\leqslant}
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\renewcommand{\ge}{\geqslant}
\newcommand{\ideal}[1]{\left\langle\, #1 \,\right\rangle}
\newcommand{\subgp}[1]{\left\langle\, #1 \,\right\rangle}
\def\p{\varphi}
\def\isomorphic{\cong}
\def\imp{\to}
\def\iff{\leftrightarrow}
\def\Gal{\text{Gal}}
\def\im{\text{im}}
\def\ran{\text{ran}}
\def\normal{\vartriangleleft}
\renewcommand{\qedsymbol}{$\checkmark$}
\def\lcm{{\text{lcm}\,}}
\newcommand{\q}[1]{{\color{red} {#1}}}
\newcommand{\startimportant}[1]{\end{[{Hint:} #1]\end}}
\renewcommand{\textcircled}[1]{\tikz[baseline=(char.base)]{\node[shape=circle,draw,inner sep=2pt,color=red] (char) {#1};}}
\newcommand{\crossout}[1]{\tikz[baseline=(char.base)]{\node[mynode, cross out,draw] (char) {#1};}}
\newcommand{\set}[1]{\left\{ {#1} \right\}}
\newcommand{\setof}[2]{{\left\{#1\,|\,#2\right\}}}
\def\C{{\mathbb C}}
\def\Z{{\mathbb Z}}
\def\bF{{\mathbb F}}
\def\Q{{\mathbb Q}}
\def\N{{\mathbb N}}
\def\U{{\mathcal U}}
\def\pow{{\mathcal P}}
\def\R{{\mathbb R}}
\newcommand{\h}[1]{{\textbf{#1}}}
\def\presnotes{}
\renewcommand{\d}{\displaystyle}
\newcommand{\N}{\mathbb N}
\newcommand{\B}{\mathbf B}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Q}{\mathbb Q}
\newcommand{\R}{\mathbb R}
\newcommand{\C}{\mathbb C}
\newcommand{\U}{\mathcal U}
\newcommand{\pow}{\mathcal P}
\newcommand{\inv}{^{-1}}
\newcommand{\st}{:}
\renewcommand{\iff}{\leftrightarrow}
\newcommand{\Iff}{\Leftrightarrow}
\newcommand{\imp}{\rightarrow}
\newcommand{\Imp}{\Rightarrow}
\newcommand{\isom}{\cong}
\renewcommand{\bar}{\overline}
\newcommand{\card}[1]{\left| #1 \right|}
\newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}}
\newcommand{\vtx}[2]{node[fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2]{}}
\newcommand{\va}[1]{\vtx{above}{#1}}
\newcommand{\vb}[1]{\vtx{below}{#1}}
\newcommand{\vr}[1]{\vtx{right}{#1}}
\newcommand{\vl}[1]{\vtx{left}{#1}}
\renewcommand{\v}{\vtx{above}{}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Worksheet 6.2.1 Worksheet
Guiding Questions. Today, we’ll seek to answer the questions:
Subsection 6.2.1.1 Vertex Coloring
In this section, we consider the problem of coloring a graph. We begin with an exploration.
Problem 6.2.1 .
In your work as a cartographer, you’ve made many maps. In order to make your maps comprehensible, you prefer to give adjacent states different colors. How many colors are
required to color the map in
Figure 6.2.2 so that adjacent states are colored differently?
Figure 6.2.2. A hypothetical map (source ). One of the interesting problems in graph theory is the problem of
vertex coloring . In a
proper vertex coloring, each vertex is assigned a color so that adjacent vertices are given different colors. We make this precise using the notion of function in
Definition 6.2.3 .
Definition 6.2.3 .
Let
\(G = (V,E)\) be a graph,
\(V = \set{v_1, v_2, \ldots, v_n}\text{,}\) and
\(C = \set{c_1, c_2, \ldots, c_k}\) a set of labels called
colors . A
proper vertex coloring is a function
\(c : V\to C\) such that if
\(\set{v_i, v_j}\in E\text{,}\) \(c(v_i)\ne c(v_j)\text{.}\)
The
chromatic number of
\(G\text{,}\) denoted
\(\chi(G)\text{,}\) is the cardinality of the smallest set of colors
\(C\) for which there is a proper coloring for the vertices of
\(G\text{.}\)
Question 6.2.5 .
Activity 6.2.6 .
Calculate the chromatic numbers of the graphs below. Be ready to justify your answers.
Figure 6.2.7. A graph.
Figure 6.2.8. A graph.
Figure 6.2.9. A graph. Let’s explore some properties of vertex coloring.
Theorem 6.2.10 .
Let
\(G\) be a graph with
\(n\) vertices. Then
\(\chi(G) \le n\text{.}\)
Theorem 6.2.11 .
Let
\(G\) be a graph. Then
\(\chi(G) \ge \omega(G)\text{.}\)
Problem 6.2.12 .
Problem 6.2.13 .
Provide examples of graphs
\(G_1\) and
\(G_2\) that demonstrate that we may have
\(\chi(G_1) \lt n\) and that
\(\chi(G_2) \gt \omega(G_2)\text{.}\)
Theorem 6.2.14 .
Let
\(G\) be a graph with largest degree of a vertex
\(\Delta(G)\text{.}\) Then
\(\chi(G) \le \Delta(G) + 1\text{.}\)
Hint .
Induction on the number of vertices.
