Coloring a Graph

The applet below provides a dynamic environment for coloring the nodes (vertices) of a graph. The applet provides a palette of ten colors for the user to color the nodes of a graph. In graph coloring, the name of the game is to color the vertices using the fewest number of colors (the only restriction being that nodes joined by an edge cannot be colored with the same color). The purpose of the applet is to develop the user's skill in finding optimal colorings (colorings that use the minimal number of colors), or at least "good" colorings of the nodes of a graph.

  1. On load, the user is presented with a sample of six graphs. These can be modified and new graphs can be added for a duration of a session. Currently, no kind of modifications survive between sessions.
  2. The "Select graph" tab is displays thumbnails of the defined graphs. Click on a thumbnail to select a graph and then switch to one of the other tabs. A double click on a thumbnail serves as a shortcut: the tabs change automatically.
  3. The "Color graph" tab is for coloring nodes, naturally. Coloring can be done either by picking a color from a checkbox at the bottom, or by cycling through the colors. To color a nod, pick a color and click on the nod. Repeated clicking on a nod changes it color in a cycling manner.
  4. The "Define graph" tab allows one to define or modify a graph. The action depends on which if the checkboxes at the bottom is checked. To add a node, click on an empty space. To add an edge, click between two nodes close to the imaginary line joining their centers, or on two nodes in sequence.

This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at, download and install Java VM and enjoy the applet.

What if applet does not run?

A k-coloring of a graph G, is a labeling of the vertices of the graph with k colors. A k-coloring is proper if adjacent vertices are labelled differently. A graph is k-colorable if it has a proper k-coloring. The chromatic number χ(G) is the least positive integer k such that G is k-colorable.

[an error occurred while processing this directive]

|Contact| |Front page| |Contents| |Algebra| |Activities|

Copyright © 1996-2018 Alexander Bogomolny

[an error occurred while processing this directive]
[an error occurred while processing this directive]