Affordable Access

Publisher Website

Coloring Toeplitz graphs

Authors
Journal
Electronic Notes in Discrete Mathematics
1571-0653
Publisher
Elsevier
Publication Date
Volume
36
Identifiers
DOI: 10.1016/j.endm.2010.05.072
Keywords
  • Toeplitz Graph
  • Coloring
  • Bipartiteness
  • Chromatic Number

Abstract

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 | ∈ { 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.

There are no comments yet on this publication. Be the first to share your thoughts.

Statistics

Seen <100 times
0 Comments

More articles like this

Coloring Planar Toeplitz Graphs

on Electronic Notes in Discrete M... Jan 01, 2000

Coloring planar Toeplitz graphs and the stable set...

on Discrete Mathematics Jan 01, 2004

On Total Colorings of Graphs

on Journal of Combinatorial Theor... Jan 01, 1993
More articles like this..