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