CHAPTER 1
Classical Coloring of Graphs
ADRIAN KOSOWSKI, KRZYSZTOF MANUSZEWSKI
Despite the variety of graph coloring models discussed in published papers of
a theoretical nature, the classical model remains one of the most significant and
widely applied in practice. The NP-hardness of the coloring problem gives rise to
the necessity of using suboptimal methods in a wide range of practical applica-
tions. Moreover, the large range of problems solved by classical coloring, as well as
the variety of graph families with practical significance in this field aids the evolu-
tion and development of new suboptimal algorithms. There exist several relatively
simple methods, which are regarded as classical due to their date of creation or
scope of practical application. As the implementation of a particular algorithmic
solution requires the selection of at least one coloring method, it is essential to for-
mulate criteria for the assessment of the suitability of coloring algorithms. Speed
of operation, measured through computational complexity, is obviously one of the
most important features which are taken into consideration when selecting a graph
coloring approach. For suboptimal methods, the algorithm's performance guar-
antee is another characteristic feature, describing how accurate, or more precisely
how inaccurate the obtained results may be. The analysis of the smallest hard to
color graphs is yet another criterium, which in a certain sense complements the
performance guarantee.
1.1.
Basic terms and definitions
DEFINITION
1.1. A graph G is an ordered pair G
=
(V, E), where V stands
for a finite set of elements called vertices, while E - a finite set of unordered pairs
of vertices called edges. The cardinality of the set of vertices V is denoted by the
symbol n
=
lVI
and called the order of graph G. Likewise, the cardinality of the
set of edges E is denoted by m
=
lEI
and called the size of graph G. The vertices
u, v
E
V are called adjacent (or neighbours) if { u, v}
E
E and nonadjacent if
{ u, v}
'f.
E. The edges e, f
E
E are said to be adjacent if
en
f =1-
0
and nonadjacent
if
en f =
0.
DEFINITION
1.2. The degree deg(v) of vertex v in graph G is the number of
edges incident to vertex v in graph
G,
that is
I {
e
E
E:
v
E
e}
1.
The maximum
degree of a vertex in graph
G
is denoted by
~(G),
while the minimum degree is
denoted by J(G). The number g(G)
=
2m/(n(n-
1))
is known as the density of
graph G.
Only simple graphs (graphs with no directed edges, loops or multiple edges)
will be taken into account in further considerations.
http://dx.doi.org/10.1090/conm/352/06369
Previous Page Next Page