Semi-Balanced Graph Colorings

Jesper Jansson
December, 2002
Master's Thesis in Mathematics

Abstract

We generalize the concept of a 2-coloring of a graph to what we call a semi-balanced coloring by relaxing a certain discrepancy condition on the shortest-paths hypergraph of the graph.

Let G be an undirected, unweighted, connected graph with n vertices and m edges. We prove that the number of different semi-balanced colorings of G is:
(1) at most n+1 if G is bipartite;
(2) at most m if G is non-bipartite and triangle-free; and
(3) at most m + 1 if G is non-bipartite.

Based on the above combinatorial investigation, we design an algorithm to enumerate all semi-balanced colorings of G in O(n m²) time.

PostScript version (1019400 bytes).

A printed version of the thesis can be obtained from:

Technical Reports Librarian

Centre for Mathematical Sciences

Lund University

Box 118

SE-221 00 Lund

Sweden

E-mail: Expedition@math.lu.se

Back