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.

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.

1. Ramsey's Theorem
2. Party Acquaintances
3. Ramsey Number R(3, 3, 3)
4. Ramsey Number R(4, 3)
5. Ramsey Number R(5, 3)
6. Ramsey Number R(4, 4)
7. Geometric Application of Ramsey's Theory
8. Coloring Points in the Plane and Elsewhere
9. Two Colors - Two Points
10. Three Colors - Two Points
11. Two Colors - All Distances
12. Two Colors on a Straight Line
13. Two Colors - Three Points
14. Three Colors - Bichromatic Lines
15. Chromatic Number of the Plane
16. Monochromatic Rectangle in a 2-coloring of the Plane
17. Two Colors - Three Points on Circle
18. Coloring a Graph
19. No Equilateral Triangles, Please

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

Copyright © 1996-2012 Alexander Bogomolny