Coloring the Nodes of a Graph with Five Colors

A graph is called planar if it can be drawn in the plane without edge crossings. In a drawing of a graph, nodes are identified with points in the plane and edges with lines connecting the corresponding end nodes. The edges are not allowed to cross nodes in the drawing.

LEDA Function for Coloring the Nodes of a Graph with Five Colors

FIVE_COLOR() colors the nodes of a planar graph G=(V,E) using five colors. FIVE_COLOR() computes for every node in V one of five colors such that the source and the target of every edge in E are assigned different colors.

Remark: FIVE_COLOR() also works for many non-planar graphs.

Application: Time Tabling and Scheduling

Many scheduling problems involve allowing for a number of pairwise restrictions on which jobs can be done simultaneously. For instance, in attempting to schedule classes at a university, two courses taught by the same faculty member cannot be scheduled for the same time slot. Similarly, two course that are required by the same group of students also should not conflict. The problem of determining the minimum number of time slots needed subject to these restrictions is a graph coloring problem. (Courses correspond to nodes and there is an edge between two nodes if the corresponding courses cannot be taught simultaneously.)

Example of How To Use FIVE_COLOR()

The following program shows how the function FIVE_COLOR() can be used.

Remark: The graph algorithms in LEDA are generic, that is, they accept graphs as well as parameterized graphs.

We first create a random planar graph G with 10 nodes and 30 edges and compute FIVE_COLOR() for G and a node_array<int> color.

#include <LEDA/graph/graph.h>
#include <LEDA/graph/node_array.h>
#include <LEDA/graph/plane_graph_alg.h>

using namespace leda;

int main()
{
  graph G; 

  random_planar_graph(G,10,30);

  node_array<int> color(G);
  FIVE_COLOR(G,color);
  
  node v; forall_nodes(v,G) {
    G.print_node(v);
    std::cout << " " << color[v] << std::endl;
  }

  return 0;
}

See also:

Algorithms for Planar Graphs

Graphs

Parameterized Graphs

Node Arrays

Graph Algorithms

Graphs and Related Data Types

Manual Entries: