Colorazioni di archi e vertici

[giulylanza06]

00

[orsoulx]

Il minimo numero di colori sufficienti per eseguire la colorazione richiesta è $ 2 \lfloor n/2 \rfloor+1 $

Se il grafo con $ n $ vertici è completo da ogni vertice escono $ n-1 $ archi e per colorare in maniera diversa il vertice e gli archi servono almeno $ n $ colori.
Se $ n $ è dispari una colorazione possibile si può ottenere associando a ciascun colore una delle classi di resto modulo $ n $.
Considerando la tabellina dell'addizione modulo $ n $ si nota che la diagonale principale contiene tutti gli $ n $ numeri e, modificando le sole intestazioni delle righe e delle colonne in modo che tali intestazioni coincidano con il numero che si trova sulla diagonale principale, si ottiene una tabella che fornisce per ogni coppia di vertici il 'colore' da assegnare all'arco che li unisce rispettando le consegne.
Quando invece $ n $ è pari ogni colore può essere usato solo $ (n-2)/2 $ [modificato perché avevo dimenticato il fratto 2] volte per colorare gli archi e questo non può bastare per completare la colorazione. Si può però utilizzare la tabella vista prima per $ n+1 $ vertici, usando pertanto un 'colore' in più.

Ciao

[giammaria2]

Secondo me invece il minimo numero di colori sufficienti per eseguire la colorazione richiesta è comunque $n$; corrisponde alla soluzione di orsoulx nel caso di $n$ dispari, mentre per $n$ pari la sua soluzione è $n+1$.

Il problema è rappresentabile con una matrice quadrata e simmetrica, in cui il generico $a_(ij)$ è il colore del tratto collegante i punti $i,j$ (se distinti), mentre $a_(ii)$ è il colore del punto $i$.
Le ipotesi richiedono che in ogni riga o colonna siano presenti $n$ colori distinti e questo è ottenibile in molti modi, fra cui una permutazione ciclica. La esemplifico con la seguente matrice, in cui $n=4$ e $c_k$ indica il k-esimo colore:
$((c_1,c_2,c_3,c_4),(c_2,c_3,c_4,c_1),(c_3,c_4,c_1,c_2),(c_4,c_1,c_2,c_3))$
Ci sono vertici con lo stesso colore, ma le ipotesi non lo vietano.

[orsoulx]

@giammaria:
hai ragione, non so perché ma volevo colorare i vertici usando tutti i colori: già con 2 vertici mi servivano 3 colori.