Math 137A Assignment 4

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Math 137A Assignment 4

1.  * Prove that if χ(G) = k , then G has at least edges.

2.  *  Let G have chromatic number k  and suppose you are given a k- coloring of G.  Prove that for each color i, there is some vertex colored i that is adjacent to vertices of each of the other k − 1 colors.

3. A graph G is color-critical if χ(G − v) < χ(G) for every vertex v (i.e., deleting any vertex reduces the chromatic number). Prove that if G is a color-critical graph, then the graph G′ constructed from G using Mycielski’s construction is also color-critical.

4.  Prove that the chromatic number of the graph below is 4.  Hint:   To show that χ(G) > 3,  start by classifying the independent sets of size 4 . Show that when deleting any such independent set, the resulting graph is not bipartite.   Why does  that suffice?

5.  * Calculate the chromatic polynomial of the following wheel graph:

7.  * Recall that the Tutte polynomial of a graph G = (V, E) is defined as

where k(A) is the number of components of the subgraph (V, A).

For this question, if G is connected, then verify that TG(1, 1) equals the number of spanning trees of G.  Note:   we  adopt the convention that 00  = 1.

8.  * Prove that every cubic Hamiltonian graph has chromatic index 3. Conclude that the Petersen Graph is not Hamiltonian.

9.  * If G is k-regular and connected but there is a vertex v such that G − v is disconnected, then prove that χ′ (G) = k + 1.