thesis.tex

\documentclass[a4paper, 12pt]{article}
% Nyelvi beállítások
%\def\magyarOptions{defaults=hu-min}
\usepackage[english]{babel}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage[varg]{txfonts}
\usepackage[lite,subscriptcorrection,slantedGreek,nofontinfo]{mtpro2} % Thanks: https://cims.nyu.edu/~fennell/mtpro2/
\usepackage{graphics}
\usepackage{tikz}
\usepackage{t1enc}
\usepackage{physics}
\usepackage{appendix}
\usepackage[nottoc,numbib]{tocbibind}
\usepackage{geometry}
\usepackage[]{algorithm2e}
\usepackage{tikz}
\usepackage{enumerate}
\usetikzlibrary{positioning,chains,fit,shapes,calc}
 
% Sorköz és teljes oldalas kitöltés
\linespread{1.3}
\usepackage{fullpage}

% Hiperlinkek
\usepackage[pdfauthor={},pdftitle={}]{hyperref}
\hypersetup{colorlinks=true, linkcolor=blue, citecolor=red, filecolor=magenta, 
            urlcolor=cyan, linktocpage=true}

% Sorszámozás            
%\renewcommand{\thesection}{\thechapter.\arabic{section}}
%\numberwithin{equation}{section}


% Tételek, definíciók
%\swapnumbers
\newtheorem{lem}{Lemma}[section]
\newtheorem{theo}[lem]{Theorem}
\newtheorem{state}[lem]{Proposition}
\newtheorem{defin}[lem]{Definition}
\newtheorem{note}[lem]{Note}
\newtheorem{example}[lem]{Example}
\newtheorem{corollary}[lem]{Corollary}
\newtheorem{remark}[lem]{Remark}

% Megjegyzésekhez, amik nem szerepelnek majd végül a pdf-ben
\newcommand{\ignore}[1]{}

% Speciális jelölések
\newcommand{\simp}{\mathop{\mathrm{Simp}}}
\newcommand{\graph}{\mathop{\mathrm{graph}}}
\newcommand{\dom}{\mathop{\mathrm{dom}}}
\newcommand{\adj}{\mathop{\mathrm{adj}}}
\DeclareMathOperator*{\ch}{ch}

% Tartalomjegyzék mélysége
\setcounter{tocdepth}{4}
%\renewcommand{\bibliofont}{\normalsize}
\addto\captionsenglish{\renewcommand{\refname}{Bibliography}}

% másik qed: ezt használom azokra a tételekre, amiket nem fogok bizonyítani
\newcommand*{\qedb}{\hfill\ensuremath{\blacksquare}}

% https://tex.stackexchange.com/questions/82271/multiple-algorithm2e-algorithms-in-two-column-documents
\makeatletter
\newcommand{\removelatexerror}{\let\@latex@error\@gobble}
\makeatother


% Irodalomjegyzék
\usepackage[backend=bibtex,
backref=true,
style=alphabetic,
citestyle=alphabetic]{biblatex}
\addbibresource{references}

\begin{document}
\thispagestyle{empty}
\newgeometry{
    top=2.5cm,
    bottom=2.5cm,
    outer=2.5cm,
    inner=2.5cm,
}
% Kezdőlap
\begin{center}\renewcommand\baselinestretch{0.9}
{\Large \textsc{KTH Royal Institute of Technology}\\\textsc{EIT Digital Master School}\\} \hrulefill
\vspace{1.0cm} {\huge \\ Benjámin Martin Seregi \\} \vspace{1cm}
{\Huge\textsc{On the list coloring of $k$-band buffering cellular graphs}\\ \vspace{0.5cm}}
{\large\textsc MSc Thesis \\ Degree Project in Electrical Engineering}\\ \vspace{1cm}
{\large \textit{Examiner}\\
\vspace{0.2cm}
Marina Petrova\vspace{1.2cm}}\\
{\large \textit{Supervisors}\\
\vspace{0.2cm}
Dávid Kunszenti-Kovács and Göran Andersson\vspace{1.2cm}}\\
\begin{figure}[!h]
\begin{center}
\resizebox{5.5cm}{!}
{\includegraphics{KTH_Logotyp_RGB_2013}}
\end{center}
\end{figure}
{\large  School of Information and Communication Technology \\ \vspace{0.5cm}
Stockholm, Sweden\\2018}
\end{center}

\pagebreak
\pagenumbering{Roman}
\section*{Acknowledgements}
%\vspace*{\fill} 
First of all, I would like to express my deep gratitude to Dávid Kunszenti-Kovács, my thesis supervisor, for his patient guidance. I would like to thank Marina Petrova and Göran Andersson for their helpful comments.

I would also like to thank my parents for their continuous support throughout my studies in Hungary, Italy and Sweden.

\begin{flushright}
Benjámin Martin Seregi

Budapest, 12 May 2018
\end{flushright}
%\vspace*{\fill}
\newpage
\tableofcontents
\newpage
\pagenumbering{arabic}
\abstract{
\textbf{In English:} The optimal channel allocation problem in cellular networks is often formulated in a graph theoretic framework. One of its variants\---where each access point knows the list of its free channels\---is related the so-called list coloring problem and is closely related to the channel allocation of IEEE 802.11 systems. In spite of the fact that the list coloring problem is NP-complete for arbitrary graphs, we show that there exists a polynomial time algorithm that $k$-list colors an arbitrary graph where $k$ is the Szekeres\---Wilf number of the graph. In addition, an upper bound for the choice number of $k$-band buffering cellular graphs is obtained proving that they are $(3k(k+1)/2+1)$-choosable.

A Java application is implemented to compute the Szekeres\---Wilf number of generated cellular graph in order to facilitate making further conjectures of sharper upper bounds for the choice number.

\textbf{In Swedish:}
}
\newpage
\section{Introduction}
In telecommunication one of the most challenging problems is the efficient allocation of available frequency. When the available bandwidth is limited, the efficient utilization of the frequency spectrum is a major concern. Due to the growing number of mobile Internet users, optimal channel allocation in cellular networks and their variants have been heavily researched in recent years \cite{Audhya:2011:SCA:1988563.1988571}.

Several variants of the channel allocation problem have been defined based on the different channel constraints that a particular service might require. One of them is the so-called co-channel constraint where the same channel is not allowed to be assigned to neighboring cells simultaneously. This problem has been formalized as a graph coloring problem by many authors \cite{1456167}. Unfortunately, graph coloring is a well-known NP-complete problem \cite{Kar72} and therefore we do not know if a polynomial time algorithm for co-channel constraint satisfaction exists. Therefore various heuristic algorithms have been developed, the list of methods includes genetic algorithms, neural networks, graph-based, and other approaches \cite{Audhya:2011:SCA:1988563.1988571}.

Cellular network topologies are usually idealized as a certain geometric structure. The most common network structure is the hexagonal grid topology where each cell is represented by a regular hexagon (two cells are neighbors if they share a common boundary). In \cite{662943}, Sen, Roxborough, and Medidi exploited this special structure and proposed an algorithm that optimally solves the channel allocation problem in $k$-band buffering systems where $k$ is $1$ or $2$. Moreover, the algorithm has polynomial running time $O(p)$ where $p$ is the number of cells.

R. Wang, et al. \cite{7248845} introduced a \textit{distinctly different} channel allocation problem from all the above-mentioned problems, by assuming a $2$-band buffering hexagonal cell topology (the interference graph $G$ created from this topology is called a cellular graph) where each cell has a fixed number of frequency channels (channels are either busy or free). They asked the following question: "\textit{What is smallest size of the set of free channels associated with the cells (nodes of the cellular graph) that can guarantee interference free channel assignment to all the nodes?}". This problem is related to one of the generalizations of the graph coloring problem, called list coloring. It turned out that the required number of free channels, that is, the choice number ($\ch(G)$) of $G$ is between $8$ and $10$.

In this thesis, we extended this result by establishing a general upper bound for $k$-band buffering cellular graphs (Corollary \ref{cor:main-result}). We proved that the maximum required number of free channels is $\frac{3k(k+1)}{2}+1$ (for $k=2$, this gives back the result of \cite{7248845}). This bound along with the $k$-band buffering cellular graph chromatic number \cite{662943} give that the required number of free channels is between $\frac{3(k+1)^2}{4}$ and $\frac{3k(k+1)}{2}+1$ if $k$ is odd, otherwise the lower bound is $\frac{3(k+1)^2}{4} + 1/4$. This asymptotically means that for sufficiently large $k$ the required number of free channels is between $\chi^k(G)$ and $2 \chi^k(G)$ where $G$ is a $k$-band buffering cellular graph and $\chi^k$ the distance-$k$ chromatic number.

In addition, we have designed an algorithm (Algorithm \ref{alg:szekeres-list-coloring}) that $l$-list colors an arbitrary graph in polynomial time where $l$ is the Szekeres\---Wilf number of the graph. Since it is generally true that 
$$\chi(G) \leqslant \ch(G) \leqslant l \leqslant \frac{3k(k+1)}{2}+1$$
if $G$ is a $k$-band buffering cellular graph, Algorithm \ref{alg:szekeres-list-coloring} requires at most as many free channels as the established upper bound.

Finally, in order to get a better picture of the relationship between the Szekeres\---Wilf number of $G$ and our upper bound, computer evaluations were run to calculate the Szekeres\---Wilf number in randomly generated cellular graphs.

The rest of the thesis is organized as follows. Section \ref{ch:list-coloring} provides a comprehensive exposition of the mathematical model and preliminaries used to develop the theory of list-coloring in cellular graphs. This section introduces the concept of degree-bounded acyclic orientations and gives a short outlook on defective coloring as well.

