Grinberg-Introduction-Graph-Theory · Problem 6.9

Colorings

Mathematics — Graph Theory · chromatic-polynomial

Problem

Let g∈Ng \in \mathbb{N}. Let GG be the simple graph whose vertices are the 2g+12g+1 integers −g,−g+1,…,g−1,g-g, -g+1, \ldots, g-1, g, and whose edges are {0,i}for all i∈{1,2,…,g};\{0, i\} \quad \text{for all } i \in \{1, 2, \ldots, g\}; {0,−i}for all i∈{1,2,…,g};\{0, -i\} \quad \text{for all } i \in \{1, 2, \ldots, g\}; {i,−i}for all i∈{1,2,…,g}\{i, -i\} \quad \text{for all } i \in \{1, 2, \ldots, g\} (these are 3g3g edges in total). Compute the chromatic polynomial χG\chi_G of GG.

Browse the problem library