= Solution
The first assertion is \b[false]. The <complete graph> $K_4$ has $\chi(K_4)=4$, but $\chi'(K_4)=3$: color each of its three perfect matchings with its own color. It is connected and has more than two vertices.
The second assertion is \b[false]. Take the <crown graph> with bipartition $a_1,\ldots,a_5$ and $b_1,\ldots,b_5$, joining $a_i$ to $b_j$ exactly when $i\ne j$. Its <chromatic number> is two. In the ordering $a_1,b_1,a_2,b_2,\ldots,a_5,b_5$, the <greedy coloring> algorithm assigns color $i$ to both $a_i,b_i$: both see all previously used colors, but they are not adjacent to each other. It therefore uses five colors, exceeding $2\chi(G)=4$. Taking more pairs makes the ratio arbitrarily large.
The third assertion is \b[true]. When an edge is colored greedily, at most $2\Delta-2$ adjacent edges have previously received colors. Thus the <greedy coloring> algorithm uses at most $2\Delta-1\le2\chi'(G)-1<2\chi'(G)$ colors whenever the graph has an edge. The edgeless case is trivial. This bound holds for every edge ordering.
Back to article page
