Publication Date:
2000
Short description:
On the Lovasz number of certain circulant graphs / V., Brimkov; B., Codenotti; V., Crespi; Leoncini, Mauro. - STAMPA. - 1767:(2000), pp. 291-305. ( N/A N/A N/A) [10.1007/3-540-46521-9_24].
abstract:
The theta function of a graph, also known as the Lov?sz number, hasthe remarkable property of being computable in polynomial time,despite being "sandwiched" between two hard to compute integers,i.e., clique and chromatic number. Very little is known about theexplicit value of the theta function for special classes of graphs. Inthis paper we provide the explicit formula for the Lov?sz number ofthe union of two cycles, in two special cases, and a practicallyefficient algorithm, for the general case.
Iris type:
Relazione in Atti di Convegno
Keywords:
graph algorithms; lovasz number
List of contributors:
V., Brimkov; B., Codenotti; V., Crespi; Leoncini, Mauro
Book title:
N/A
Published in: