6.5 Χρωματισμοί

6.5.1 Γενικά

Ορισμός 6.7   Ενας χρωματισμός ενός συνόλου $A$ με $r$ χρώματα θα είναι μια συνάρτηση

$$\chi: A \to [r] = {\left\{{1,\ldots,r}\right\}}.$$

Αντί να αναφερόμαστε δηλ. στα χρώματα με άσπρο, κόκκινο, κλπ, τα αριθμούμε απλώς και προσδιορίζουμε το πόσα είναι.

Ορισμός 6.8   (Χρωματισμός κορυφών, χρωματισμός ακμών) Εστω $G=(V,E)$ ένα γράφημα. Ενας χρωματισμός κορυφών του $G$ με $r$ χρώματα είναι μια συνάρτηση $\chi:V\to[r]$ τέτοια ώστε

$$\forall u,v \in V: u \sim v \Longrightarrow \chi(u) \neq \chi(v).$$

Κορυφές που ενώνονται με ακμές δηλ. πρέπει να πάρουν αναγκαστικά διαφορετικό χρώμα.

Ομοίως χρωματισμός ακμών του $G$ με $r$ χρώματα είναι συνάρτηση $\chi:E\to[r]$ τ.ώ.

$$\forall e, e' \in E: e \sim e' \Longrightarrow \chi(e) \neq \chi(e').$$

Δηλ. ακμές που έχουν κοινή κορυφή πρέπει να πάρουν διαφορετικό χρώμα.

Προφανώς μπορούμε πάντα να χρωματίσουμε τις κορυφές ενός γραφήματος με $n$ κορυφές χρησιμοποιώντας $n$ χρώματα, ένα για κάθε κορυφή. Το ζητούμενο είναι αν μπορούμε να κάνουμε το ίδιο με λίγα χρώματα.

Ορισμός 6.9   (Χρωματικός αριθμός) Ο χρωματικός αριθμός $\chi(G)$ ενός γραφήματος $G$ είναι ο ελάχιστος φυσικός $r$ για τον οποίο υπάρχει ένας χρωματισμός κορυφών του $G$.

Παράδειγμα 6.7   Το πλήρες γράφημα με $n$ κορυφές, $K_n$, χρειάζεται $n$ χρώματα ( $\chi(K_n) = n$), ενώ το κενό γράφημα χρειάζεται ένα μόνο ( $\chi(E_n)=1$).

Άσκηση 6.19   Δείξτε ότι ο κύκλος $C_n$ έχει χρωματικό αριθμό $\chi(C_n) = 2$ αν $n$ άρτιος και $3$ αν $n$ περιττός.

6.5.2 Εκτιμήσεις για τον χρωματικό αριθμό

Θα δώσουμε ένα άνω φράγμα για το $\chi(G)$ σε σχέση με το μέγιστο βαθμό των κορυφών του και ένα κάτω φράγμα σε σχέση με το πόσο μεγάλα πλήρη υπογραφήματα έχει. Αρχίζουμε με το κάτω φράγμα που είναι προφανές.

Θεώρημα 6.7   Αν το $G$ έχει ένα υπογράφημα ισομορφικό με το $K_s$ τότε $\chi(G) \ge s$.

Απόδειξη. Αν δηλ. το $G$ έχει $s$ κορυφές που όλες συνδέονται μεταξύ τους τότε χρειαζόμαστε τουλάχιστον $s$ χρώματα για να χρωματίσουμε τις κορυφές του $G$, που είναι φανερό. $\qedsymbol$

Το άνω φράγμα είναι πιο ενδιαφέρον.

Θεώρημα 6.8   Αν όλες οι κορυφές του $G$ έχουν βαθμό $\le d$ τότε $\chi(G) \le d+1$.

Απόδειξη. Με επαγωγή ως προς το πλήθος κορυφών $n$ του $G$. Για $n=1$ είναι φανερό.

Εστω $G$ ένα γράφημα με $n$ κορυφές και μέγιστο βαθμό $d$ και έστω $u$ οποιαδήποτε κορυφή του $G$. Ορίζουμε $G'$ να είναι το υπογράφημα του $G$ που προκύπτει αν διαγράψουμε την κορυφή $u$ και όλες τις ακμές της. Αυτό έχει $n-1$ κορυφές και μέγιστο βαθμό όχι μεγαλύτερο από πριν, άρα $\le d$. Συνεπώς, από την επαγωγική μας υπόθεση, $\chi(G') \le d+1$, δηλ. μπορούμε να χρωματίσουμε τις κορυφές του $G'$ με τα χρώματα $1,2,\ldots,d+1$.

Εστω τώρα οι γείτονες της $u$ στο $G'$, $u_1,\ldots,u_k$, με $k\le d$. Αρα υπάρχει κάποιο από τα χρώματα $1,2,\ldots,d+1$ που δεν έχει χρησιμοποιηθεί στο χρωματισμό των $u_1,\ldots,u_k$, έστω το χρώμα $c$. Χρωματίζουμε τότε την κορυφή $u$ με το χρώμα $c$ και κρατάμε τα χρώματα των υπολοίπων κορυφών όπως στο χρωματισμό του $G'$. Εχουμε έτσι κατασκευάσει ένα χρωματισμό του $G$ με $d+1$ χρώματα. $\qedsymbol$

Άσκηση 6.20   Αν $\chi(G)=k>1$ δείξτε ότι το σύνολο κορυφών $V$ του $G$ μπορεί να διαμεριστεί σε δύο σύνολα $V = V_1 \cup V_2$ έτσι ώστε, αν $G_i$ είναι το υπογράφημα του $G$ που επάγεται από τις κορυφές $V_i$.$i=1,2$, τότε να ισχύει

$$\chi(G_1) + \chi(G_2) = k.$$

Άσκηση 6.21   Ας είναι $G_1, G_2$ δύο γραφήματα πάνω στο ίδιο σύνολο κορυφών $V$. Δείξτε ότι

$$\chi(G_1 \cup G_2) \le \chi(G_1) \chi(G_2).$$

Εδώ με $G_1 \cup G_2$ συμβολίζουμε το γράφημα με σύνολο κορυφών $V$ και με ακμές τις ακμές του $G_1$ μαζί με τις ακμές του $G_2$.

Άσκηση 6.22   Αν σε ένα γράφημα $G$ με $n$ κορυφές υπάρχουν $s$ κορυφές που δε συνδέονται καθόλου μεταξύ τους δείξτε ότι

$$\chi(G) \le n-s+1.$$

Άσκηση 6.23  

Σχήμα 6.9: Κύκλοι στο επίπεδο όπως στην Άσκηση 6.23.

Στο επίπεδο εχουμε $k$ ίσους κύκλους οι οποίοι δεν τέμνονται ανά δύο αλλά μπορούν να εφάπτονται (εξωτερικά, αφού είναι ίσοι). Δείξτε ότι μπορούμε να χρωματίσουμε τα εσωτερικά των κύκλων αυτών με το πολύ 4 διαφορετικά χρώματα με τρόπο τέτοιο ώστε αν δύο κύκλοι εφάπτονται τότε αυτοί να έχουν διαφορετικό χρώμα στο εσωτερικό τους.

Υπόδειξη: Επαγωγή ως προς $k$. Εστιάσετε την προσοχή σας σε ένα κύκλο με ελάχιστη τετμημένη του κέντρου του.