Note that if K_t is the complete graph on t vertices with t even, then the 2-power of the 2-subdivision of K_t is isomorphic to the total graph of K_t. That is the graph T(K_t) whose vertex set is V(K_t) union E(K_t) and two vertices are adjacent in T(K_t) if their either adjacent or incident in K_t.
clique number of T(K_t) is t + 1 and the chromatic number of T(K_t) is >= t+2.
login/create account
Drupal
CSI of Charles University
Needs revision
Note that if K_t is the complete graph on t vertices with t even, then the 2-power of the 2-subdivision of K_t is isomorphic to the total graph of K_t. That is the graph T(K_t) whose vertex set is V(K_t) union E(K_t) and two vertices are adjacent in T(K_t) if their either adjacent or incident in K_t.
clique number of T(K_t) is t + 1 and the chromatic number of T(K_t) is >= t+2.