Choose two graphs and determine the chromatic numbers of them. Give your explanationfor each case. — 이것저것 공부방

728x90

Solution

1. Figure (a)

The graph in Figure (a) includes the subgraph $C_5$ (observe the outer 5 vertices).
If the graph is 2-colorable, it must have an even number of vertices. However, $C_5$ has an odd number of vertices (5).
Thus, $\chi(C_5) \geq 3$ .
Below is Figure (a):

I marked the graph with 3 proper colors (1, 2, 3). It is 3-colorable.
Therefore, $\chi(\text{graph (a)}) = 3$ .

2. Figure (b)

The graph in Figure (b) also contains $C_5$ . I highlighted it with a yellow line.
For the same reason as mentioned above, the chromatic number of this graph is at least 3.
Below is Figure (b):

I marked the graph with 3 proper colors (1, 2, 3). It is 3-colorable.
Therefore, $\chi(\text{graph (b)}) = 3$ .

728x90

저작자표시

'Graph Theory' 카테고리의 다른 글

Let $e_i(G)$ denote the number of vertices of G whose degree is strictly greater than i. Use the greedy algorithm to show that if $e_i(G) \leq i + 1$ for some i, then $\chi(G) \leq i + 1$ . Find an example H that satisfies $e_4(H) \leq 5$ and compute χ(H) (0)	2025.01.14
For every graph G, show that there is an ordering of the vertices of G such that the numberof required colors from Greedy Algorithm is exactly χ(G). (You should describe how togive such an order.) (0)	2025.01.14
Use Menger’s Theorem to prove that κ(G) = κ′(G) for every 3-regular graph G. (1)	2025.01.14
Use Menger’s Theorem ( $\kappa$ (x, y) = $\lambda$ (x, y) when $xy$ $\notin$ $E(G)$ ) to prove that $\alpha'(G) = \beta(G)$ when $G$ is bipartite. (0)	2025.01.14
Let G be a simple graph of even order n having a set S of size k such that o(G-S) > k. Prove that G has at most $\binom{k}{2} + k(n-k) + \binom{n-2k-1}{2}$ edges, and that this bound is best possible. Use this to determine the maximum size of a simple $n$ (0)	2025.01.14

Solution

이것저것 공부방 프로그래밍, 주식 등 공부한 것을 정리하고 공유하는 공부방입니다! ___+_

티스토리툴바