Coloring The Line.
Arnfried Kemnitz, Massimiliano Marangio · Ars Combinatoria · 2007
Coloring the Line Arnfried Kemnitz Computational Mathematics, Techn. Univ. Braunschweig, Pockelsstr. 14, 38 106 Braunschweig, Germany [email protected] The distance graph G(S, D) has vertex set V (G(S, D)) = S ⊆ IR and two vertices u and v are adjacent if and only if their distance d(u, v) is an element of the distance set D ⊆ IR+. We determine the chromatic index, the choice index, the total chromatic number and the total choice number of all distance graphs G(IR, D), G(Q, D) and G(ZZ, D) transferring a theorem of de Bruijn and Erdős on infinite graphs. Moreover, we prove that |D|+ 1 is an upper bound for the chromatic number and the choice number of G(S, D), S ⊆ IR.