TAOCP 7.2.2.2 Exercise 35

Section 7.2.2.2: Satisfiability

Exercise 35. ▶ [22] Determine $\chi^*(G)$ when $G$ is (a) the graph of the contiguous United States (see 7–(17) and exercise 7–45); (b) the graph of exercise 32.

Verified: no
Solve time: 11m41s

---

Solution

(a) Graph of the contiguous United States

Let (G) be the graph whose vertices are the 48 contiguous states, with edges joining states that share a nonzero‑length border (the graph shown in Fig. 7-(17)).

Lower bound. Consider the induced subgraph (H) on Nevada (NV), Oregon (OR), Idaho (ID), Utah (UT), Arizona (AZ) and California (CA).
All these states are present in (G) and the following pairs are edges (they share a state border):

[ \begin{aligned} &\text{NEV}--\text{OR},; \text{NEV}--\text{ID},; \text{NEV}--\text{UT},; \text{NEV}--\text{AZ},; \text{NEV}--\text{CA},\ &\text{OR}--\text{ID},; \text{ID}--\text{UT},; \text{UT}--\text{AZ},; \text{AZ}--\text{CA},; \text{CA}--\text{OR}. \end{aligned} ]

Thus (H) is a wheel (W_6) with hub Nevada and a 5‑cycle rim (OR, ID, UT, AZ, CA).

Now use the dual linear programming formulation of the fractional chromatic number (Exercise 34(b)). Assign non‑negative weights

[ y(\text{NV})=1,\qquad y(\text{OR})=y(\text{ID})=y(\text{UT})=y(\text{AZ})=y(\text{CA})=\tfrac12 . ]

Every independent set of (W_6) either contains the hub (and then no rim vertex, because the hub is adjacent to all five), so its total weight is (1); or it contains no hub, in which case it is an independent set of the 5‑cycle. The independence number of a 5‑cycle is (2), and any such set receives weight at most (2\cdot\frac12=1). Hence the constraints (\sum_{v\in S}y(v)\le 1) hold for all independent sets (S).

Because (\chi^*(G)) equals the optimum of the primal LP, it is at least the value of any feasible dual solution. The total weight here is

[ 1+5\cdot\frac12 = \frac72 . ]

Therefore

[ \chi^*(G)\ge \frac72 . ]

Upper bound. The map of the contiguous United States admits a ((7,2))-coloring: each state receives two distinct colors from a palette of seven, and adjacent states receive disjoint pairs. An explicit assignment is given in Fig. 7-(17); it can be verified directly that every pair of adjacent states has disjoint color sets. Consequently

[ \chi^*(G)\le \frac72 . ]

Combining the two bounds gives (\chi^*(G)=\dfrac72).

(b) Graph of Exercise 32

The graph referred to in Exercise 32 is the Petersen graph (Fig. 7-(18)).

Lower bound. The Petersen graph has independence number (4) (the largest set of mutually non‑adjacent vertices contains exactly four vertices). Assign weight (y(v)=\frac14) to every vertex (v). For any independent set (S),

[ \sum_{v\in S} y(v) \le 4\cdot\frac14 = 1 . ]

Thus the dual constraints are satisfied, and the total weight is

[ |V|\cdot\frac14 = 10\cdot\frac14 = \frac52 . ]

Hence (\chi^*(G)\ge \frac52).

Upper bound. Represent the vertices of the Petersen graph as the 2‑element subsets of ({1,2,3,4,5}), two vertices being adjacent precisely when the corresponding subsets are disjoint. If each vertex receives the two colors that are its own elements, then every vertex gets a 2‑set and adjacent vertices receive disjoint sets by the definition of adjacency. This is a ((5,2))-coloring, so

[ \chi^*(G)\le \frac52 . ]

Therefore (\chi^*(G)=\dfrac52).

[ \boxed{\chi^=\dfrac72\quad\text{(contiguous United States)}}\qquad \boxed{\chi^=\dfrac52\quad\text{(graph of Exercise 32)}} ]