Selected topics in finite mathematics/Graph coloring

From Wikiversity
Jump to navigation Jump to search

Objectives[edit]

To color all the vertices where no adjacent vertex is alike, use the least amount of colors possibles

Details[edit]

vertex coloring graph where no adjacent vertices are similar, two coloring a graph that you only use 2 colors, and three coloring a graph that you only use 3 colors

Examples[edit]

Examples of graph colorings
Figure E1  
Figure E2  
Figure E3  
Figure E4  
Figure E5  
  1. The graphs in figure E1-E5 have been colored with three colors. Note in particular that no two adjacent vertices share the same color.

Nonexamples[edit]

Examples of graphs with colored vertices, that are not graph colorings
Figure N1  
Figure N2  
  1. Neither of the graphs in figures N1 nor N2 are valid colorings because some adjacent vertices use the same color. That is, two vertices that share an edge have the same color.

FAQ[edit]

Homework[edit]

Figure H1  
Figure H2  
Figure H3  
Figure H4  
Figure H5  
  1. Color the graph in figure H1 with as few colors as possible.
  2. Color the graph in figure H2 with as few colors as possible.
  3. Color the graph in figure H3 with as few colors as possible.
  4. Color the graph in figure H4 with as few colors as possible.
  5. Color the graph in figure H5 with as few colors as possible.

Homework Solutions[edit]

2. 5 colors must be used because each vertex is connected to all of the surrounding vertices