Let $n, a_1, a_2, . . . , a_k$ be distinct positive integers. A finite Toeplitz graph $T_n(a_1, a_2, . . . , a_k) = (V,E)$ is a graph where $V = {v_0, v_1, . . . , v_{n-1}}$ and $E = {(v_i, v_j ), for |i - j| \in {a_1, a_2, . . . , a_k}}$. If the number of vertices is infinite, we get an infinite Toeplitz graph. In this paper we first give a complete characterization for connected bipartite finite/infinite Toeplitz graphs. We then focus on finite/infinite Toeplitz graphs with k <= 3, and provide a characterization of their chromatic number.
Coloring Toeplitz graphs
Nicoloso S;
2010
Abstract
Let $n, a_1, a_2, . . . , a_k$ be distinct positive integers. A finite Toeplitz graph $T_n(a_1, a_2, . . . , a_k) = (V,E)$ is a graph where $V = {v_0, v_1, . . . , v_{n-1}}$ and $E = {(v_i, v_j ), for |i - j| \in {a_1, a_2, . . . , a_k}}$. If the number of vertices is infinite, we get an infinite Toeplitz graph. In this paper we first give a complete characterization for connected bipartite finite/infinite Toeplitz graphs. We then focus on finite/infinite Toeplitz graphs with k <= 3, and provide a characterization of their chromatic number.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
