Sempre roba easy

[NicolasRossi]

Siano $G_1,G_2,G_3$ tre grafi finiti aventi gli stessi nodi. Supponendo che i nodi di $G_1$ si possano colorare con $2$ colori in modo che nessun vertice adiacente abbia lo stesso colore e che, $G_2$ si possa colorare con $3$ colori (sempre rispettando le ipotesi fatte su $G_2$) e che i nodi $G_3$ si possano colorare con $4$ colori, dimostrare che $G$ si può colorare con $24$ colori. (Chiamo $G$ il grafo con gli stessi nodi di $G_1,G_2$ e $G_3$ e come archi, l'insieme dato dall'unione degli archi di $G_1,G_2$ e $G_3$.)

[xXStephXx]

Per prima cosa si può dimostrare che dati due grafi finiti con gli stessi nodi $A$ e $B$, dove $A$ è colorabile con $a$ colori e $B$ con $b$ colori, il grafo ottenuto dalla loro unione è colorabile con $ab$ colori.
Qua basta prendere una matrice $C$ di $a$ righe e $b$ colonne contenente $ab$ colori distinti. Chiamo $a_i$ i colori usati per colorare $A$ con $0<i\leq a$ e $b_j$ i colori usati per colorare $B$ con $0<j \leq b$.
Faccio l'unione tra i due grafi e per ogni vertice $X$ applico questo procedimento: se $X$ in $A$ era colorato col colore $a_i$ e in $B$ era colorato con $b_j$ adesso lo coloro con $C_{i,j}$. Questa colorazone soddisfa sicuramente la tesi. Infatti se per assurdo due vertici adiacenti avessero lo stesso colore, allora avevano lo stesso colore sia in $A$, sia in $B$ e di conseguenza non erano collegati nè in $A$ nè in $B$, ma allora come fanno ad essere collegati con l'unione? assurdo


Di conseguenza $G_1 \cup G_2$ può essere colorato con $6$ colori e $(G_1 \cup G_2) \cup G_3 = G_1 \cup G_2 \cup G_3$ può essere colorato con $24$ colori.

Per caso esiste un modo per stimare il numero di colori necessari a priori?

[Troleito br00tal]

Con $23$ colori si può fare?

[xXStephXx]

Con $23$ non sempre. Si può ad esempio costruire un caso in cui non si può fare.
Basta dimostrare che si può realizzare un $24-agono$ completo che chiaramente richiede almeno $24$ colori.
Quindi prendo $24$ nodi del grafo e li numero da $1$ a $24$.
Ora in $G_1$ coloro con $a_1$ i nodi di posto dispari e con $a_2$ quelli di posto pari. Dopodichè faccio tutti i collegamenti che posso fare. Rimangono scollegati i nodi congrui tra loro modulo $2$.
In $G_2$ coloro con $b_1$ tutti quelli del tipo $6k+1, 6k+2$ con $b_2$ tutti quelli del tipo $6k+3, 6k+4$ con $b_3$ tutti quelli $6k+5, 6k+6$.
Faccio tutti i collegamenti che posso fare.
Ora da $G_2 \cup G_1$ ottengo che rimangono scollegati solo quelli congrui tra loro modulo $6$.
Su $G_3$ coloro con $c_1$ quelli da $1$ a $6$ con $c_2$ quelli da $7$ a $12$ con $c_3$ da $13$ a $18$ con $c_4$ da $19$ a $24$.
Collego tutti quelli che posso collegare. E ora dall'unione dei tre grafi viene fuori un $24-agono$ completo.