Let $n, a_1, . . . , a_k$ be distinct positive integers. A finite Toeplitz graph $T_n(a_1, . . . , a_k) = (V,E)$ is a graph where $V = {v_0, . . . , v_{n-1}}$ and $E = {(v_i, v_j), for |i-j| in {a_1, . . . , a_k}}$. In this paper, we characterize bipartite finite Toeplitz graphs with $k <= 3$. As a consequence, using previous results, we get a complete characterization for the chromatic number of such graphs. In addition, we characterize some classes of bipartite Toeplitz graphs with $k >= 4$.
Bipartite finite Toeplitz graphs
Nicoloso S;
2011
Abstract
Let $n, a_1, . . . , a_k$ be distinct positive integers. A finite Toeplitz graph $T_n(a_1, . . . , a_k) = (V,E)$ is a graph where $V = {v_0, . . . , v_{n-1}}$ and $E = {(v_i, v_j), for |i-j| in {a_1, . . . , a_k}}$. In this paper, we characterize bipartite finite Toeplitz graphs with $k <= 3$. As a consequence, using previous results, we get a complete characterization for the chromatic number of such graphs. In addition, we characterize some classes of bipartite Toeplitz graphs with $k >= 4$.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.
