Explore BrainMass

List-Chromatic Numbers

Show that K3,3 has list-chromatic number 3.

Please can you explain what does list-chromatic number means and don't forget to draw a graph.

Solution Preview

In a proper graph coloring, all vertices are colored such that any two adjacent vertices (vertices which share an edge) are different colors. In a standard k-coloring we may use any of the k colors for each vertex. In a list coloring, each vertex has an associated list of colors that it can take on. The list chromatic number is the minimum number of colors k such that, if every list has k colors, there is a proper coloring. (In other words, assume someone is ...

Solution Summary

List-Chromatic Numbers are investigated. The solution is detailed and well presented.