Graph coloring facts for kids

A valid solution of coloring a graph, when two connected vertices must not get the same color.

Graph coloring is the name for a number of problems from graph theory. These problems are concerned with coloring (or labelling) the vertices of a graph, given certain conditions. A simple problem in this context might look for the minimal number of colors needed to color the vertices, when two connected vertices cannot have the same color. In the graph shown, the circles are called vertices and the lines connecting them are called edges. The minimum number of colors needed to color a graph is called its chromatic number.

Images for kids

• 

  All non-isomorphic graphs on 3 vertices and their chromatic polynomials. The empty graph E₃ (red) admits a 1-coloring; the complete graph K₃ (blue) admits a 3-coloring; the other graphs admit a 2-coloring.

See also

In Spanish: Coloración de grafos para niños