Let G = (V, E) be a graph of order n and let 1 ≤ k < n be an integer. The k-token graph of G is the graph whose vertices are all the k-subsets of V, two of which are adjacent whenever their symmetric difference is a pair of adjacent vertices in G. In this paper we characterize precisely, for each value of k, which graphs have a regular k-token graph and which connected graphs have a planar k-token graph.
A colored mixed graph has vertices linked by both colored arcs and colored edges. The chromatic number of such a graph is defined as the smallest order of a colored mixed graph such that there exists a (color preserving) homomorphism from to . These notions were introduced by Nešetřil and Raspaud in , J. Combin. Theory Ser. B (2000), no. 1, 147–155, where the exact chromatic number of colored mixed trees was given. We prove here that this chromatic number is reached by the much simpler family...
Page 1