Section \ref{ch:list-coloring} and \ref{sec:4-choosable} are an extended version of my II2202 Research Methodology and Scientific Writing report\footnote{Repository of the report: \url{https://github.com/Benmartin92/research-kth}} (co-authored with Marine Collery and supervised by prof. Gerald Q. Maguire Jr. at KTH, Fall 2017).

In Section \ref{sec:4-choosable}, an upper bound for the choice number of $1$-band buffering graphs is established proving that they are $4$-choosable. The computation of kernels in directed acyclic graphs is detailed. Finally, we close this part of the thesis by presenting a polynomial-time algorithm\---heavily based on Galvin's theorem\---that $4$-list colors $1$-band buffering cellular graphs.

Section \ref{sec:k-band-case} extends the results of Section \ref{sec:4-choosable} by deriving the above mentioned upper bound and algorithm. Furthermore, an interesting application is indicated regarding the channel allocation in IEEE 802.11 systems.

Our evaluation concerning the Szekeres\---Wilf and chromatic number of cellular graphs are drawn in Section \ref{sec:eval}.

\subsection{Problem statement}
In the age of the Internet of Things, Wireless Local Area Networks (WLANs) have become an essential part of any household, institution and public space. Most of these wireless networks operate in the 2.4GHz (and 5GHz) band using the IEEE 802.11 medium access control (MAC) protocol mostly known under the trademark ''WiFi''. The IEEE 802.11 standard divides this 2.4GHz band into 13 channels (the exact number depends on the specific protocol version and local regulations) with only three non-overlapping channels.

Transmitting simultaneously using overlapping channels might result in packet collisions (or in other words: interference) which can significantly degrade the throughput (due to the numerous packet retransmissions). Although the MAC sublayer has been designed to solve this task by regulating the wireless medium access while providing fairness and avoiding packet collisions (CSMA/CA), it has two major drawbacks: 
\begin{itemize}
\item It is unable to utilize the whole wireless spectrum (i.e. works in a single channel).
\item In a densely deployed environment, the statistical (exponential backoff) and random methods (contention window technique) work less efficiently.
\end{itemize} 
Therefore, the efficient channel allocation in such systems is of great interest to provide best performance in crowded environments. 


\subsection{State-of-the-art analysis}

In this section, the state-of-the-art analysis is divided into two parts. First, we review the general graph theoretic techniques that do not assume the network topology to be hexagonal. The second part of this literature review deals with such methods that requires the network topology to be hexagonal and exploit this special geometric property.

\subsubsection{General graph theoretic approaches}
Channel allocation problems in cellular networks have been heavily researched by many authors in graph theoretic settings \cite{marina, 1456167, mishra, wang-liu, orden} to design algorithms in order to achieve interference-free channel allocations or a certain performance criterion. 

J. Riihijarvi, M. Petrova and P. Mahonen \cite{marina} defined the term interference graph $G$ where the vertices $V(G):=\lbrace v_1,v_2, \ldots, v_n \rbrace$ are the access points and two vertices $v_i$ and $v_j$ are connected, that is, $(v_i,v_j) \in E(G)$ if and only if their traffic would interfere if they were communicating on the same channel simultaneously. A channel allocation or coloring of this graph is a function $c\colon V(G) \to F$ where $F$ is the available channels (colors) to the access points. A channel allocation (coloring) is called admissible (or proper) if and only if $(v_i,v_j) \in E(G)$ implies $c(v_i) \neq c(v_j)$ for all $i,j \in \lbrace 1, 2, \ldots, |V(G)| \rbrace$. An admissible coloring that minimizes $|c(V)|$ is called optimal, the number of color needed by an optimal coloring is the chromatic number of $G$ denoted by $\chi(G)$. 

They applied DSATUR algorithm proposed by Brélaz \cite{dsatur} to the problem that constructs an admissible coloring in polynomial time, however, DSATUR only approximates the optimal coloring. The main advantages of this algorithm are that it can be used in a distributed manner and is computationally cheap with a complexity of $O(|V(G)|^2)$. 

In addition, they investigated the scenario when the interference graph is so dense that no admissible coloring exists using the non-overlapping channel set $F'$ from $F$ (i.e. $|F'| < \chi(G)$). In that case, they used the complete channel set $F$, however an additional requirement had been introduced for the coloring function $c_T$, namely
$$
c_T(u) - c_T(v) \not\in T
$$
if $u$ and $v$ are neighbors and $T \subset \mathbb{N}$, yielding the approach called $T$-coloring (originally introduced by W. K. Hale in \cite{1456167}). The set $T$ allows the network designer to impose separation constraints on the channel assignment and thereby reducing the amount of interference.

Finally, they evaluated DSATUR algorithm against random channel allocation by measuring various network metrics such as throughput and number of packet collisions in a ns-2 simulation environment. The results showed that implementing graph coloring techniques provides real benefit compared to the uncoordinated, random channel allocation approach.

A. Mishra, S. Banerjee and W. Arbaugh \cite{mishra} addressed the same problem that $T$-coloring has been designed for, namely due to the densely deployed access points, the number of non-overlapping channels are usually not enough to construct a proper (interference-free) channel allocation. They introduced the weighted variant of the graph coloring problem, extending the above mentioned interference graph with a function $w\colon E(G) \to \mathbb{R}^+$ which indicates the importance of using non-overlapping channels (colors) for a particular pair of access points (vertices) in the interference graph.

This approach makes it possible to prioritize certain access points (by giving them higher weight) that need to serve more users or need to serve prioritized users. In order to construct an objective function using the edge weights, a special metric called $I$-factor (interference-factor) had been introduced that measures the amount of interference between two access points and therefore it is defined as a function $I\colon V(G) \times V(G) \to \mathbb{R}^+$. Naturally, if two different non-overlapping channels have been assigned to the access points $u$ and $v$ then $I(u,v)=0$ holds. The total interference is defined to be the product of the weight and the $I$-factor:
$$
\text{total interference}:=I(u,v) \cdot w(e): \quad e=(u,v) \in E(G),
$$
and therefore the following objective functions can be defined:
\begin{gather}
L(G,c) := \max_{\forall e = (u,v) \in E(G)}I(u,v) \cdot w(e), \\
L(G,c) := \sum_{\forall e = (u,v) \in E(G)}I(u,v) \cdot w(e), \\
L(G,c) := \sum_{\forall e = (u,v) \in E(G)}I(u,v).
\end{gather}
An optimal proper weighted coloring of an interference graph $G$ is a proper coloring $c$ of $G$ that minimizes the function $L(G,c)$ with a given weight $w$. One can easily read that:
\begin{enumerate}[(1)]
\item minimizes the maximum impact among all the access points, this can interpreted to be some kind of fairness among the access points,
\item minimizes the total interference in the graph which can yield good average performance with some poorly performing access points,
\item minimizes the impact of the overlapping channels. Note that a proper coloring $c$ that satisfies $L(G,c)=0$ is an interference-free channel allocation.
\end{enumerate}
Unfortunately, it has been proved that the weighted graph coloring problem is NP-hard and therefore we do not know if there exists a polynomial time algorithm that minimizes the above mentioned objective functions. However, the authors proposed two different distributed, heuristic strategies to minimize (1).

W. Wang and X. Liu in \cite{wang-liu} endowed each node in the interference graph $G$ with an additional set representing the available spectrum (i.e. free channels) at the particular location. These sets are subject to time-varying channel availability due to the traffic load variation offered by the users. They abstract the network as an undirected graph $G=(V,E,L)$ where $V$ and $E$ represent the users ($N:=|V|$ is the number of users) and the interference, respectively, similarly to the previous models. $L = \lbrace l_{ik} \rbrace$ is a $N \times K$ matrix which represents the frequency availability where $K$ is the number of available channels in total. If $l_{ik} = 1$ then channel $k$ is available at node $i$ and $l_{ik} = 0$ otherwise. The channel assignment is denoted by the matrix $S = \lbrace s_{ik} \rbrace$ where $s_{ik}$ is either $1$ or $0$ depending on whether channel $k$ has been assigned to node $i$ or not. An assignment is called a feasible assignment if and only if it satisfies the frequency and availability constraints, that is,
$$s_{ik} \cdot s_{jk} \cdot e_{ij}=0 \quad \text{ for all } i,j=1,\ldots,N \text{ and } k = 1, \ldots, K.$$

They defined an integer non-linear program that has an objective function which maximizes the spectrum utilization:

\begin{equation}\label{eq:list-multicolor}
\begin{array}{ll@{}ll}
\text{maximize}  & \displaystyle\sum\limits_{i=1}^{N} \sum\limits_{k=1}^{K} s_{ik} &\\
\text{subject to}& s_{ik} \leqslant l_{ik}\\
                 & s_{ik} \cdot s_{jk} \cdot e_{ij}=0 \\
                 & s_{ik} \in \lbrace 0,1 \rbrace,
\end{array}
\end{equation}
for all $i,j=1,\ldots,N \text{ and } k = 1, \ldots, K.$
However, solving this linear program is NP-complete and therefore the authors proposed heuristic algorithms: a distributed greedy, distributed fair and a randomized fair algorithm to address the problem. The greedy algorithm achieved nearly optimal spectrum utilization in their simulation setup. However, the approximation constants for the proposed algorithms have not been determined in the paper, and therefore the behaviour of the algorithms remained unknown in arbitrary topologies. 

D. Orden et al. \cite{orden} have recently introduced two novel coloring problems, namely the threshold spectrum coloring (TSC) and the chromatic spectrum coloring (CSC) problem. Their model is defined as follows. Let $G$ be an arbitrary, undirected graph and $S = \lbrace c_1, c_2, \ldots, c_s \rbrace$ the spectrum of colors endowed with an $s \times s$ matrix $W_{ij} := W(c_i,c_j)$ representing the amount of interference between color $i$ and $j$. For such $(G,W,c)$ triples where $c$ is an arbitrary coloring of $G$, the amount of interference induced at node $v$ is defined to be
$$I_v(G,W,c) := \sum_{u \in N(v)}W(c(u),c(v)),$$
where $N(v)$ is the neighbour set of $v$.

Given a pair $(G,W)$ and a fixed number of colors $k$, the goal of the threshold spectrum coloring is to determine the smallest non-negative $t \in \mathbb{R}$ such that $(G,W)$ admits a $k$-coloring $c$ and 
$$I_v(G,W,c) \leqslant t \text{ for all } v \in V(G).$$
The minimum $t$ is called $k$-chromatic threshold and denoted by $T_k(G,W)$.

The second problem can be considered to be the complementary problem of TSC since it fixes the threshold $t$ and aims to minimize the number of colors $k$. Formally, the $t$-interference chromatic number $\chi_t(G,W)$ is the smallest integer $k \in \lbrace 1,\ldots, |V(G)| \rbrace$ such that $(G,W)$ admits a $\chi_t(G,W)$-coloring $c$ and $I_v(G,W,c) \leqslant t$ for all $v \in V(G)$.

The authors obtained tight upper bounds for both problems.

\begin{theo}[TSC upper bound]
Let $G$ be a graph endowed with the spectrum $S$ and the interference matrix $W.$ For any $2 \leqslant k \leqslant |S|$, the following bound holds:
$$T_k(G,W) \leqslant \frac{\Delta(G) \| W \|_{\infty}}{k}.$$
In addition, the bound is tight.
\end{theo}

\begin{theo}[CSC upper bound]
Let $G$ be a graph endowed with the spectrum $S$ $(|S| \geqslant 2)$ and the interference matrix $W.$ For any fixed $t \geqslant 0$ being the multiple of $\gcd(W)$ and such that $|S|t \geqslant \Delta(G) \| W \|_{\infty}$, the following holds:
$$\chi_t(G,W) \leqslant \left( \frac{\Delta(G) \| W \|_\infty + \gcd(W)}{t + \gcd(W)} \right).$$
\end{theo}

In addition, they gave a DSATUR-based heuristic (TSC-DSATUR and CSC-DSATUR) for these problems as they are both NP-complete.

\subsubsection{Graph theoretic approaches in hexagonal topologies}\label{sec:hex-topo}

\begin{figure}
\centering
\includegraphics[scale=1.2]{figures/hexagonal-topology-wifi.pdf}
\caption{An IEEE 802.11 network topology idealized as a cellular graph colored with 3 colors. Each color represents a channel used by the access point in the corresponding cell.}\label{fig:hexagonal-topology-wifi}
\end{figure}

The topology of cellular networks is often modelled by hexagonal tilings of the plane or\---in a graph theoretic framework\---by cellular graphs (see Figure \ref{fig:hexagonal-topology-wifi}). This idealization of real-life cellular networks has been widely used by many researchers \cite{khanna, 7248845, 662943}.

S. Khanna et al. \cite{khanna} introduced the generalized chromatic number $\chi^{\underline{d}}(G)$ of a graph $G$ where $\underline{d}$ is a so-called demand vector. In this coloring problem\---similarly to above-mentioned problems\---no adjacent nodes share the same color such that node $i$ has at least $d_i > 0$ colors for all $i = 1,2,\ldots,|V(G)|$ (note that for $d=(1,1,\ldots,1) \in \mathbb{N}^n$ it is the usual coloring problem). Similarly, the generalized clique can be defined to be 
$$\omega^{\underline{d}}(G) = \max_{S \in \mathcal{F}}\left( \sum_{i \in S}d_i \right) \quad \text{where } \mathcal{F} \text{ is the set of cliques}.$$

The authors proved that for $1$-band buffering cellular graphs $\chi^{\underline{d}}(G) \leqslant (17/12) \cdot \omega^{\underline{d}}(G)$ while for $2$-band buffering cellular graphs $\chi^{\underline{d}}(G) \leqslant 2 \cdot \omega^{\underline{d}}(G)$.  We would like to note that for the usual coloring problem, this is simply $\chi(G) \leqslant 2 \cdot \omega(G)$ since $\sum_{i \in S}d_i = |S|$.

A. Sen et al. \cite{662943} calculated a lower and upper bound for distance-$k$ chromatic number of cellular graphs:

\begin{theo} The distance-$k$ chromatic number of a cellular graph $G$ is at least
\[ \begin{cases} 
      \frac{3}{4} \cdot (k+1)^2 & \text{if $k$ is odd} \\
      \frac{3}{4} \cdot (k+1)^2 + \frac{1}{4} & \text{if $k$ is even}.
   \end{cases}
\]
\end{theo}

\begin{theo} The distance-$k$ chromatic number of a cellular graph $G$ is at most $k^2 + k + 1.$
\end{theo}

It can be seen that for $k=1,2$ the bounds coincide and therefore $\chi(G)=3$ and $\chi^2(G)=7$. In addition, it can be concluded that $\chi^k(G) = O(k^2).$ We would like to note that from \cite{khanna}, it only follows that $\chi(G) \leqslant 4$ since $\omega(G)=3$ and thus $\chi^{\underline{d}}(G) \leqslant (17/12) \cdot \omega^{\underline{d}}(G)$ is not tight.

R. Wang et al. \cite{7248845} investigated a similar problem to that of \cite{wang-liu} in a $2$-band buffering hexagonal topology. However, they were interested in calculating the required number of free colors available at each node such that \ref{eq:list-multicolor} is solvable. Formally\---with the notation of \cite{wang-liu}\---they were looking for the numbers $\alpha$ and $\beta$ such that \ref{eq:list-multicolor} admits a solution:

$$\alpha \leqslant \sum^k_{k=1} l_{ik} \leqslant \beta \quad (i = 1,2,\ldots,N).$$

They proved that $\alpha=8$ and $\beta=10$ is a sufficient condition, that is, no matter how the frequency availability $L$ is defined, \ref{eq:list-multicolor} admits at least one solution.

\subsection{Motivation of the thesis}
In the thesis, we would like to extend the results of \cite{7248845} since\---to the best of our knowledge\---upper bounds for $k$-band buffering case ($k>2$) have not been reported so far. It would be useful to know the number of channels necessary to be able plan networks described in \cite{wang-liu}.

The general observation regarding the above-mentioned methods is that all authors recognized that finding the optimal solution of the channel allocation problem is NP-complete. Therefore most of the papers were organized in the following fashion:

\begin{enumerate}
\item Definition of the interference graph.
\item Definition of the problem that slightly modifies the well-known coloring problem by adding more constraints such as weighted coloring, varying color availability, demand vector and interference constraints. However, each variant inherently consists the usual graph coloring problem, which is NP-complete in itself.
\item Descriptions of various heuristic methods that solves the particular variant of the coloring problem.
\item Finally, numerical results on comparing the performance of these heuristics and the optimal solution (which was usually computed by some integer linear program in exponential time) in some well-known ''benchmark'' topologies.
\end{enumerate}
The general problem with this research methodology that the algorithms' approximation constants were computed through numerical experimentation in the well-known benchmark topology instances which does not guarantee that the algorithms scale in real-world scenarios as well.

In Section \ref{sec:hex-topo}, we tried to collect such papers that aimed to obtain some analytical results in the hexagonal topology where the special geometry can be exploited. 

Our goal is to extend the analytical results for the $k$-band buffering case ($k>2$). In addition, we would like to design such efficient (polynomial time) algorithms that do not use heuristic methods but they always achieve the established bounds. Therefore, the performance is guaranteed in arbitrary hexagonal topologies.
\subsection{How does the hexagonal case help in general design?}
In spite of the fact that our upper bound is established for $k$-band buffering cellular graphs, it can help estimating the number of channels needed to create an interference-free channel allocation an in arbitrary wireless topology. 

It is a trivial graph theoretic result that if $H$ is a subgraph of $G$ then $\chi(H) \leqslant \chi(G)$ and thus knowing a chromatic number of a graph helps estimating the chromatic number of the original graph. Since $k$-band buffering graphs model a structure that arises quite often in network topologies, we can estimate the chromatic number and the choice number in arbitrary topologies.

However, we would like to highlight the fact that Algorithm \ref{alg:szekeres-list-coloring} can be used for an arbitrary topology.

\subsection{Limitations of our approach}

A major drawback of our algorithm could be that it might not be used in a distributed manner. Algorithms that are not distributed require some kind of wireless controller that would result in higher implementation cost and exclude commercial-grade access points from the application. However, in this thesis, we do not investigate whether the proposed algorithm can be implemented in a distributed manner.

\newpage
\section{List coloring of $1$-band buffering cellular graphs} \label{ch:list-coloring}
Section \ref{sec:math-model} introduces the mathematical framework of list coloring. In Section \ref{sec:orientation}, we construct a special acyclic orientation of a cellular graph that satisfies some outdegree bound. In addition, we will give a polynomial time algorithm that constructs such orientations in polynomial time. We end this section with the generalization of the same results for arbitrary graphs by introducing the Szekeres\---Wilf number. A weaker coloring technique called ''defective coloring'' that tolerates some error in the usual graph coloring is described in Section \ref{sec:defective}.

\begin{note} Unless otherwise stated cellular graph means $1$-band buffering cellular graph.
\end{note}

\subsection{The mathematical model}\label{sec:math-model}
In this section, we introduce the basic notions and definitions that are essential to formulate the problem in a graph-theoretic setting. We introduce the definitions cellular graph, list coloring and choice number which will play a central role in our investigations. An example of list coloring and some well known bounds for the choice number are also given.
\begin{defin} A graph $G$ is a  \textit{cellular graph} (see Figure \ref{fig:cellular-graph}) if it is constructed from the hexagonal cell topology in the following way: each cell is a node and two nodes are connected if and only if they share a common boundary.
\end{defin}
\begin{figure}[!h]
\centering
\includegraphics[scale=1]{figures/cellular-graph.pdf}
\caption{An example of a cellular graph}\label{fig:cellular-graph}
\end{figure}
\begin{defin} A cellular network is $k$\textit{-band buffering} if the interference extends up to $k$ cells.
\end{defin}
\begin{defin} Let $G$ be a graph and $L(v)$ a set of colors for all $v \in V(G)$ such that $|L(v)|=k$. We say that $G$ is $k$\textit{-choosable} if $G$ is colorable such that the color of $v$ is in $L(v)$ for all $v \in V(G)$, such colorings called $k$\textit{-list coloring} of $G$.
\end{defin}
\begin{defin} The \textit{choice number} of $G$ is the smallest $k \in \mathbb{N}$ (denoted by $\ch(G)$) such that $G$ is $k$-choosable.
\end{defin}
\begin{defin} Let $G$ be any graph. The smallest and the maximum degree of $G$ are denoted by $\delta(G)$ and $\Delta(G)$, respectively.
\end{defin}
It is worth pointing out that proving a graph to be $k$-choosable is more difficult than showing that it is $k$-colorable. This simply follows from the fact that the lists $L(v):=\lbrace 1,2,3,\ldots,k\rbrace$ for all $v \in V(G)$ bring us back to the original $k$-coloring problem. This observation yields our first bound, that is, $\chi(G) \leqslant \ch(G)$ for any graph $G$. Therefore, it is not surprising that there exists a non $2$-choosable but $2$-colorable graph.
\begin{example}[A non $2$-choosable graph $G$ with $\chi(G)=2$]\label{ex:2-colorable-ch3}
To construct such an example, let us consider the graph in Figure \ref{fig:2-colorable-ch3}. Its coloring immediately shows that $\chi(G)=2$. For the choice number imagine that the numbers inside the nodes correspond to the list of available colors at each node.
\begin{figure}[!h]
\centering
\includegraphics[scale=1.7]{figures/2-colorable-3ch.pdf}
\caption{A non $2$-choosable graph $G$ with $\chi(G)=2$}\label{fig:2-colorable-ch3}
\end{figure}
Selecting either color $1$ or color $3$ in the upper-left corner leads to a conflict in the coloring and thus $G$ is not $2$-choosable.
\end{example}
\begin{theo}\label{theo:logarithm-bound}
Let $G$ be any graph with $n$ nodes. Then $\ch(G) \leqslant \chi(G) \ln{n}$.
\end{theo}
\begin{proof} To prove the inequality, we use a probabilistic argument. Assume that $G$ is colored with $s := \chi(G)$ colors, that is, the nodes $V(G)$ are divided into the color classes $C_1, C_2, \ldots, C_s$. Suppose that $G$ has a $k$-list assignment $L$ where $k = \chi(G) \ln{n}$ and $n := |V(G)|.$ Consider the probability space of the $s$-partitions $\pi \colon \pi_{1},\pi_{2},\ldots,\pi_{s}$ of $\bigcup_{v \in V(G)} L(v).$ If we can assign for all $i \in \lbrace 1,2,3,\dots,s \rbrace$ a partition $\pi_i$ to the color class $C_i$ such that for all $v \in C_i$ we have $L(v) \cap \pi_i \neq \varnothing$, then $G$ can be colored from the lists $L$. 

It remains to prove that such a partition $\pi$ exists with nonzero probability and thus the assertion follows. Let us first calculate the probability of the complementary event:
\begin{equation*}
\begin{split}
\mathbb{P}(\exists i \in \lbrace 1,2,\ldots, s \rbrace, \exists v \in C_i, L(v) \cap \pi_i = \varnothing) = \\
\sum_{v \in V(G)}\left( 1 - \frac{1}{s} \right)^k = n \left(\left(1 - \frac{1}{s} \right)^s \right)^{\frac{k}{s}} < n\mathrm{e}^{-\frac{k}{s}}.
\end{split}
\end{equation*}
The term $\left( 1 - \frac{1}{s} \right)$ is the probability of $c \in L(v)$ not being in $\pi_i.$ Since there are $k$ colors in each list and we consider every node, the summation is valid. From the equation $k = s \ln{n}$, it follows that $n = \mathrm{e}^{k/s}$ and therefore $n\mathrm{e}^{-k/s} = 1.$ Since the complementary event is not a sure event, it follows that
$$
\mathbb{P}(\forall i \in \lbrace 1,2,\ldots, s \rbrace, \forall v \in C_i, L(v) \cap \pi_i \neq \varnothing) > 0
$$
which completes the proof.
\end{proof}
\begin{note} Unfortunately, the choice number cannot be bounded by the chromatic number in general, that is, there is no function $f$ such that $\ch(G) \leqslant f(\chi(G))$ for every graph $G$ \cite{GRAVIER1996299}.
\end{note}
\begin{note}From now on we assume that all graphs are connected. We can do it without the loss of generality as all the algorithms and proofs can be repeated for each connected component of a graph.\end{note}

\subsection{Degree bounded acyclic orientations of cellular graphs}\label{sec:orientation}

\begin{defin}We say that the directed graph $D=(V,A)$ is acyclic if it does not have directed cycles, that is, it does not contain a sequence of directed edges such that $(v_1,v_2),\ldots,(v_i,v_{i+1}),\ldots,(v_n,v_1) \in A$.
\end{defin}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{lem}\label{lem:degree-constraint}
Let $G$ be a cellular graph. Then $G$ has a node $v$ such that $\deg(v) \leqslant 3$.
\end{lem}

\begin{proof} Let us consider the planar drawing of the graph $G$ which corresponds to its hexagonal topology.
Let $v$ be any node of $G$ and we assign $(0,0)$ to this node. We assign coordinates to every node starting from node $v$ in the following way. If a node $w$ is to the north of node $v$ then the coordinates of node $w$ is equal to the coordinates of node $v$ plus $(0,1)$. We summarize this method in Figure \ref{fig:assignment} according to the cardinal directions.
\begin{figure}[!h]
\centering
\includegraphics[scale=1]{figures/hexagonal-coordinate-system.pdf}
\caption{Hexagonal coordinate system}\label{fig:assignment}
\end{figure}
By applying this method to every node, we get a coordinate system within our hexagonal topology. Since there are finitely many node in $V(G)$, we can select the maximal node by selecting the node with maximal $x$- and $y$-coordinate, that is, a node $w$ with the following property: if $(x_1,y_1)$ is the coordinates of $w$ and $v \neq w$ is another node with the coordinates $(x_2,y_2)$ then $x_1 \geqslant x_2$ and $y_1 > y_2$ are satisfied.

To obtain a contradiction, suppose that the maximal node $w$ has more than 3 neighbors. It follows then at least one if its neighbors is either to the north, northeast or southeast to $w$. However, this neighbor would violate the maximality of $w$. Therefore we proved that $\deg(w) \leqslant 3$.
\end{proof}
\begin{defin}
We say that the orientation of a digraph $G$ is $k$\textit{-bounded} if for each node $v \in V(G)$ its outdegree is bounded by $k$, that is, $\deg^+(v) \leqslant k$.
\end{defin}
\begin{lem}\label{lem:bounded-acyclic-orientation}
If $G$ is a cellular graph, then $G$ has a $3$-bounded acyclic orientation.
\end{lem}
\begin{proof} Since $G=(V,E)$ is a cellular graph, we can make use of Lemma \ref{lem:degree-constraint}, that is, let $v$ be a node of $G^{(0)}:=G$ with $\deg(v) \leqslant 3$. We construct a function $f\colon V(G) \to \mathbb{N}$ by setting $f(v) := 0$ and then remove the node $v$ from $G^{(0)}$ yielding the graph $G^{(1)}$. By repeating the same procedure\---at step $i$\---we select a node $v$ in $G^{(i)}$ such that $\deg(v) \leqslant 3$ and we set $f(v):=i$. Then we remove $v$ from $G^{(i)}$ which yields the graph $V(G^{(i+1)})$ spanned by $V(G^{(i)}) \setminus \lbrace v \rbrace$. It is trivial that the graphs $G^{(1)},\ldots,G^{(|V(G)|)}$ are all cellular therefore it was valid using Lemma \ref{lem:degree-constraint}.

We note that the procedure ends after $|V(G)|$ steps.

Now we construct a digraph $H=(V,A)$ from $G$ using the function $f$. Let $(u,v) \in E$ be an arbitrary edge. If $f(u) < f(v)$ then $A:=A\cup (u,v)$ otherwise $A:=A \cup (v,u)$. By repeating this procedure for all edges in $E$ we get an orientation of $G$, that is, the digraph $H$. We need to prove that $H$ is
\begin{enumerate}
\item acyclic and
\item $\deg^+(v) \leqslant 3$ holds for all $v \in V(G)$.
\end{enumerate}
To prove (1), we will obtain a contradiction by assuming that $H$ contains a directed cycle. Let $C$ be a directed cycle in $H$ with the nodes $C:=\lbrace v_1,v_2,\ldots,v_k \rbrace$ that are ordered such that $(v_i,v_{i+1 \bmod{k}}) \in E$ $(i=1,2,\ldots,k)$ which means that $f(v_1) < f(v_2) < \ldots < f(v_{k-1}) < f(v_k)$ but also $f(v_k) < f(v_1)$ which is impossible.

What is left to show is that $\deg^+(v) \leqslant 3$. At each step we select a node with no more than $3$ remaining neighbors and those neighbors will be assigned a number that is greater than $f(v)$. Therefore the outdegree of $v$ cannot be larger than $3$.
\end{proof}

It is easy to see that the proof of this lemma can be transformed into a polynomial time algorithm. We outline the algorithm (Algorithm \ref{alg:find-acyclic-bounded-orientation}) that is based on the proof of Lemma \ref{lem:bounded-acyclic-orientation} and then we prove that its running time is $O(|V(G)| + |E(G)|)$.
\begin{algorithm}[h!]\label{alg:find-acyclic-bounded-orientation}
 \KwData{A cellular graph $G = (V,E)$}
 \KwResult{An acyclic $3$-bounded orientation of $G$}
 $G^{(0)} := G$\;
 Initialize $f \colon V(G) \to \mathbb{N}$\;
 \For{$i\leftarrow 0$ \KwTo $|V(G)|-1$}{
  Select $v \in V(G^i)$ such that $\deg(v) \leqslant 3$\;
  $f(v):=i$\;
  $V(G^{(i+1)}):=V(G^{i}) \setminus \lbrace v \rbrace$\;
 }
 Initialize $H:=(V,A)$\;
 \ForAll{$e = (u,v) \in E(G)$}{
   \eIf{$f(u) < f(v)$} {
   	$A := A \cup (u,v)$\;
   }{
   $A := A \cup (v,u)$\;
   }   
 }
 \caption{Constructing an $3$-bounded acyclic orientation of a cellular graph}
\end{algorithm}
\begin{state}\label{state:acyclic-complexity-proof} Algorithm \ref{alg:find-acyclic-bounded-orientation} has a running time of $O(|V(G)| + |E(G)|)$.
\end{state}
\begin{proof}
It is enough to prove that "Select $v \in V(G^i)$ such that $\deg(v) \leqslant 3$" can be done in $O(|V(G)|)$ since the rest is obvious. Let us initialize a queue $Q := \lbrace v \mid \deg(v) \leqslant  3\rbrace$ before we start running the algorithm. We pop a node $v$ from $G$ at every iteration and push new ones after the removal of $v$ if there are new nodes in $G$ that satisfy the degree condition. The pop and push methods can be implemented in constant time which completes the proof.
\end{proof}

\begin{note} We would like to note that a more general proposition can be formulated from Lemma \ref{lem:bounded-acyclic-orientation} without assuming that $G$ is cellular. If we can ensure that in each step a node $v$ with $\deg(v) \leqslant k$ can be selected then the algorithm will yield a $k$-bounded acyclic orientation in arbitrary graphs.
\end{note}

\begin{defin} We say that the Szekeres\---Wilf number of a graph $G$ is $k$ if every subgraph of $G$ contains a node of degree at most $k$. The term $k$-degeneracy is also used in some literature.
\end{defin}

It immediately follows that if we omit the cellular graph assumption\---having known that the Szekeres\---Wilf number of graph is $k$\---then the arguments of the proof of Lemma \ref{lem:bounded-acyclic-orientation} can be repeated and thus the following lemma holds.

\begin{lem}\label{lem:szekeres} Let $G$ be any graph with Szekeres\---Wilf number of $k$. Then $G$ has a $k$-bounded acyclic orientation. \qed
\end{lem}

Another interesting question is how to compute the Szekeres\---Wilf number of a graph. The following algorithm \cite{Matula:1983:SOC:2402.322385} computes this number in linear time by repeatedly removing the minimum-degree nodes.

\begin{algorithm}[h!]\label{alg:szekeres-wilf-computation}
 \KwData{An arbitrary graph $G = (V,E)$}
 \KwResult{The Szekeres\---Wilf number of $G$ in $szw$}
 $H^{(1)} := G$\;
 $szw := 0$\;
 \For{$i\leftarrow 1$ \KwTo $|V(G)|$}{
  Select $v_i \in V(H^{i})$ such that $\deg(v) = \delta(G)$\;
  $szw := \max(\deg(v_i), szw)$\;
  $V(H^{i+1}) := V(H^{i}) \setminus \lbrace v \rbrace$\;
 }
 \caption{Computing the Szekeres\---Wilf number of an arbitrary graph}
\end{algorithm}
\begin{proof}
The linear time is obvious as we iterate through the nodes of $G$. The efficient selection of the minimum-degree node is described in the proof of Proposition \ref{state:acyclic-complexity-proof}. Let $k$ be the Szekeres\---Wilf number of $G$. It is obvious that $szw \leqslant k = \max_{H \subset G} \delta(H)$. To obtain a contradiction assume that $szw < k$. Now let $H$ be the "maximal" subgraph in $G$, that is, $szw < \delta(H) = k$. Let $i$ be the smallest index such that $v_i \in V(H)$. Due to our choice we have $H \subset H_i$. Then $\deg_{H_i}(v_i) = \delta(H_i) \leqslant szw < k = \delta(H) \leqslant \deg_H(v_i)$. However, from $H \subset H_i$, it follows that $\deg_H(v_i) \leqslant \deg_{H_i}(v_i)$ which is a contradiction and therefore $k = szw$ as required.
\end{proof}

\subsection{Defective coloring}\label{sec:defective}
Due to the robust design of wireless communication systems, it is not always necessary (and in fact possible) to achieve interference-free channel allocation. Wireless systems employs error detecting and correcting techniques (such as Forward Error Correction (FEC) in IEEE 802.11 systems \cite{ieee80211}) codes to be able to tolerate interference to a certain extent. However, error correcting codes introduce redundancy in data transmissions and thus reduce the net transmission bit rate (or information rate).


\begin{defin} We say that a graph $G$ is $(k,d)$-colorable if the graph can be colored with $k$ colors such that every color class induces a graph with maximum degree at most $d$.
\end{defin}

Such colorings are known as \textit{defective} or \textit{improper} coloring since the definition allows the nodes to have at most $d$ neighbors from the same color class.
A classical result from Lovász shows that an arbitrary graph can be colored with $k$ colors in polynomial time with at most $[\Delta(G)/k]$ ''errors''.
\begin{theo}[Lovász]\label{theo:lovasz-defective}
Let $G$ be any graph and $k > 0$ then it is $(k,[\Delta(G)/k])$-colorable in $O(|E|)$ steps.
\end{theo}
\begin{proof} Let us consider an arbitrary (not necessarily proper) $k$-coloring of $G$. If this coloring is a $(k,[\Delta(G)/k])$-coloring then we are done otherwise choose a node $v$ that has more than $[\Delta(G)/k]$ neighbors from the same color class. It is obvious that there exists a color class $c$ with at most $[\Delta(G)/k]$ nodes in the neighbor set of $v$. By changing the color class of $v$ to color class $c$, we decrease the monochromatic edges in the coloring by at least one. Therefore we reach a $(k,[\Delta(G)/k])$-coloring in at most $|E|$ steps.
\end{proof}

Observe that the argument of Theorem \ref{theo:lovasz-defective} can be repeated in a list coloring fashion since it is true that there exists a color class $c \in L(v)$ with at most $[\Delta(G)/k]$ nodes in the neighbor set of $v$ for any $k$-list coloring. Therefore, the following theorem holds.

\begin{theo}[Lovász theorem for list coloring]Let $G$ be any graph and $k > 0$ then it is $(k,[\Delta(G)/k])$-list colorable in $O(|E|)$ steps. $\blacksquare$
\end{theo}

\begin{corollary}\label{cor:lovasz} Let $G$ be any graph then it is $(\Delta(G)/2 + 1,1)$-list colorable in $O(|E|)$ steps. $\blacksquare$
\end{corollary}

We will see that Corollary \ref{cor:lovasz} gives us a bit weaker result than the goal of this thesis (Corollary \ref{cor:main-result}), however in a much simpler and faster way.

\paragraph*{References} Example \ref{ex:2-colorable-ch3} is from \cite{erdos-choosability} \textit{Example scheme showing how choice $\ch(G)$ exceeds $\chi(G)$}. The proof of Theorem \ref{theo:logarithm-bound} can be found at \url{http://www.math.uri.edu/~eaton/TalkUriOct03P2.pdf} (accessed on the 9th March 2018). The idea of Algorithm \ref{alg:find-acyclic-bounded-orientation} came from \cite{CHROBAK1991243} \textit{Theorem 2.1} where the authors proved that every planar graph has a $5$-bounded acyclic orientation. They used the fact that every planar graph has a node with at most $5$ neighbors which follows from Euler's formula. Theorem \ref{theo:lovasz-defective} is from \cite{Cowen:1997:CD:314161.314387} \textit{Theorem 1.1} and the proof of Algorithm \ref{alg:szekeres-wilf-computation} can be found in \cite{Matula:1983:SOC:2402.322385} \textit{2. Smallest-Last Vertex Ordering}.

\section{$1$-band buffering cellular graphs are $4$-choosable}\label{sec:4-choosable}
We are about to prove one of our main results, that is, cellular graphs are $4$-choosable. We would like to note that since $G$ is a planar, it follows from Thomassen's theorem \cite{Thomassen:1994:PG:184180.184192} that it is $5$-choosable. It is worth noting that cellular graphs are $3$-colorable \cite{662943} (Theorem 1). However, even with this additional constraint, we still cannot say that if $G$ is planar and $3$-colorable then it is $4$-choosable as a counterexample can be found in \cite{JGT:JGT4}. The counterexample is quite interesting (\cite {JGT:JGT4}, second figure) as it is constructed from a cellular graph; however the author added one extra node and joined it to all of the outer nodes. Due to this step, the resulting graph does not always contain a node of degree $3$ therefore the property of Lemma \ref{lem:degree-constraint} is not true for this construction.

In Section \ref{sec:kernel-perf-and-galvin} we introduce the notion of kernel, kernel-perfectness and Galvin's theorem which gives a sufficient condition for being $k$-choosable. Section \ref{sec:dag} details the fast computation of kernels in DAGs. Finally, a polynomial time algorithm that 4-list colors an arbitrary cellular graph is given in Section \ref{sec:4-list-coloring}.
\subsection{Kernel-perfectness and theorem of Galvin}\label{sec:kernel-perf-and-galvin}
Before proving our theorem we need to introduce the notion of kernel in graphs and a theorem from Galvin \cite{Galvin:1995:LCI:199352.199369} (non-multigraph version from \cite{citeulike:395714}, Lemma 5.4.3) that will play a central role in our study. The proof of the theorem is inductive and can be transformed into an algorithm.
\begin{defin} Let $G$ be a directed graph. We say that an independent set $K \subseteq V(G)$ is a kernel of $G$ if it satisfies the following: for each node $u \in V(G) \setminus K$ there is a node $v \in K$ such that $(u,v) \in E(G)$.
\end{defin}
\begin{theo}[Galvin, 1995]\label{thm:galvin} Let $G$ be a graph and $\lbrace L(v) \mid v \in V(G) \rbrace$ given color sets. If $G$ has an orientation $D$ such that $d^+(v) < |L(v)|$ for all $v \in V(D)$ and every induced subgraph of $D$ has a kernel, then $G$ can be colored from the given color sets. $\blacksquare$
\end{theo}
We postpone giving a proof of this theorem as we will reformulate Galvin's theorem for cellular graphs later.
\begin{defin} We note that a directed graph is called kernel-perfect if all of its induced subgraphs contain a kernel.
\end{defin}
\begin{theo}\label{thm:choice-number}
If $G$ is a cellular graph then $\ch(G) \leqslant 4$.
\end{theo}
\begin{proof}
Since $G$ is cellular, we can consider its $3$-bounded acyclic orientation by Lemma \ref{lem:bounded-acyclic-orientation}. This orientation is kernel-perfect by Richardson's theorem \cite{richardson1946}. Therefore we can apply Theorem \ref{thm:galvin} (with $d^+(v) \leqslant 3$ and $L(v)=4$) which concludes the proof.
\end{proof}

We have proven that cellular graphs are $4$-choosable, hence what is left is to show that there exists an algorithm that constructs such colorings in polynomial time.
\subsection{Finding a kernel in DAGs}\label{sec:dag}

It has been shown that finding a kernel in an arbitrary graph is $\mathrm{NP}$-complete \cite{chvatal}. However, we will show that in directed acyclic graphs (DAGs) this problem can be easily solved in polynomial time. This is crucial as our $4$-list coloring algorithm has to construct kernels repeatedly at run.

\begin{defin} A topological order of a directed graph $D=(V,A)$ is a linear order of vertices $v_1,v_2,\ldots,v_n \in V$ such that if $(v_i,v_j) \in A$ is a directed edge then $i < j$ in the order.
\end{defin}

\begin{note} It is a well-known fact that every DAG admits a topological order.
\end{note}

\begin{lem}\label{lem:kernel-lemma} Let $G$ be a directed acyclic graph. Then a kernel $K \subseteq V(G)$ can be found in polynomial time.
\end{lem}
\begin{proof} Since $G$ is acyclic we can consider the topological order of its nodes (which can be computed in polynomial time). Let $\lbrace v_1, v_2, \ldots, v_n \rbrace$ be this topological order. Let us start from node $v_n$ and add it to the kernel, that is, $K = \lbrace v_n \rbrace$. Mark the neighbors of $v_n$. After that, we move on with the next node $v_{n-1}$, if it is marked we skip it otherwise we add it to the kernel $(K := K \cup \lbrace v_{n-1} \rbrace)$ and mark its neighbors. Repeat this procedure with the remaining nodes. We need to prove that
\begin{enumerate}
\item $K$ is independent and
\item for each node $u \in V(G) \setminus K$ there is a node $v \in K$ such that $(u,v) \in E(G)$.
\end{enumerate}
1) If $v \in K$ then its neighbors are marked. Since we do not add marked nodes to $K$, it is always independent.
2) When $v$ is unmarked and we add it to $K$ all of its neighbors come after it in the topological order (otherwise $v$ would have already been marked), that is, $v$ is connected to its neighbors by forward edges.
\end{proof}
\begin{algorithm}[h!]\label{alg:find-kernel-in-dags}
 \KwData{A directed acyclic graph $G = (V,A)$}
 \KwResult{A kernel $K \subseteq V(G)$}
 $T := \text{the topological order of $V(G)$}$\;
 $K := \emptyset$\;
 \For{$i\leftarrow |V(G)|$ \KwTo $1$}{
  \If{$T(i)$ is unmarked} {
  	$K := K \cup \lbrace T(i) \rbrace$\;
  	Mark the neighbors of $T(i)$\;
  }
 }
 \caption{Finding a kernel in a DAG}
\end{algorithm}

We note that the topological order can be computed in linear time in the number of nodes and edges with Kahn's algorithm \cite{Kahn:1962:TSL:368996.369025}, therefore the running time of our algorithm is $O(|V(G)|+|E(G)|)$. We also note that an induced subgraph of a DAG is trivially a DAG, therefore from Algorithm \ref{alg:find-kernel-in-dags} it follows that DAGs are kernel-perfect, that is, there is no need to apply Richardson's theorem in the proof of Theorem \ref{thm:choice-number}. 

Finally, it is worth mentioning that Von Neumann and Morgenstern \cite{neumann} proved that the kernel of a DAG is unique, that is, the output of Algorithm \ref{alg:find-kernel-in-dags} is independent of the selected topological order.
\subsection{$4$-list coloring of cellular graphs}\label{sec:4-list-coloring}
Now we have everything necessary to prove our main result and give a polynomial algorithm that computes a $4$-list coloring of a cellular graph. 

First, we reformulate Galvin's theorem for cellular graphs and prove it (Theorem \ref{thm:galvin-cellular}), the proof is based on \cite{citeulike:395714} (Lemma 5.4.3). The original proof uses mathematical induction, we just repeat the same argument, fortunately, the inductive step describes how to color the nodes, that is, the proof can be transformed into an algorithm. The cellular version, however, uses our result, namely Lemma \ref{lem:bounded-acyclic-orientation}. In addition, it also uses Lemma \ref{lem:kernel-lemma}. Then we prove that its (Algorithm \ref{alg:four-list-coloring}) running time is polynomial. Algorithm \ref{alg:four-list-coloring} uses Algorithm \ref{alg:find-acyclic-bounded-orientation} and Algorithm \ref{alg:find-kernel-in-dags}. The fact that Algorithm \ref{alg:four-list-coloring} is polynomial follows from the fact that Algorithm \ref{alg:find-acyclic-bounded-orientation} and Algorithm \ref{alg:find-kernel-in-dags} are polynomial.
\begin{theo}[Galvin's theorem for cellular graphs]\label{thm:galvin-cellular} Let $G$ be a graph and $\lbrace L(v) \mid v \in V(G) \rbrace$ given color sets. If $G$ has a kernel-perfect orientation $D$ such that $d^+(v) < |L(v)|$ for all $v \in V(D)$. Then $G$ can be colored from the given color sets.
In particular, if $G$ is a cellular graph and $|L(v)| \geqslant 4$ for all $v \in V(G)$. Then $G$ can be colored from the given color sets.
\end{theo}
\begin{proof}
Let $G^*$ be the $3$-bounded acyclic orientation of $G$ (Lemma \ref{lem:bounded-acyclic-orientation}), that is, $d^+(v) \leqslant 3$. We apply induction on $|V(G^*)|$. For $|V(G^*)|=0$, the empty coloring is good. Let us assume that we know how to color $G^*$ with $|V(G^*)| < n$ and consider the case when $|V(G^*)|=n$. Let $\alpha$ be any color from one of the color sets and set $V_\alpha$ to $\lbrace v \in V(G) \mid \alpha \in L(v) \rbrace$. Consider the non-empty subgraph $D$ of $G^*$ that is spanned by $V_\alpha$. Since $G^*$ is a DAG, it is kernel-perfect (Lemma \ref{lem:kernel-lemma}), therefore $D$ has a kernel $U \neq \emptyset$. Assign the color $\alpha$ to every node in $U$ and remove $\alpha$ from $L(v)$ for all $v \in V_\alpha$. Since $U$ is independent, and we removed $\alpha$, it follows that we did not (and we will not) violate the rules of the graph coloring. After that, remove $U$ from $D$. Since every node in $V(D) \setminus U$ sends an edge to $U$, having removed $U$ from $D$, we decreased the outdegree of each node in $D$ by $1$. Since the modified lists $L'(v)$ $(v \in V_\alpha)$ satisfy $d^+(v) < |L'(v)|$ for all $v \in V(D) \setminus U$, we can use our induction hypothesis to color $V(G^*) \setminus U$.
\end{proof}
\begin{algorithm}[h!]\label{alg:four-list-coloring}
 \KwData{A cellular graph $G$ and a set of colors $L(v)$ for all $v \in V(G)$ with $|L(v)| \geqslant 4$}
 \KwResult{$4$-list coloring of $G$}
  Let $G^*$ be the $3$-bounded acyclic orientation of $G$ (Algorithm \ref{alg:find-acyclic-bounded-orientation})\;
  \While{$V(G^*)$ is non-empty} {
  	Let $\alpha$ be a color from $L(v)$ where $v \in V(G^*)$\;
  	$V_\alpha := \lbrace v \in V(G) \mid \alpha \in L(v) \rbrace$\;
  	Let $D$ be the subgraph of $G^*$ that $V_\alpha$ spans\;
  	Let $U$ be a kernel in $D$ (Algorithm \ref{alg:find-kernel-in-dags})\;
  	Color the nodes in $U$ with color $\alpha$\;
  	Remove $\alpha$ from $L(v)$ for all $v \in V_\alpha$\;
  	Remove the colored nodes, that is, $V(G^*) := V(G^*) \setminus U$\;
  }
 \caption{$4$-list coloring of a cellular graph}
\end{algorithm}

It can be seen from the algorithm that first we call Algorithm \ref{alg:find-acyclic-bounded-orientation}, then we call Algorithm \ref{alg:find-kernel-in-dags} multiple times. If we assume the worst-case scenario when the kernel $U$ has only $1$ element, then the while loop iterates $|V(G)|$ times. The auxiliary operations such as spanning a subgraph or creating the set $V_\alpha$ can be done in linear time. Therefore the overall running time of our algorithm is $O(|V(G)|^2+|V(G)||E(G)|)$.

In each iteration, we color the nodes in $U$ and remove one color. The color is proper by Theorem \ref{alg:four-list-coloring}. However, we need to show that in each iteration every node is either colored or it has a free available color.
\begin{lem} Algorithm \ref{alg:four-list-coloring} is correct, that is, in each iteration every node is either colored or it has a free available color.
\end{lem}
\begin{proof} To obtain a contradiction, let us suppose that there is a node $v$ that is not colored and it does not have an available color ($|L(v)|=0$). This means that $v$ was in $V_{\alpha}$ for at least $4$ different colors and it was never in the kernel. However, this would mean that $d^+(v) \geqslant 4$ as $v$ sent an edge to each kernel. This is impossible since $G^*$ is $3$-bounded.
\end{proof}

\paragraph*{References} Galvin's theorem with proof can be found in \cite{citeulike:395714} \textit{Lemma 5.4.3}.

\section{The $k$-band buffering case and its application in IEEE 802.11 systems}\label{sec:k-band-case}
In this section, we generalize the current results for $k > 1$. In addition, we introduce a possible application of the presented algorithms.

\subsection{$k$-band buffering cellular graphs are $(3(k+1)k/2+1)$-choosable}
Galvin's theorem and Lemma \ref{lem:szekeres} can be summarized as follows.
\begin{theo} Let $G$ be any graph. If $G$ has a Szekeres\---Wilf number of $k$ then $G$ is $(k+1)$-choosable. In other words, if $G$ has a $k$-bounded acyclic orientation then it is $(k+1)$-choosable.
\end{theo}

By exploiting the special structure of $1$-band buffering cellular graphs, we found that such graphs always have a node with $\deg(v) \leqslant 3$ (Lemma \ref{lem:degree-constraint}). Lemma \ref{lem:bounded-acyclic-orientation} used this property to prove that they admit a $3$-bounded acyclic orientation.

Even though Algorithm \ref{alg:four-list-coloring} is designed for $1$-band buffering cellular graphs, the input graph $G$ can be easily modified such that running Algorithm \ref{alg:four-list-coloring} properly $l$-list-colors $G$ while it does not violate the $k$-band buffering requirement. The usual trick to do this is to construct a new graph $G^k$ (as depicted in Figure \ref{fig:cellular-graph-extension}) from $G$ such that $V(G^k) := V(G)$ and
\begin{equation}\label{eq:graph-mod}
(u,v) \in E(G^k) \text{ if and only if } d_{G}(u,v) \leqslant k
\end{equation}
\begin{figure}[!h]
\centering
\includegraphics[scale=1]{figures/cellular_graph_extension.pdf}
\caption{The red node of the cellular graph is connected (with dashed edges) to its $2$-distance neighbors}\label{fig:cellular-graph-extension}
\end{figure}
where $d_{G}(u,v)$ is the distance between $u$ and $v$ in $G$, that is, the length of the shortest path that connects $u$ and $v$. It is trivial that running Algorithm \ref{alg:four-list-coloring} for $G^k$ is equivalent to running a $k$-band buffering list-coloring algorithm  for $G$.

\begin{defin} The construction in Equation \ref{eq:graph-mod} is called graph powering and it is denoted by $G^k$. 
\end{defin}

The $k$th graph power of a graph $G$ can be calculated from the adjacency $\adj(G)$ matrix of $G$ in the following way \cite{power}:
$$
\adj(G^k) = \sum^k_{i=1} \adj(G)^i.
$$
\begin{note} From now on when we say $k$-band buffering cellular graph $G^k$ (or simply $G$), we mean the $k$th graph power $G^k$ that is constructed from a $1$-band buffering cellular graph $G$.
\end{note}
Obviously, we also need to modify Algorithm \ref{alg:find-acyclic-bounded-orientation} as we do not know the Szekeres\---Wilf number of $G^k$. Algorithm \ref{alg:find-acyclic-bounded-orientation-general} simply modifies Algorithm \ref{alg:find-acyclic-bounded-orientation} by selecting a node with $\deg(v) = \delta(G^i)$ in each iteration $i$ which is the same step that Algorithm \ref{alg:szekeres-wilf-computation} carries out to compute the Szekeres\---Wilf number. Therefore the following theorem holds:

\begin{figure}[!h]
\centering
\includegraphics[scale=1]{figures/proof-k-band-buffering.pdf}
\caption{This figure visualizes that above the white diagonal we either increase coordinate $x$ or $y$ of the red hexagon.}\label{fig:extremal-proof}
\end{figure}


\begin{theo} Algorithm \ref{alg:find-acyclic-bounded-orientation-general} computes a $k$-bounded acyclic orientation of an arbitrary graph $G$ where $k$ is the Szekeres\---Wilf number of $G$.
\end{theo}

\begin{proof} Immediately follows from Algorithm \ref{alg:find-acyclic-bounded-orientation} and \ref{alg:szekeres-wilf-computation}.
\end{proof}

\begin{algorithm}[h!]\label{alg:find-acyclic-bounded-orientation-general}
 \KwData{A graph $G = (V,E)$}
 \KwResult{An acyclic $k$-bounded orientation of $G$}
 $G^{(0)} := G$\;
 Initialize $f \colon V(G) \to \mathbb{N}$\;
 \For{$i\leftarrow 0$ \KwTo $|V(G)|-1$}{
  Select $v \in V(G^i)$ such that $\deg(v) = \delta(G^i)$\;
  $f(v):=i$\;
  $V(G^{(i+1)}):=V(G^{i}) \setminus \lbrace v \rbrace$\;
 }
 Initialize $H:=(V,A)$\;
 \ForAll{$e = (u,v) \in E(G)$}{
   \eIf{$f(u) < f(v)$} {
   	$A := A \cup (u,v)$\;
   }{
   $A := A \cup (v,u)$\;
   }   
 }
 \caption{Constructing a $k$-bounded acyclic orientation of an arbitrary graph $G$ where $k$ is the Szekeres\---Wilf number of $G$}
\end{algorithm}

The following question immediately arises: how large is the Szekeres\---Wilf number of $k$-band buffering cellular graphs? Unfortunately, we cannot answer this question, however the following theorem gives us an upper bound and as a corollary it turns out that $k$-band buffering cellular graphs are $(3(k+1)k/2+1)$-choosable.

\begin{theo}\label{theo:extremal-degree} Let $G^k$ be a $k$-band buffering cellular graph. Then $G^k$ has a node $v$ with $\deg(v) \leqslant 3(k+1)k/2$.
\end{theo}
\begin{proof} Let $G$ be a $1$-band buffering cellular graph and $v$ any node of $G$. It is easy to see that the maximum number of $m$-distance neighbors of $v$ is $6m$. Therefore the maximum number of at most $k$-distance neighbors of $v$ is 
$$6+12+\ldots+6k=\frac{(6 + 6k)k}{2} = 3k(k+1).$$
Let us select the same extremal point that we have selected in Lemma \ref{lem:degree-constraint}, that is, a node $v$ with maximal $x$- and $y$-coordinate. Figure \ref{fig:extremal-proof} and our hexagonal coordinate system (see Figure \ref{fig:assignment}) show that by moving either north, northeast or southeast, we increase either coordinate $x$ or $y$ that would violate the maximality of $v$. Since this region includes exactly the half of the possible at most $k$-distance neighbors of $v$, we can deduce that
$$\deg_{G^k}(v) \leqslant \frac{3(k+1)k}{2}$$ 
as required.
\end{proof}
\begin{corollary}\label{cor:main-result} Let $G^k$ be a $k$-band buffering cellular graph. Then $G^k$ is $(3(k+1)k/2+1)$-choosable.
\end{corollary}
It is worth mentioning that for $k=2$ we proved that a $2$-band buffering cellular graph is $10$-choosable which coincides with the result of \cite{7248845}. 

\begin{corollary}\label{cor:defective-main-result} Let $G^k$ be a $k$-band buffering cellular graph. Then $G^k$ is $(3(k+1)k/2+1, 1)$-list colorable in $O(|E|)$ steps.
\end{corollary}
\begin{proof} From Theorem \ref{theo:extremal-degree}, it can be seen that $\Delta(G^k) = 3k(k+1)$. The rest follows from Corollary \ref{cor:lovasz}.
\end{proof}
Now, we have everything to modify Algorithm \ref{alg:four-list-coloring} such that it can handle arbitrary graphs and thus $k$-band buffering graphs. Algorithm \ref{alg:szekeres-list-coloring} would accept list of size $3k(k+1)/2+1$, however it is possible to run Algorithm \ref{alg:szekeres-wilf-computation} to precompute the Szekeres\---Wilf number of the current $k$-band buffering graph thereby decreasing the initial list sizes.

\begin{algorithm}[h!]\label{alg:szekeres-list-coloring}
 \KwData{A graph $G$ and a set of colors $L(v)$ for all $v \in V(G)$ with $|L(v)| \geqslant k+1$ where $k$ is the Szekeres\---Wilf number of $G$}
 \KwResult{$(k+1)$-list coloring of $G$}
  Let $G^*$ be the $k$-bounded acyclic orientation of $G$  (Algorithm \ref{alg:find-acyclic-bounded-orientation-general})\;
  \While{$V(G^*)$ is non-empty} {
  	Let $\alpha$ be a color from $L(v)$ where $v \in V(G^*)$\;
  	$V_\alpha := \lbrace v \in V(G) \mid \alpha \in L(v) \rbrace$\;
  	Let $D$ be the subgraph of $G^*$ that $V_\alpha$ spans\;
  	Let $U$ be a kernel in $D$ (Algorithm \ref{alg:find-kernel-in-dags})\;
  	Color the nodes in $U$ with color $\alpha$\;
  	Remove $\alpha$ from $L(v)$ for all $v \in V_\alpha$\;
  	Remove the colored nodes, that is, $V(G^*) := V(G^*) \setminus U$\;
  }
 \caption{$(k+1)$-list coloring of $G$ where $k$ is the Szekeres\---Wilf number of $G$}
\end{algorithm}

\subsection{Channel allocation in IEEE 802.11 systems}
In IEEE 802.11 $2.4$ GHz band systems channel center frequencies are defined as follows \cite{ieee80211} (cf. Figure \ref{fig:channel-allocation}):
$$\text{Channel center frequency } = 2403 + 5\cdot n_{ch} \text{ MHz} \quad (n_{ch} = 1,2,\ldots, 13).$$
The number of non-overlapping channels with $22$ MHz channel width is $3$ (namely Channel $1, 6$ and $11$) meaning that an interference-free allocation is possible if and only if the interference graph $G$ has a chromatic number of $3$. In practice, this rarely happens due to the growing number of IEEE 802.11 access points which results in very crowded deployments.
\begin{figure}[!h]
\centering
\includegraphics[scale=0.3]{figures/wifi-freq.png}
\caption{Channel allocation in the $2.4$ GHz Band (source: \url{https://en.wikipedia.org/wiki/List_of_WLAN_channels})}\label{fig:channel-allocation}
\end{figure}

Commercial access points usually implements some kind of automatic channel allocation method that tries to switch to the optimal channel by measuring the received signal strength indication (RSSI). Cisco calls its own method Dynamic Channel Assignment (DCA)\footnote{Cisco Radio Resource Management White Paper: \url{https://www.cisco.com/c/en/us/td/docs/wireless/controller/technotes/8-3/b_RRM_White_Paper.html}} that monitors the available channels, tracks changing conditions and based on that calculates a cost metric function (CM). This CM consists of interference, noise, user sensitivity threshold and load yielding a weighted signal-to-noise-plus-interference ratio (SNIR).

Using this CM, the RF Group Leader (which is a designated access point to maintain the channel scheme in a Cisco infrastructure) ranks the access point by creating a list called Channel Plan Change Initiator (CPCI). DCA first picks the worst performing access point from the CPCI list and before moving on the next worst performing access points it selects a random one in between. Having selected an access points, DCA takes its $1$- and $2$-hop neighbors to see if the channel plan can be improved for the current CPCI.

The general problem with such methods that they try (the whole method is not described in the white paper) optimize the channel utilization in a local neighborhood which might not lead to the global optimum.

However, this CM can be used to identify the free channels (e.g. if they are below some constant) $L(v)$ at each access point $v$. A controller\---which knows the topology of the access points\---whould be able to run Algorithm \ref{alg:szekeres-list-coloring}. In addition, using the concept of graph powering we would be able to require $k$-band buffering interference-free allocations if there are enough channels (i.e. more than the Szekeres\---Wilf number of the access point topology graph).
\section{Computer evaluations}\label{sec:eval}
\subsection{Computing the Szekeres\---Wilf number}
The aim of this section is to compare our upper bound established in Theorem \ref{theo:extremal-degree} with the Szekeres\---Wilf number of $k$-band buffering cellular graphs. The reason we are interested in the relationship of these two numbers is due to the fact the a graph has Szekeres\---Wilf number of $k$ if and only if it has a $k$-bounded acyclic orientation. One direction has already been proven in Lemma \ref{lem:bounded-acyclic-orientation}. Now, assume that $G$ has $k$-bounded acyclic orientation, we need to prove that if $H$ is a nonempty subgraph of $G$ then $H$ has a node $v$ with $\deg_H(v) \leqslant k$. Since $G$ is a DAG, it has at least one node $v$ with $\deg_{H}^-(v)=0$, however $\deg_{H}^+(v) \leqslant k$ and therefore $\deg_H(v) = \deg_{H}^+(v) + \deg_{H}^-(v) \leqslant k$. This means the we cannot improve Algorithm \ref{alg:szekeres-list-coloring} by constructing better acyclic orientations.

Another benefit of this equivalence is that it is enough to find one graph where our upper bound equals the Szekeres\---Wilf number and it immediately follows that the bound is sharp.
\begin{table}[h!]
\centering
\begin{tabular}{|c|c|c|}
\hline
 $k$& Theoretical upper bound $(3k(k+1)/2)$ & Szekeres\---Wilf number \\ \hline
 1&  3&  3 \\ \hline
 2&  9&  9\\ \hline
 3&  18& 18\\ \hline
 4&  30& 30\\ \hline
 5&  45& 44 \\ \hline
\end{tabular}
\caption{The output of Algorithm \ref{alg:szekeres-wilf-computation} implemented as a Java application using a generated $k$-band buffering cellular graph of $3000$ nodes.}
\label{eval-szekeres}
\end{table}

Table \ref{eval-szekeres} shows that the bound is sharp for $k=1,2,3,4$ and for $5$ they are very close. This result somehow suggest that they might be equal for $k > 4$ using a different generated graph. This would mean that the best attainable list-coloring with Galvin's approach requires at least $3k(k+1)/2+1$ list size.

\subsection{Computing the chromatic number}
For this section, we generated a smaller instance of hexagonal topology with $500$ access points. We calculated its chromatic number and Szekeres\---Wilf number. Unfortunately, we could not compute the chromatic number of the $3000$-node (see Table \ref{eval-szekeres}) topology since it is computationally very expensive and thus it might be possible there exists $k$-band buffering topologies with higher chromatic number.

\begin{table}[h!]
\centering
\begin{tabular}{|c|c|c|c|c|}
\hline
 $k$& Lower bound: $\begin{cases} 
      \frac{3}{4} \cdot (k+1)^2 & \text{if $k$ is odd} \\
     \frac{3}{4} \cdot (k+1)^2 + \frac{1}{4} & \text{if $k$ is even}.
   \end{cases}$ 
   & Upper bound: $k^2+k+1$ \\ \hline
 1& 3& 3 \\ \hline
 2& 7 &7 \\ \hline
 3& 12 &13 \\ \hline
 4& 19 &21 \\ \hline
\end{tabular}

\caption{Bounds for the chromatic number of $G^k$ from \cite{662943}.}
\label{eval-chrom-bounds}
\end{table}

\begin{table}[h!]
\centering
\begin{tabular}{|c|c|c|}
\hline
 $k$& $\chi(G^k)$ & Szekeres\---Wilf number \\ \hline
 1& 3 &3\ \\ \hline
 2&7 & 9\\ \hline
 3& 12 &18\\ \hline
 4& 19 &28\\ \hline
\end{tabular}

\caption{Computational results show that the choice number of $G^k$ is indeed between $\chi(G^k)$ and $2 \chi(G^k)$.}
\label{eval-chrom}
\end{table}
Table \ref{eval-chrom-bounds} and \ref{eval-chrom} show the relation between the $\chi(G^k)$ and $\ch(G^k)$. We computationally verified the following analytical result, namely $\chi(G^k) \leqslant \ch(G^k) \leqslant 2 \chi(G^k)$ which can be deduced by simply taking the limit
$$\lim_{k\to\infty} \frac{3k(k+1)/2+1}{(k+1)^2 + \frac{1}{4}} = 2.$$
In other words, if every access point has at least $2\chi(G^k)$ free channels then it is always possible to create an interference-free assignment.
\paragraph*{References.} The graph generator source code is available at \url{https://github.com/Benmartin92/thesis-kth} (CellularGraphGenerator.java)). The Sage program together with the $500$-node graph's adjacency matrix is available at the same repository (adj_matrix.sage).
\section{Summary and Conclusion}
The aim of this thesis was to bring together two areas, namely graph theory and telecommunication engineering. We showed that certain cellular topologies arising in telecommunication network design can be modeled using a special graph called $k$-band buffering cellular graph.

A special frequency allocation scheme used in IEEE 802.11 systems was investigated in a graph theoretic setting by showing that it is equivalent to the list-coloring problem in cellular graphs.

An upper bound for the choice number of cellular graphs\---which relates to the number of free channels necessary to establish an interference-free channel allocation in IEEE 802.11 systems\---was established. We proved that the choice number of a $k$-band buffering cellular graph $G$ is at most $\frac{3k(k+1)}{2}+1$ generalizing the $2$-band buffering case of R. Wang, et al. \cite{7248845} which was the main inspiration of this thesis.

In addition, computer simulations were run to calculate the Szekeres\---Wilf number in large cellular graphs showing that our bound is sharp for $k=1,2,3$ and $4$. 

Our conjecture is that this bound is sharp for $k > 0$ and it might be proved by constructing an appropriate $k$-band buffering cellular graph.
\newpage
\printbibliography
\addcontentsline{toc}{section}{References}
\end{document}