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 https://www.java.com/en/download/index.jsp, 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.

  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|

Copyright © 1996-2018 Alexander Bogomolny

71878703