National University of Computer & Emerging Sciences

MT-3001 Graph Theory

Instructor: Miss Urooj
COLORING VARIATION
The previous sections should show just how varied and deep of a field is graph coloring. This
section will highlight additional variations of graph coloring, specifically vertex colorings. Within
each of these we will see applications of graph coloring that can inform why this new version of
coloring is worthy of study.

On-Line Coloring:
On-line coloring differs from a general coloring in that the vertices are examined one at a time
(hence they are seen in a linear manner, or “on a line”).
 The notion of an on-line coloring relies on a specific type of subgraph, called an induced
subgraph.
 We need induced subgraphs for coloring problems since if we only took any subgraph and
colored it, we may be missing edges that would indicate two vertices need different colors
in the larger graph.
 On-line coloring algorithms require a vertex to be colored based only upon the induced
subgraph containing that vertex and the previously colored vertices.

Many different on-line algorithms exist, some of which can be quite complex.
 Mathematicians are often interested in finding an on-line algorithm that works well on a
specific type of graph, or in showing how the underlying structure of specific types of
graphs limits the performance of any on-line algorithm.
 We will focus on a greedy algorithm called First-Fit that uses the first available color for a
new vertex.

1
One of the benefits of First-Fit is the ease with which it is applied. When a new vertex is
encountered, we simply need to examine its neighbors that have already been colored and give
the new vertex the least color available.

2
3
4
As the example above shows, First-Fit can perform quite well given the proper ordering.
Unfortunately, given the right graph and wrong order of the vertices, First-Fit can perform
remarkably poorly, as seen below.

5
6
7
8
9
WEIGHED COLORING:
Consider the following scenario.
Ten families need to buy train tickets for an upcoming trip. The families vary in size but each of
them needs to sit together on the train. Determine the minimum number of seats needed to
accommodate the ten family trips.
Explanation:
This problem should sound very similar to Example 6.15 where colors were representing seats and
the vertices were intervals of time indicative of when a person was on the train. Here, we are still
interested in a graph coloring, but now each vertex represents a family and so has a size associated
with it.
In previous chapters, we used weights on the edges of a graph to indicate distance, time, or cost.
For graph coloring models, weighted edges would have very little meaning.
Instead, we will be assigning a weight to each vertex, and finding a proper coloring will be referred
to as a weighted coloring.

Note that in some publications, weighted colorings are referred to as interval colorings (since an
interval of colors is being assigned to each vertex). To avoid the confusion between interval
colorings and interval graphs, we use the term weighted coloring.

10
Remarks:
We focus less on a vertex degree and more on the vertex weight when we are searching for a
minimal weighted coloring.
This is in part due to the need for the set of colors to be consecutive.
If a vertex has high weight, then it needs a larger range from which to pick the set of colors.
Whereas a vertex with large degree but a small weight may be able to squeeze in between the sets
of colors of its neighbors.

11
12
13
On-line algorithms, and specifically First-Fit, can also be used for weighted colorings. It should not
come to much surprise that on-line algorithms generally use more colors than when the entire
graph can be seen.

14
LIST COLORING:
Like weighted coloring, list coloring is a more modern approach to graph coloring and was
introduced independently by Vizing in 1976. In list coloring we are concerned with assigning colors
to vertices (or edges) with the added restriction that the colors must come from some predefined
list. Before we dive into the theory and some surprising results, let us consider the following
example.

The lists for the vertices need not be the same size nor contain the same items. The example
above shows that finding a proper coloring can largely depend on the lists given for the vertices;
the difference between the first and second set of lists above was minor (only those for a and b
changed). Before we discuss some results on list coloring, we formally define what we mean by
measuring a graph’s ability to be list colored.

15
First, we should note that choosability is not based on if there exists a singular collection of lists, each of a given size,
that exhibit a proper coloring.
Every possible collection of lists of a given size can produce a proper coloring. This should intuitively make sense as
otherwise we could find a proper coloring if each vertex has a list of size one with the lists being disjoint.
However, there is a direct relationship between the choosability of a graph and its chromatic number.

Conclusion:
Graph coloring provides avenues for studying limitations and optimal strategies for resource
management. As such, many additional variations of graph coloring exist that cannot be included
here, such as total coloring, path coloring, and acyclic coloring.

16