Seminario Interdipartimentale di Algoritmica
 
 
 

Dipartimento di Informatica e Sistemistica - DIS
via Salaria 113, II piano
Aula C2

Abstract:
Non e esagerato dire che i due invarianti piu studiati di un grafo siano il suo numero di clique (omega) e il suo numero cromatico (chi). Quando questi non coincidono, e di consequenza, la capacita di Shannon del grafo risulta, in generale, un punto inafferrabile all'interno dell'intervallo [omega, chi], allora, nel tentativo di "catturarlo", sembra utile individuare altri invarianti, contenuti nello stesso intervallo.

In questo seminario si introducono tali invarianti, si studiano le loro relazioni, si esibisce un'arbitrario divario tra i loro valori, e si studiano i corrispondenti valori asintotici per grafi potenza. Poiche' i nuovi invarianti coinvolgono il numero di colori presenti sugli intorni dei vertici, essi possono essere generalizzati in un modo naturale a grafi diretti con l'obiettivo di limitare la loro capacita di Sperner.

I nuovi risultati sono congiunti con Concetta Pilotto (Roma) e Gabor Simonyi (Budapest).