Graph coloring §

Alcune definizioni §

Def Una colorazione di un Grafo semplice $G$ è una funzione $f:V(G)\mapsto C$ che mappa i vertici del grafo in un insieme finito $C$, con la proprietà che se $\{u,v\}\in E(V)$, ovvero due vertici sono adiacenti, allora $f(u)\ne f(v)$, hanno un “colore” diverso.

Def Il numero cromatico di una grafo $\chi (G)$ è definito come la minima cardinalità possibile di una colorazione del grafo $G$:

$$\chi (G):=\min \{|f(V(G))|:f\text{ colorazione di }G\}$$

Osservazione Se $F\subseteq G$ è sotto grafo, allora $\chi (F)\le \chi (G)$. Infatti la restrizione della colorazione di $G$ ai vertici di $F$ è ancora una colorazione per $F$, ma il viceversa non è sempre vero. Quindi il minimo è fatto su un insieme più grande. Data una colorazione ottimale $h$ di $G$ e la sua restrizione:

$$\chi (F)\le |h(V(F))|\le |h(V(G))|=\chi (G)$$

Relazioni con gli altri invarianti §

1. Clique Se un grafo $G$ ha numero di clique $\omega (G)=k$, ovvero contiene una $k$-clique, il suo numero cromatico dovrà essere maggiore di $k$:

$$\omega (G)\le \chi (G)$$

infatti ho bisogni di $k$ colori per colorare $K_k$, che è sottografo di $G$, quindi per l’osservazione precedente

$$\omega (G)=n=\chi (K_k)\le \chi (G)\square$$

2. Stabile O indipendet set. Il numero di stabilità di un grafo $\alpha (G)$ è la massima cardinalità di un indipendet set contenuto in $G$. Vale $\alpha (G)=\omega (\overline{G})$. Dalla definizione di colorazione, segue che le preimmagini della colorazione fissato un colore siano un insieme stabile. Quindi una colorazione è una decomposizione di un grafo in insiemi stabili.

Proposizione Sia $\alpha (G)$ il numero di stabilità del grafo $G$ (l’ordine dell’insieme stabile massimo che contiene), allora vale il seguente lower-bound per il numero cromatico di $G$:

$$\frac{|V(G)|}{\alpha (G)}\le \chi (G)$$

($\alpha (G)\ge 1$ per ogni grafo non vuoto). Dim Sfrutto il fatto che la preimmagine di una colorazione è un insieme stabile, e tutte le preimmagini sono una partizione dei veritici:

$$V(G)={\dot{\bigcup }}_{c\in C}{f}^{-1}(c)|V(G)|=\sum _{i=1}^{\chi (G)}|f^{-1}(c_i)|\le \chi (G)\alpha (G)\square$$

Osservazione Se ho una $n$-partizione in stabili del grafo $G$, allora $\chi (G)\le n$.

Si può ottenere un upper bound che riguarda il numero di stabilità: Proposition Let $G$ be a graph of order $n$, then

$$\chi (G)\le 1+n-\alpha (G)$$

Proof Let $S\subseteq G$ be a maximal indipendent set of $G$. We can assign it the same color. For the remaining $n-\alpha (G)$ vertices, assign different colors. This is a valid coloration, so

$$\chi (G)\le 1+n-\alpha (G)\square$$

Algoritmo greedy e upper bound §

Da un algoritmo greedy, che procede colorando uno stabile e poi rimuovendolo dal grafo, si ottiene l’upper bound:

$$\chi (G)\le d(G)+1$$

Lemma Sia $V=V_1\dot{\cup }{V}_2$ e $G_i=G[V_i]$ i due grafi indotti. Allora:

$$\chi (G)\le \chi (G_1)+\chi (G_2)$$

Dim “Incollo” le due colorazioni, creando una colorazione valida sul grafo di partenza:

$$f:V_1\dot{\cup }{V}_2\mapsto C_1\cup C_2$$

suppongo di avere colori diversi, ovvero $C_1\cap C_2=\varnothing$.

$$f(v):=\{\begin{array}{l}{f}_1(v)\text{ se }v\in V_1\\ f_2(v)\text{ se }v\in V_2\end{array}$$

$f$ è una colorazione di $G$ con $|f(V)|=\chi (G_1)+\chi (G_2)$, ma non è necessariamente ottima. $\square$

Dim Dimostriamo l’upperbound per induzione sul grado del grafo. Per $d=0$ $G$ è fatto di punti isolati, è $1$-colorabile:

$$\chi (G)=1\le 0+1$$

Sia $G$ un grafo di grado $k<d$, allora $\chi (G)\le k+1\le d$. Facciamo vedere che se $d(G)=d$ allora vale $\chi (G)\le d+1$.

L’idea è costruire la colorazione in modo greedy:

1. Coloro un vertice $v$;
2. Costruisco uno stabile massimale $S$ che contiene $v$ e lo coloro del colore di $v$.
3. Rimuovo tutto lo stabile, cambio colore e ripeto.

Claim $d(G\setminus S)<d(G)=d$ Il grado di ogni vertice in $G\setminus S$ cala di almeno uno, altrimenti significa che non erano collegati a nessun vertice di $S$, quindi sarebbero stati inclusi nello stabile. $\square$

Ho fatto, questo significa che posso usare l’ipotesi induttiva su $G\setminus S$:

$$\chi (G\setminus S)\le k+1<d+1$$

ma $G\setminus S$ ed $S$ sono una bipartizione di $G$, quindi vale $\chi (G)\le \chi (S)+\chi (G\setminus S)$, la essendo $S$ uno stabile è $1-$colorabile. Quindi:

$$\chi (G)\le \chi (G\setminus S)+1\le k+2<d+2$$

che è equivalente a

$$\chi (G)\le d+1\square$$

Colorability and complementary graph §

Proposition Let $G$ be a graph of order $n$ and $\overline{G}$ its complementary graph. Then

1. $n\le \chi (G)\chi (\overline{G})$,
2. $2\sqrt{n}\le \chi (G)+\chi (\overline{G})$.

Proof of 1 Use the lower bounds $\frac{n}{\alpha (\overline{G})}\le \chi (\overline{G})$ and $\omega (G)\le \chi (G)$, and the fact that $\alpha (\overline{G})=\omega (G)$. $\square$ Proof of 2 Just add the two lower bounds:

$$\frac{n}{\omega (G)}+\omega (G)\le \chi (G)+\chi (\overline{G})$$

the function on the left side is

$$2\sqrt{n}\le \frac{n+x^2}{x}$$

and has a point of minimum when $\omega (G)=\sqrt{n}$, with value $2\sqrt{n}$. $\square$

Morale sul numero cromatico §

$$1\le \omega (G)\le \chi (G)\le d(G)+1\le |V(G)|$$

Osservazione Due grafi dove si raggiunge l’upper bound $d(G)+1$ sono ovviamente i grafi completi $K_n$ e i cicli di ordine dispari $C_{2n+1}$.

Question Sotto quali ipotesi posso invece avere $\chi (G)\le d(G)$? Il teorema di Teorema di Brooks risponde a questa domanda.