A graph coloring assigns a color to every vertex in a graph, with the restriction that two…
A graph coloring assigns a color to every vertex in a graph, with the restriction that two vertices of the same color cannot be adjacent. A graph is said to be k-colorable if it can be colored in k or fewer colors.
• Give an algorithm that will return true if a graph is 2-colorable and false otherwise.
• Exercise 15 defined a bipartite graph. Show that a graph is bipartite if and only if it is 2-colorable. Then, using this fact, implement a method that detects whether a graph is bipartite.
A graph is said to be bipartite if the vertices can be divided into two groups such that every edge goes from a vertex in one group to a vertex in the other group. Figure 28-1 of the previous chapter contains a bipartite graph. We could put Sandwich, Hyannis, Orleans, and Provincetown in group A, and Barnstable, Falmouth, Chatham, and Truro in group B. Every edge goes from a vertex of group A to a vertex of group B.
a. Which of the graphs in Figure 28-4, 28-6, and 28-7b are bipartite?
b. How might the implementation of a bipartite graph differ from that of a regular graph to take advantage of its bipartite nature?