Coloring Circulant Graphs (Abstract/Poster in atti di convegno)

Type
Label
  • Coloring Circulant Graphs (Abstract/Poster in atti di convegno) (literal)
Anno
  • 2005-01-01T00:00:00+01:00 (literal)
Alternative label
  • NICOLOSO Sara; PIETROPAOLI Ugo (2005)
    Coloring Circulant Graphs
    in XXVI Annual Conference of the Italian Operational Research Society, AIRO 2005, Camerino (MC), Italia, Settembre 2005
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • NICOLOSO Sara; PIETROPAOLI Ugo (literal)
Note
  • Abstract (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
  • NICOLOSO Sara, IASI-CNR; PIETROPAOLI Ugo, Univesità di Roma Tor Vergata (literal)
Titolo
  • Coloring Circulant Graphs (literal)
Abstract
  • Let n, a and b be positive integers. By Cn(a,b)=(V,E) we shall denote the graph on n = |V| vertices whose edge set is E = {(i,(i+a) mod n), (i,(i-a) mod n), (i,(i+b) mod n), (i,(i-b) mod n), for i = 0, ..., n-1}. The problem we deal with is the following Given three positive integers n, a and b, such that the (simple) graph Cn(a,b) is 4-regular and connected Find an assignment of colors to the vertices of Cn(a,b) Such That adjacent vertices receive different colors and the number ?(Cn(a,b)) of used colors is minimized. We discuss some simple isomorphism conditions, we characterize ?(Cn(a,b)) on the basis of simple relations between n, a, b, and propose linear algorithms for determining optimum colorings. Effective mathematical models are proposed, and the structure of some characteristic cycles of the graphs is investigated. (literal)
Prodotto di
Autore CNR
Insieme di parole chiave

Incoming links:


Autore CNR di
Prodotto
Insieme di parole chiave di
data.CNR.it