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:
6. * Prove that the chromatic polynomial of the ladder graph with 2n vertices pictured below is (k2 − 3k + 3)n−1k(k − 1).
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.
版权所有：编程辅导网 2021 All Rights Reserved 联系方式：QQ:99515681 微信：codinghelp 电子信箱：99515681@qq.com
免责声明：本站部分内容从网络整理而来，只供参考！如有版权问题可联系本站删除。
