Χρωματισμός ακμών

Στη Θεωρία γράφων ο χρωματισμός ακμών ενός γραφήματος είναι η τοποθέτηση "χρωμάτων" στα άκρα του γραφήματος, έτσι ώστε να μην υπάρχουν δύο γειτονικές ακμές με το ίδιο χρώμα. Για παράδειγμα, η εικόνα στα δεξιά είναι ο χρωματισμός ακμών ενός γραφήματος με κόκκινο, μπλε και πράσινο χρώμα. Ο χρωματισμός ακμών είναι ένας από τους ποικίλους τρόπους χρωματισμού γραφημάτων. Το πρόβλημα χρωματισμού ακμών διερευνά αν είναι εφικτό να χρωματίσουμε τις ακμές ενός δοθέντος γραφήματος χρησιμοποιώντας μέχρι κ διαφορετικά χρώματα, όπου κ μια δεδομένη τιμή, ή με όσο το δυνατόν λιγότερα χρώματα. Ο ελάχιστος αριθμός χρωμάτων για τις ακμές ενός δοθέντος γραφήματος ονομάζεται χρωματικός δείκτης του γραφήματος. Για παράδειγμα, οι ακμές του γραφήματος της εικόνας μπορούν να χρωματιστούν με τρία χρώματα αλλά όχι με δύο,οπότε το εμφανιζόμενο γράφημα έχει χρωματικό δείκτη ίσο με τρία.

Χρωματισμός ακμών με 3 χρώματα του Desargues Graph.

Σύμφωνα με το θεώρημα του Vizing, ο απαιτούμενος αριθμός χρωμάτων για το χρωματισμό ενός απλού γραφήματος είναι σε μέγιστο βαθμό είτε Δ ή Δ+1. Σε κάποια γραφήματα, όπως στα διμερή ή στα επίπεδα γραφήματα υψηλού βαθμού,ο αριθμός των χρωμάτων είναι πάντα Δ , και για τα πολλαπλά γραφήματα ο αριθμός των χρωμάτων μπορεί να είναι ως και 3Δ/2. Υπάρχουν πολυωνυμικοί αλγόριθμοι για το βέλτιστο χρωματισμό διμερών γραφημάτων και το χρωματισμό απλών μη διμερών γραφημάτων οι οποίοι χρησιμοποιούν μέχρι και Δ+1 χρώματα. Ωστόσο, το γενικό πρόβλημα ανεύρεσης του βέλτιστου χρωματισμού ακμών είναι το NP-complete και ακόμα και οι ταχύτεροι γνωστοί αλγόριθμοι χρειάζονται πολύ χρόνο για την αντιμετώπισή του. Έχουν μελετηθεί πολλές παραλλαγές του προβλήματος χρωματισμού ακμών, στις οποίες οι αναθέσεις χρωμάτων στα άκρα/ακμές πρέπει να πληρούν όρους/συνθήκες μη γειτνίασης (στις οποίες δεν μπορούν δύο κοντινές ακμές να έχουν το ίδιο χρώμα). Ο χρωματισμός ακμών έχει εφαρμογή σε προβλήματα προγραμματισμού και στην εκχώρηση συχνοτήτων για δίκτυα οπτικών ινών.

Παραδείγματα

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

Γεωμετρική κατασκευή χρωματισμού ακμών με 7 χρώματα ενός κανονικού γραφήματος K₈. Κάθε μία από τις χρωματικές κλάσεις περιέχει μια ακμή η οποία ξεκινά από το κέντρο του πολυγώνου και καταλήγει σε μια κορυφή του,και 3 επιπλέον ακμές κάθετες σε αυτήν.

Ένα πλήρες γράφημα K_n με n μπορεί να έχει τις ακμές του χρωματισμένες με n − 1 χρώματα όταν το n είναι ζυγός αριθμός, αυτή είναι η ειδική περίπτωση του θεωρήματος του Baranyai. Ο Soifer (2008) παρείχε την ακόλουθη την γεωμετρική κατασκευή χρωμάτων στην περίπτωση αυτή: τοποθέτησε n σημεία στις κορυφές και το κέντρο ενός πολυγώνου (n − 1) ακμών. Για κάθε χρωματική κλάση, συμπεριέλαβε τις ακμές με το ένα άκρο στο κέντρο του πολυγώνου και το άλλο σε μια από τις κορυφές του, και επίσης όλες τις κάθετες ακμές που συνδέουν ζεύγη κορυφών του πολυγώνου. Ωστόσο,όταν το n είναι περιττός αριθμός, χρειάζονται n χρώματα, όπου κάθε χρώμα μπορεί να χρησιμοποιηθεί μόνο για (n − 1)/2 κορυφές δηλαδή για το 1/n του συνόλου.

Πολλοί συγγραφείς έχουν μελετήσει το χρωματισμό ακμών για γραφήματα περιττών ακμών ως εξής: στα n-κανονικά γραφήματα οι κορυφές αντιπροσωπεύουν ομάδες από n − 1 παίκτες που επιλέγονται από ένα σύνολο 2n - 1 παικτών. Στην περίπτωση αυτή οι ακμές αντιπροσωπεύουν πιθανές αντιστοιχίσεις αυτών των ομάδων (με έναν παίκτη να μένει εκτός σαν να "επιβλέπει" τον αγώνα). Η περίπτωση όπου το n = 3 gείναι γνωστή ως το γράφημα Petersen. Όπως εξηγεί ο Biggs (1972) στο πρόβλημα (για n = 6), οι παίκτες αναζητούν την οργάνωση αυτών των αντιστοιχίσεων έτσι ώστε κάθε παίκτης να παίζει τα 6 παιχνίδια του σε διαφορετικές μέρες της εβδομάδας, με τις Κυριακές να είναι αργίες για όλες τις ομάδες. Δηλαδή, διατυπώνοντας το μαθηματικά, αναζητούν το χρωματισμό 6 ακμών του κανονικού περιττού γραφήματος O₆. Όταν το n είναι 3, 4, ή 8, ο χρωματισμός ακμών του O_n χρειάζεται n + 1χρώματα, ενώ όταν είναι 5, 6 ή 7 χρειάζονται μόνο n χρώματα.

Ορισμοί

Όπως και ο χρωματισμόs κορυφών, ο χρωματισμός ακμών ενός γραφήματος,όταν αναφέρεται χωρίς καμία διευκρίνηση,θεωρείται πάντα ότι είναι ο ορθός δηλαδή ότι δεν υπάρχουν γειτονικές ακμές με το ίδιο χρώμα. Εδώ,δύο ακμές λέγονται γειτονικές όταν έχουν μια κοινή κορυφή.Ο χρωματισμός ακμών ενός γραφήματος G μπορεί επίσης να θεωρηθεί ισοδύναμος με το χρωματισμό κορυφών του γραμμικού γραφήματος L(G), δηλαδή αυτού που διαθέτει μια κορυφή για κάθε άκρο του G και ένα άκρο για κάθε ζευγάρι γειτονικών κορυφών του G.

Ο σωστός χρωματισμός ακμών με k διαφορετικά χρώματα ονομάζεται k-χρωματισμός ακμών. Ένα γράφημα στο οποίο μπορούμε να τοποθετήσουμε το σωστό αριθμό k χρωμάτων ονομάζεται k-χρωματιζόμενο γράφημα. Ο ελάχιστος αριθμός χρωμάτων που απαιτείται για τον ορθό χρωματισμό ενός γραφήματος G λέγεται χρωματικός αριθμός και συμβολίζεται χ′(G). Ο χρωματισμός αριθμός συμβολίζεται πολλές φορές χρησιμοποιώντας δείκτη ωσ εξής χ₁(G) και εδώ ο δείκτης 1 αντιστοιχεί σε ακμές μίας διάστασης. Ένα γράφημα είναι k-χρωματιζόμενο αν ο χρωματικός του δείκτης είναι ακριβώς k. Ο χρωματικός δείκτης δεν πρέπει να συγχέεται με τον χρωματικό αριθμό χ(G) ή χ₀(G), που είναι ο ελάχιστος αριθμός απαιτούμενων χρωμάτων για τον ορθό χρωματισμό κορυφών του G.

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

Συσχέτιση με το ταίριασμα

Αυτό το κανονικό επίπεδο γράφημα έχει 16 κορυφές και 24 ακμές, αλλά μόνο 7 ακμές σε κάθε τέλειο ταίριασμα. Γι'αυτό απαιτούνται μόνο 4 χρώματα για οποιασδήποτε μορφής χρωματισμό του.

Ένα ταίριασμα(matching) σε ένα γράφημα G είναι ένα σύνολο ακμών,με την ιδιότητα ότι κάθε κόμβος εμφανίζεται το πολύ σε μια ακμή του. Ένα τέλειο ταίριασμα είναι αυτό στο οποίο κάθε κόμβος εμφανίζεται σε μία μόνο ακμή και ένα ανώτατου ταίριασμα(maximum matching) είναι εκείνο που περιέχει όσο το δυνατόν περισσότερες ακμές.Δηλαδή, ένας σωστός χρωματισμός ακμών είναι το ίδιο πράγμα με τη διαμέριση του γραφήματος σε ασυνεχή ταιριάσματα.

Αν το μέγεθος ενός ανώτατου ταιριάσματος σε ένα δοθέν γράφημα είναι μικρό,τότε θα χρειαστούν πολλά ταιριάσματα ώσπου να καλυφθούν όλα τα άκρα του γραφήματος.Ειδικότερα, με βάση αυτή τη λογική το γράφημα έχει m ακμές συνολικά,και αν το πολύ β από αυτά ανήκουν στο ανώτατο ταίριασμα,τότε για κάθε χρωματισμό ακμών του γραφήματος πρέπει να χρησιμοποιηθούν τουλάχιστον m/β διαφορετικά χρώματα.Για παράδειγμα,το επίπεδο γράφημα 16-κορυφών που φαίνεται στην εικόνα έχει m = 24 ακμές.Σε αυτό το γράφημα,δεν υπάρχει τέλειο ταίριασμα; αν η κορυφή του κέντρου αποτελεί κόμβο στο ταίριασμα,οι υπόλοιπες κορυφές που δεν μετέχουν στο ταίριασμα μπορούν μπορούν να ομαδοποιηθούν σε τρια διαφορετικά σύνολα με τέσσερις,πέντε και πέντε κορυφές και τα υποσύνολα με μονό αριθμό κορυφών δεν μπορούν να σχηματίσουν τέλειο ταίριασμα. Ωστόσο,στο γράφημα υπάρχει ανώτατο ταίριασμα με 7 ακμές,έτσι ισχύει β = 7. Ως εκ τούτου, ο αριθμός των χρωμάτων που απαιτούνται για το χρωματισμό των ακμών είναι τουλάχιστον 24/7, και δεδομένου ότι ο αριθμός των χρωμάτων θα πρέπει να είναι ακέραιος,είναι τουλάχιστον τέσσερα. Για ένα κανονικό γράφημα βαθμού k στο οποίο δεν υπάρχει τέλειο ταίριασμα,αυτό το κατώτερο όριο μπορεί να χρησιμοποιηθεί για να δείξει ότι απαιτούνται τουλάχιστον k + 1 χρώματα.Ειδικότερα, αυτό είναι αληθές για ένα κανονικό γράφημα με περιττό αριθμό κορυφών (όπως στα odd complete graphs ). Σ'αυτά τα γραφήματα,σύμφωνα με το handshaking lemma,το k πρέπει να είναι ζυγός αριθμός. Ωστόσο,η ανισότητα χ′ ≥ m/β δεν ορίζει πλήρως το χρωματικό δείκτη για κάθε κανονικό γράφημα,διότι υπάρχουν κανονικά γραφήματα στα οποία υπάρχει τέλειο ταίριασμα αλλά δεν έχουν k χρωματισμένες ακμές.Για παράδειγμα,το γράφημα Petersen είναι κανονικό,με m = 15 και β = 5 ακμές στο τέλειο ταίρασμα αλλά δεν έχει χρωματισμό ακμών με 3 χρώματα.

Συσχέτιση με το βαθμό

Θεώρημα του Vizing

Ο χρωματικός αριθμός ενός γραφήματος G είναι πολύ στενά συνδεδεμένος με τον μέγιστο βαθμό Δ(G) , τον μεγαλύτερο αριθμό των άκρων σε οποιοδήποτε μεμονωμένη κορυφή του G . Σαφώς, χ′(G) ≥ Δ(G), αν για Δ διαφορετικές ακμές που καταλήγουν στην ίδια κορυφή ν, όλες αυτές οι ακμές να αποδίδονται με διαφορετικά χρώματα η μία από την άλλη, και αυτό μπορεί να συμβεί μόνο αν υπάρχουν τουλάχιστον Δ διαθέσιμα χρώματα.Σύμφωνα με το θεώρημα του Vizing(που πήρε το όνομά του από τον Vadim G. Vizing ο οποίος το διατύπωσε το 1964) αυτό το όριο χρωμάτων είναι πολύ περιορισμένο: δηλαδή για κάθε γράφημα ο χρωματικός δείκτης των ακμών είναι είτε Δ(G) είτε Δ(G) + 1.Όταν ισχύει χ′(G) = Δ(G), το G λέγεται γράφημα τάξης 1, ενώ αλλιώς γράφημα τάξης 2.

Κάθε διμερές γράφημα είναι τάξης 1 και σχεδόν όλα τα τυχαία γραφήματα είναι επίσης τάξης 1. . Ωστόσο, η εξακρίβωση για το αν ένα αυθαίρετο γράφημα είναι τάξης 1 πραγματοποιείται με το NP-complete .

Ο Vizing (1965) απέδειξε ότι τα επίπεδα γραφήματα με μέγιστο βαθμό από 8 και πάνω είναι τάξης 1 και εικάζοταν ότι το ίδιο ισχύει και για τα επίπεδα γραφήματα με μέγιστο βαθμό 6 ή 7.Παρόλα αυτά,υπάρχουν επίπεδα γραφήματα με μέγιστο βαθμό που κυμαίνεται ανάμεσα στο 2 και το 5, τα οποία είναι γραφήματα τάξης 2. Η εικασία έκτοτε έχει αποδειχθεί για γραφήματα με μέγιστο βαθμό επτά. Τα μη συνεκτικά επίπεδα κυβικά γραφήματα είναι όλα τάξης 1 και αυτό αποτελεί μια ισοδύναμη έκφραση του θεωρήματος των τεσσάρων χρωμάτων.

Κανονικά γραφήματα

Η 1-παραγοντοποίηση ενός k-κανονικού γραφήματος, δηλαδή ο διαμελισμός των ακμών του γραφήματος σε τέλεια ταιριάσματα, είναι το ίδιο με το χρωματισμό k-ακμών του γραφήματος. Αυτό συμβαίνει γιατί, ένα κανονικό γράφημα έχει μια 1-παραγοντοποίηση αν και μόνο εάν είναι πρώτης τάξης. Μία ειδική περίπτωση είναι ο χρωματισμός τριών ακμών ενός κύβου (3-κανονικό) γραφήματος και ονομάζεται Tait χρωματισμός.

Δεν έχουν όλα τα κανονικά γραφήματα 1-παραγοντοποίηση, για παράδειγμα, το γράφημα του Patersen δεν έχει. Γενικότερα τα γραφήματα του Snark ορίζονται ως τα γραφήματα, όπως το γράφημα του Petersen,τα οποία δεν είναι πλήρη, 3-κανονικά , και δεύτερης τάξης.

Σύμφωνα με το θεώρημα του Kőnig (1916), κάθε διμερές κανονικό γράφημα έχει μία 1-παραγοντοποίηση. Το θεώρημα ορίστηκε νωρίτερα με τον όρο προβολικός σχηματισμός και αποδείχθηκε από τον Ernst Steinitz.

Πολυγραφήματα

'Ενα Shannon πολυγράφημα με 6 ακμές,πολλαπλότητα ακμών ίση με 3 στο οποίο απαιτούνται 9 χρώματα για το χρωματισμό ακμών του.

Στα πολυγραφήματα, στα οποία πολλαπλές παράλληλες ακμές τέμνονται στην ίδια κορυφή, έχουν διαπιστωθεί συμπεράσματα παρόμοια με αυτά του θεωρήματος Vizing, βέβαια με μικρότερη ισχύ, τα οποία συσχετίζουν το χρωματικό αριθμό των ακμών του χ′(G), το μέγιστο δείκτη Δ(G), και την πολλαπλότητα μ(G), η οποία είναι ο μέγιστος αριθμός ακμών σε κάθε δέσμη παράλληλων ακμών. Με ένα απλό παράδειγμα επαληθεύεται ότι το θεώρημα του Vizing δεν ισχύει για τα πολυγραφήματα: θεωρώντας ένα πολυγράφημα Shannon, δηλαδή ένα πολυγράφημα με 3 κορυφές και 3 δέσμες παράλληλων ακμών μ(G) που συνδέουν τα 3 ζεύη κορυφών. Σε αυτό το παράδειγμα ισχύει, Δ(G) = 2μ(G) (κάθε κορυφή προσπίπτει μόνο σε δύο από τις τρεις δέσμες παράλληλων ακμών μ(G) ) αλλά ο χρωματικός αριθμός των ακμών είναι 3μ(G) (υπάρχουν τρεις 3μ(G) ακμές συνολικά, και οι ακμές είναι παρακείμενες ανα δύο άρα πρέπει να ανατεθεί διαφορετικό χρώμα σε κάθε ακμή). Ένα συμπέρασμα του Shannon(1949), το οποίο ενέπνευσε τον Vizing, δείχνει ότι η δυσκολότερη περίπτωση για κάθε πολυγράφημα είναι: χ′(G) ≤ (3/2)Δ(G) . Ακόμη για κάθε πολυγράφημα ισχύει, χ′(G) ≤ Δ(G) + μ(G), κάτι το οποίο περιορίζει το θεώρημα του Vizing στην περίπτωση απλών γραφημάτων (για την οποία μ(G) = 1).

Αλγόριθμοι

Επειδή το πρόβλημα ελέγχου αν ένα γράφημα είναι πρώτης τάξης είναι NP-complete, δεν υπάρχει γνωστός polynomial time algorithm για τον χρωματισμό ακμών γραφήματος με τον βέλτιστο αριθμό χρωμάτων. Παρ'όλα αυτά, έχει αναπτυχθεί ένα πλήθος αλγορίθμων το οποίο επιτρέπει τουλάχιστον ένα από τα ακόλουθα κριτήρια:ισχύουν μόνο για ένα υποσύνολο γραφημάτων, ή δεν χρησιμοποιείται πάντα ο βέλτιστος αριθμός χρωμάτων, ή δεν μπορούν πάντα να επιλυθούν σε πολυωνιμικό χρόνο.

Βέλτιστος χρωματισμός ειδικών γραφημάτων

Στην περίπτωση των διμερών γραφημάτων ή των πολυγραφημάτων μεγίστου βαθμού Δ, το βέλτιστο πλήθος χρωμάτων είναι ακριβώς Δ. Οι Cole, Ost & Schirra (2001) απέδειξαν ότι ο βέλτιστος χρωματισμός ακμών αυτών των γραφημάτων υπολογίζεται από το όριο της σχεδόν γραμμικής σχέσης O(m log Δ), όπουm το πλήθος ακμών του γραφήματος, αλλά, πιο συγκεκριμένα οι αλγόριθμοι περιγράφηκαν από τους Cole & Hopcroft (1982) και Alon (2003). Ο αλγόριθμος του Alon (2003)αρχίζει εισάγοντας το κανονικό γράφημα, χωρίς να υπολογίζει τον βαθμό του ή το μέγεθός του, συγχωνεύει τα ζεύγη των κορυφών που βρίσκονται στην ίδια πλευρά των διμερών γραφημάτων και μετά προσθέτει κάποιες επιπλέον κορυφές και ακμές. έπειτα, αν ο βαθμός είναι περιττός, ο Alon εφηύρε ένα μοναδικό τέλειο ταίριασμα στην σχεδόν γραμμική σχέση , του προσδιόρισε ένα χρώμα, και το απομάκρυνε απ το γράφημα, ώστε ο βαθμός να γίνει άρτιος. Τέλος, ο Alon εφάρμοσε την παρατήρηση Gabow (1976), κατά την οποία συγκεντρώνει εναλλασσόμενα υποσύνολα ακμών σε ένα Euler tour του γραφήματος και τα χωρίζει σε δύο κανονικά υπογραφήματα , για να διασπάσει το πρόβλημα του χρωματισμού ακμών σε δύο μικρότερα υποπροβλήματα, και ο αλγόριθμός του λύνει τα δύο υποπροβλήματα αναδρομικά. Ο συνολικός χρόνος του αλγόριθμου αυτού είναι O(m log m).

Για επίπεδες καμπύλες με μέγιστο βαθμό Δ ≥ 7, ο βέλτιστος αριθμός χρωμάτων είναι και πάλι Δ. Ισχυρότερη είναι η υπόθεση Δ ≥ 9, και είναι δυνατό να βρεθεί ο βέλτιστος χρωματισμός ακμών σε γραμμικό χρόνο (Cole & Kowalik 2008).

Αλγόριθμοι που χρησιμοποιούν μεγαλύτερο αριθμό χρωμάτων από τον βέλτιστο

Οι Misra & Gries (1992) και Gabow και άλλοι (1985) περιγράφουν πολυωνυμικούς αλγόριθμους για το χρωματισμό οποιουδήποτε γραφήματος με Δ + 1 χρώματα, συναντώντας το όριο απ το θεώρημα του Vizing.

Για τα πολυγραφήματα, οι Karloff & Shmoys (1987) παρουσιάζουν τον ακόλουθο αλγόριθμο, τον οποίο απέδωσαν στον Eli Upfal. Κάνει την εισαγωγή ενός πολυγραφήματος G G Eulerian προσθέτοντας μία νέα κορυφή που συνδέεται με μία ακμή σε κάθε περιττού βαθμού κορυφή, βρίσκει ένα Euler tour, και επιλέγει έναν προσανατολισμό για αυτό. Σχηματίζει ένα διμερές γράφημα H στο οποίο υπάρχουν δύο αντίγραφα κάθε κορυφής του G, ένα σε κάθε πλευρά, με τη μία ακμή μίας κορυφής u στην αριστερή πλευρά του γραφήματος και μίας κορυφής v στην δεξιά πλευρά, κάθε φορά που ο προσανατολισμός είναι από το u προς το v στο G. Έτσι εφαρμόζεται ο αλγόριθμος χρωματισμού ακμών για το διμερές γράφημα H. Κάθε χρωματική τάξη του H αντιστοιχεί σε μία συλλογή από ακμές του G που σχηματίζουν ένα υπογράφημα βαθμού το πολύ δύο. Αυτό συμβαίνει επειδή, μία ξένη ένωση μονοπατιών και κύκλων, είναι δυνατόν κάθε κλάση χρωμάτων του H να αντιστοιχεί σε τρεις τάξεις χρωμάτων του G. Τη στιγμή που ο αλγόριθμος οριοθετείται από το χρώμα της ακμής ενός διμερούς γραφήματος O(m log Δ) χρησιμοποιούμε τον αλγόριθμο των Cole, Ost & Schirra (2001). Το πλήθος των χρωμάτων που χρησιμοποιεί αυτός ο αλγόριθμος είναι το πολύ $3\left\lceil {\frac {\Delta }{2}}\right\rceil$, που μοιάζει αλλά δεν είναι ίδιο με το όριο του Shannon $\left\lfloor {\frac {3\Delta }{2}}\right\rfloor$. Μπορεί, επίσης, να μετατραπεί σε έναν παράλληλο αλγόριθμο με άμεσο τρόπο. Οι Karloff και Shmoys παρουσιάζουν ένα γραμμικό αλγόριθμο για τον χρωματισμό πολυγραφημάτων μεγίστου βαθμού τρία με τέσσερα χρώματα (συνδυασμός ορίων από τα θεωρήματα Shannon και Vizing) ο οποίος λειτουργεί με παρόμοιο τρόπο. Ο αλγόριθμός τους προσθέτει μία νέα κορυφή για να γίνει το γράφημα σαν του Euler, βρίσκει ένα Euler tour, και επιλέγει εναλλασσόμενα σύνολα από ακμές για να χωρίσει το γράφημα σε δύο υπογραφήματα μεγίστου βαθμού δύο. Τα μονοπάτια ακόμα και οι κύκλοι κάθε υπογραφήματος μπορούν να χρωματιστούν με δύο χρώματα ανά υπογράφημα. Μετά από αυτό, κάθε υπολοιπόμενος κύκλος περιέχει τουλάχιστον μία ακμή η οποία μπορεί να χρωματιστεί με ένα από τα δύο χρώματα του απέναντι υπογραφήματος. Μετακινώντας την ακμή από τον κύκλο αφήνει ένα μονοπάτι, το οποίο μπορεί να χρωματιστεί χρησιμοποιώντας τα δύο χρώματα του αντίστοιχου υπογραφήμτος.

Ένας αλγόριθμος με πλεονεκτικό χρωματισμό , εξετάζει τις ακμές ενός γραφήματος ή πολυγραφήματος μία προς μία, εκχωρεί σε κάθε ακμή το πρώτο διαθέσιμο χρώμα και ίσως το πλήθος των χρωμάτων είναι 2Δ − 1, δηλαδή σχεδόν το διπλάσιο του απαραίτητου. Ωστόσο, έχει το πλεονέκτημα ότι μπορεί να χρησιμοποιηθεί στους online αλγόριθμους, ελέγχοντας την είσοδο γραφημάτων που δεν είναι γνωστά εκ των προτέρων. Με αυτόν τον έλεγχο, ο ανταγωνιστικός δείκτης του είναι δύο και αυτός είναι ο βέλτιστος γιατί κανένας άλλος online αλγόριθμος δεν έχει καλύτερα αποτελέσματα. Παρ' όλα αυτά, αν οι ακμές επιλέγονται με τυχαία σειρά, και ο βαθμός του γραφήματος εισόδου είναι τουλάχιστον λογαριθμικός, τότε μπορούν να επιτευχθούν μικρότεροι ανταγωνιστικοί δείκτες.

Κάποιοι συγγραφείς έχουν φτιάξει εικασίες που συνεπάγονται πως ο κλασματικός χρωματικός δείκτης κάθε πολυγραφήματος (υπολογίζεται από πολυώνυμα χρησιμοποιώντας γραμμικό προγραμματισμό) έχει μία χρωματική ένδειξη. Αν αυτές οι εικασίες αληθεύου, είναι δυνατό να υπολογίσουμε ένα νούμερο που ποτέ δεν ξεπερνά αυτή τη χρωματική ένδειξη στην περίπτωση των πολυγραφημάτων, συνδυάζοντας ό,τι είναι γνωστό που το θεώρημα του Vizing για απλά γραφήματα. Αν αποδειχθεί αυτό σε γενικές γραμμές, αυτές οι εικασίες μπορούν να ισχύουν όταν οι χρωματικές ενδείξεις είναι τουλάχιστον $\Delta +{\sqrt {\Delta /2}}$, όπως συμβαίνει σε πολυγραφήματα με μεγάλη πολυπλοκότητα .

Ακριβείς αλγόριθμοι

Είναι απλό να εξετάσουμε πότε οι ακμές ενός γραφήματος μπορούν να χρωματιστούν με ένα ή δύο χρώματα, ούτως ώστε στην πρώτη μη τετριμμένη περίπτωση χρωματισμού ακμών να ελέγχεται πότε ένα γράφημα έχει 3 χρώματα για τις ακμές. Όπως έδειξε ο Kowalik (2009), γίνεται να ελέγξουμε πότε ένα γράφημα έχει 3 χρώματα για τις ακμές του σε χρόνο O(1.344ⁿ), χρησιμοποιώντας μόνο τον πολυωνυμικό χώρο. Παρόλο που το όριο αυτού του χρόνου είναι εκθετικό, είναι αισθητά πιο γρήγορο από την απλή αναζήτηση πάνω σε όλες τις πιθανες αναζητήσεις χρωμάτων για ακμές. Κάθε συνδεδεμένο 3-κανονικό γράφημα με n κορυφές έχει O(2^n/2) 3-χρωματισμούς ακμών, οι οποίοι μπορούν να αναφερθούν σε χρόνο O(2^n/2) (πιο αργό από την εύρεση μοναδικού χρώματος). Όπως παρατήρησε ο Greg Kuperberg, το γράφημα ενός πρίσματος με n/2-πλευρές έχει πολλά χρώματα, δείχνοντας ότι το όριο αυτό είναι αυστηρό.

Με τη εφαρμογή ακριβών αλγορίθμων για χρωματισμό κορυφών στο γράφημα γραμμής του γραφήματος εισαγωγής, είναι δυνατό να βελτιστοποιήσουμε τον χρωματισμό ακμών κάθε γραφήματος με m ακμές, ανεξάρτητα από τον αριθμό των χρωμάτων που απαιτούνται, σε χρόνο 2^mm^O(1) και εκθετικό διάστημα, ή O(2.2461^m) και μόνο πολυωνυμικό διάστημα (Björklund, Husfeldt & Koivisto 2009).

Επειδή ο χρωματισμός ακμών είναι NP-complete ακόμα και για τρία χρώματα, είναι απίθανο να έχουμε σταθερή παράμετρο όταν παραμετρικοποιούμε με βάση το πλήθος των χρωμάτων. Ωστόσο, είναι λογικό να συμβαίνει για άλλες παραμέτρους. Ειδικότερα, οι Zhou, Nakano & Nishizeki (1996) απέδειξαν πως για γραφήματα πλάτους w, ο βέλτιστος χρωματισμός ακμών υπολογίζεται ε χρόνο O(nw(6w)^{w(w + 1)/2}), ένα όριο με εκθετική εξάρτηση από το w, αλλά γραμμική από το πλήθος n των κορυφών του γραφήματος.

Οι Nemhauser & Park (1991) διατυπώνουν το πρόβλημα του χρωματισμού ακμών ως ένα ακέραιο πρόγραμμα και περιγράφουν την πρακτική τους χρησιμοποιώντας την λύση ενός ακέραιου προγραμματισμού στο χρώμα των ακμών αυτών. Ωστόσο, δεν παρουσιάζουν καμία ανάλυση πολυπλοκότητας του αλγορίθμου τους.

Πρόσθετες Ιδιότητες

Το uniquely 3-colorable γενικευμένο γράφημα Πέτερσεν G(9,2). Μία από τις τρεις κατηγορίες χρωμάτων της φαίνεται από τις φωτεινές ακμές και οι άλλες δύο μπορεί να βρεθούν είτε με την περιστροφή των άκρων φωτός κατά 40° προς κάθε κατεύθυνση ή διαχωρίζοντας τον σκοτεινό Hamiltonian κύκλο σε εναλλασσόμενα άκρα.

Ένα γράφημα είναι uniquely k-edge-colorable αν υπάρχει μόνο ένας τρόπος για να διαχωρίσει τις άκρες σε k τάξεις χρώματος, αγνοώντας τους k! πιθανούς συνδυαμούς χρωμάτων. Για k ≠ 3, τα μόνα uniquely k-edge-colorable γραφήματα είναι γραμμές, κύκλοι και άστρα, αλλά για k = 3 ενδέχεται να είναι uniquely k-edge-colorable και άλλα γραφήματα. Κάθε uniquely 3-edge-colorable γράφημα διαθέτει ακριβώς τρεις Χαμιλτονιανούς κύκλους, που σχηματίζεται διαγράφοντας μία από τις τρεις κλάσεις χρώματος, αλλά υπάρχουν 3-κανονικά γραφήματα πυ διαθέτουν τρεις Χαμιλτονιανούς κύκλους και δεν είναι uniquely 3-colorable, όπως το γενικευμένο γράφημα Πέτερσεν G(6n + 3, 2) για n ≥ 2. Το μόνο γνωστό μη επίπεδο uniquely 3-colorable γράφημα είναι το γενικευμένο γράφημα Πέτερσεν G(9,2) και έχει αποδειχθεί ότι δεν υπάρχουν άλλα.

Οι Folkman & Fulkerson (1969) ερεύνησαν τις μη αύξουσες ακολουθίες αριθμών m₁, m₂, m₃, ... με την ιδιότητα ότι υπάρχει ένας σωστός χρωματισμός ακμών ενός δεδομένου γραφήματος G με m₁ ακμές για το πρώτο χρώμα, m₂ ακμές για το δεύτερο χρώμα, κλπ. Παρατήρησαν ότι, αν μία ακολουθία P είναι δυνατόν να δημιουργηθεί έτσι, και είναι μεγαλύτερη σε λεξικογραφική σειρά από μια ακολουθία Q με τις ίδιες ιδιότητες, τότε και η Q στηρίζεται στον ίδιο τρόπο δημιουργίας. Γιατί, αν P > Q σε λεξικογραφική σειρά, τότε η P μπορεί να μετατραπεί σε Q με μια σειρά βημάτων, κάθε ένα από τα οποία μειώνει έναν από τους αριθμούς m_i κατά μία μονάδα και αυξάνει έναν επόμενο αριθμό m_j με i < j κατά μία μονάδα. Από την άποψη χρωματισμού ακμών, ξεκινώντας από ένα χρώμα που ενεργοποιεί την P, καθένα από τα ίδια βήματα μπορούν να γίνουν με την εναλλαγή χρωμάτων i και j σε μια Kempe αλυσίδα, την μέγιστη διαδρομή των άκρων που εναλλάσσονται μεταξύ των δύο χρωμάτων. Ειδικότερα, κάθε γράφημα έχει έναν ισότιμο χρωματισμό ακμών, έναν χρωματισμό με το βέλτιστο αριθμό χρωμάτων στα οποίο κάθε δύο κλάσσεις διαφέρουν ως προς το μέγεθος το πολύ μία μονάδα.

Άλλοι τύποι για τον χρωματισμό ακμών

Ένας διαχωριμός του πλήρους διμερούς γραφήματος Κ_4,4 into three forests, showing that it has arboricity three.

Ο Thue number ενός γραφήματος είναι ο αριθμός των χρωμάτων που απαιτούνται σε έναν χρωματισμό ακμών, σε συνδυασμό με την ισχυρότερη απαίτηση ότι σε κάθε διαδρομή, ακόμη και μήκους, τα πρώτο και δεύτερο μισό της διαδρομής σχηματίζουν διαφορετικές αλληλουχίες των χρωμάτων. The arboricity ενός γραφήματος είναι ο ελάχιστος αριθμός των χρωμάτων που απαιτούνται έτσι ώστε τα άκρα του κάθε χρώματος να μην έχουν κύκλους (αντί για το προτότυπο πρόβλημα ακμής χρωματισμού, που δεν έχουμε παρακείμενα ζεύγη ακμών). Δηλαδή είναι ο ελάχιστος αριθμός Unlike the chromatic index, the arboricity of a graph may be computed in polynomial time.

Η Λίστα Χρωματικών Ακμών είναι ένα πρόβλημα στο οποίο δίνεται ένα γράφημα που η κάθε πλευρά του συνδέεται με μια λίστα χρωμάτων, και πρέπει να βρούμε έναν ορθό χρωματισμό κατά τον οποίο το χρώμα κάθε ακμής επιλέγεται από την λίστα χρωμάτων. Ο χρωματικός δείκτης λιστας, ενός γραφήματος G είναι ο μικρότερος αριθμός k με την ιδιότητα ότι, ανεξάρτητα από το πώς επιλέγει κάποιος την λίστα χρωμάτων για τις ακμές, εφ 'όσον κάθε ακμή έχει τουλάχιστον k χρώματα στη λίστα της, ένας χρωματισμός είναι σίγουρο ότι θα πραγματοποιηθεί. Έτσι, ο χρωματικός δείκτης λίστας είναι πάντα τουλάχιστον τόσο μεγάλος όσο ο χρωματικός δείκτης. Η Dinitz εικασία για την ολοκλήρωση της μερικής Λατινικής πλατείας s μπορεί να αναδιατυπωθεί ως την δήλωση ότι λίστα χρωματικού αριθμού ακμών του πλήρες διμερές γράφημα K _{n, n} ισούται άκρη χρωματικό αριθμό του, n. Galvin (1995) επιλυθεί η εικασία αποδεικνύοντας, γενικότερα, ότι σε κάθε διμερές γράφημα το χρωματικό δείκτη και λίστα χρωματική δείκτη είναι ίσες. Η ισότητα μεταξύ του χρωματικού δείκτη και του χρωματικού δείκτη λίστας εικάζεται ότι ισχύει, και ακόμη πιο γενικά, για αυθαίρετα πολυγραφήματα χωρίς αυτοβρόχους.αυτή η υπόθεση παραμένει ανοιχτή.

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

Αν ένα 3-κανονικό γράφημα σε μια επιφάνεια είναι 3-πλευρα χρωματισμένο,το διπλό γράφημα του σχηματίζει έναν τριγωνισμός της επιφάνεια η οποία είναι επίσης χρωματισμένο άκρο (παρ' όλου που γενικά δεν) κατά τέτοιον τρόπο ώστε κάθε τρίγωνο να έχει ένα άκρο για κάθε χρώμα. Άλλοι χρωματισμοί και προσανατολισμοί για τους τριγωνισμούς, με άλλους τοπικούς περιορισμούς σχετικά με το πώς τα χρώματα είναι διατεταγμένα στις κορυφές ή επιφάνειες του τριγωνισμού, μπορεί να χρησιμοποιηθούν για να κωδικοποιήσουν διάφορους τύπους γεωμετρικού αντικειμένου. Για παράδειγμα, ορθογώνιες υποδιαιρέσεις (τμήματα μιας υποδιαίρεσης ενός ορθογώνιου σε μικρότερα ορθογώνια, με τρία ορθογώνια να συναντιούνται σε κάθε κορυφή) μπορεί να περιγραφεί συνδυαστικά με μια "κανονική σήμανση», ενός δύο-χρωματισμού των ακμών ενός τριγωνισμού διπλής υποδιαίρεσης, με τον περιορισμό ότι οι άκρες που ενώνονται σε μια κορυφή σχηματίζουν τέσσερις συνεχόμενες υπακολουθίες, μέσα στην κάθε μια τα χρώματα είναι τα ίδια. Αυτή η σήμανση είναι διπλή σε χρωματισμό της ίδιας της ορθογώνιας υποδιαίρεση στην οποία οι κάθετες ακμές έχουν ένα χρώμα και οι οριζόντιες ακμές έχουν το άλλο χρώμα. Παρόμοιοι περιορισμοί για την σειρά με την οποία μπορεί να εμφανιστούν οι χρωματιστές άκρες γύρω από μια κορυφή μπορεί επίσης να χρησιμοποιηθεί για να κωδικοποιήσει την ευθεία γραμμή embeddings του πλέγματος των επίπεδων γραφημάτων και τα τρισδιάστατα πολύεδρα με άξονες παράλληλες πλευρές. Για καθένα από αυτά τα τρία είδη των κανονικών σημάνσεων, το σύνολο των κανινικών σημάνσεων μιας σταθερής μορφής γραφήματος διανεμητικό lattice, στο οποίο μπορεί να χρησιμοποιηθεί για να κατηγοριοποιήσει γρήγορα όλες τις γεωμετρικές δομές που βασίζονται στην ίδια γραφική παράσταση (όπως όλοι οι άξονες παράλληλων πολύεδρων έχουν τον ίδιο σκελετό) ή να βρει δομές που ικανοποιούν επιπλέον περιορισμούς.

Ένα ντετερμινιστικό πεπερασμένο αυτόματο μπορεί να ερμηνευθεί ως ένα κατευθυνόμενο γράφημα στο οποίο κάθε κορυφή έχει τον ίδιο εξωτερικό βαθμό d, και οι ακμές είναι d -χρωματισμένες με τέτοιο τρόπο ώστε κάθε δύο άκρα με την ίδια κορυφή έχουν διακριτά χρώματα. Το πρόβλημα χρωματισμού δρόμου είναι το πρόβλημα χρωματισμού ακμών ενός κατευθυνόμενου γραφήματος με ομοιόμορφους εξωτερικούς βαθμούς, κατά τέτοιο τρόπο ώστε το αυτόματο που προκύπτει να έχει μία λέξη συγχρονισμού. Trahtman (2009) έλυσε το πρόβλημα χρωματισμού δρόμου, αποδεικνύοντας ότι ένας τέτοιος χρωματισμός μπορεί να βρεθεί κάθε φορά που η συγκεκριμένη γραφική παράσταση είναι άρρηκτα συνδεδεμένη και το απεριοδικό.

Το θεώρημα του Ραμσή αφορά το πρόβλημα k-χρωματισμένων ακμών ενός μεγάλου πλήρους γραφήματος K_n έτσι ώστε να αποφευχθεί η δημιουργία μονοχρωματικών πλήρων υποδιαιρέσεων K_s κάποιου συγκεκριμένου μεγέθους s. Σύμφωνα με αυτό το θεώρημα, υπάρχει ένας αριθμός R_k(s) τέτοιος ώστε, όταν n ≥ R(s), ένας τέτοιος χρωματισμός να μην είναι δυνατός. Για παράδειγμα, R₂(3) = 6, δηλαδή όταν οι ακμές του γραφήματος K₆ είναι 2-χρωμες, πάντα θα υπάρχει ένα μονοχρωματικό τρίγωνο.

Εφαρμογές

Ο χρωματισμός ακμών ενός πλήρους γραφήματος μπορεί να χρησιμοποιηθεί για να προγραμματιστεί ένας κυκλικός-robin γύρος σε όσους το δυνατόν λιγότερο γύρους έτσι ώστε κάθε ένας από ένα ζευγάρι αντιπάλων να παίζει σε κάθε γύρο. Σε αυτήν την εφαρμογή οι κορυφές του γραφήματος αντιστοιχούν στους αντιπάλους του τουρνουά,οι ακμές αντιστοιχούν στα παιχνίδια και οι χρωματισμένες ακμές στους γύρους στους οποίους παίζονται τα παιχνίδια.Παρόμοιες τεχνικές χρωματισμού μπορούν επίσης να χρησιμοποιηθούν για να προγραμματίσουν άλλα ομαδικά αθλήματα που δεν είναι μεταξύ δύο παικτών. Για παράδειγμα, στην Εθνική Ομάδα Ποδοσφαίρου,τα ζευγάρια των ομάδων που θα παίξουν μεταξύ τους σε ένα δεδομένο έτος καθορίζονται με βάση τις εγγραφές των ομάδων από το προηγούμενο έτος, και στη συνέχεια ένας αλγόριθμος χρωματισμού ακμών εφαρμόζεται στην γραφική παράσταση που διαμορφώνεται από το σύνολο των ζευγαριών, προκειμένου να αναθέσει παιχνίδια για τα Σαββατοκύριακα.. Για την εφαρμογή αυτή, από το θεώρημα Vizing συνεπάγεται ότι ανεξάρτητα από την ομάδα ζευγαριών που θα επιλεγεί (εφ' όσον δεν υπάρχουν ομάδες που παίζουν μεταξύ τους δύο φορές την ίδια σεζόν), είναι πάντα δυνατό να βρεθεί ένα πρόγραμμα που χρησιμοποιεί το πολύ ένα ακόμη Σαββατοκύριακο από ό,τι τα παιχνίδια ανά ομάδα.

Ο Ανοικτός προγραμματισμός είναι ένα πρόβλημα προγραμματισμού παραγωγικών διαδικασιών, στο οποίο υπάρχει μια σειρά από αντικείμενα που πρόκειται να κατασκευαστούν, κάθε αντικείμενο έχει μια σειρά από εργασίες που πρέπει να εκτελεστούν σε αυτό ( σε οποιαδήποτε σειρά), και κάθε εργασία πρέπει να πραγματοποιείται σε ένα συγκεκριμένο μηχάνημα, αποτρέποντας οποιαδήποτε άλλη εργασία που χρησιμοποιεί το ίδιο μηχάνημα να εκτελείται ταυτόχρονα. Εάν όλες οι εργασίες έχουν το ίδιο μήκος, τότε το πρόβλημα αυτό μπορεί να τυποποιηθεί ως ένα πρόβλημα χρωματισμού ακμών ενός διμερούς πολυγράφου, κατά το οποίο οι κορυφές στην διμερή πλευρά αντιπροσωπεύουν τα αντικείμενα που πρόκειται να κατασκευαστούν, οι κορυφές στην απέναντι από την διμερή πλευρά αντιπροσωπεύουν τα μηχανήματα κατασκευής, οι ακμές αντιπροσωπεύουν τις εργασίες που πρέπει να εκτελεστούν, και τα χρώματα αντιπροσωπεύουν τα χρονικά διάστημα στα οποία μπορεί να πραγματοποιηθεί κάθε εργασία. Από την στιγμή που ο διμερές χρωματισμός ακμών μπορεί να γίνει σε πολυωνυμικό χρόνο, το ίδιο ισχύει και για την παρούσα κλειστή περίπτωση του ανοικτόυ προγραμματισμού.

Οι Gandham, Dawande & Prakash (2005) μελέτησαν το πρόβλημα της σύνδεσης του προγραμματισμού με τον χρόνο διαίρεσης πολλαπλής πρόσβασηςτων πρωτόκολλων επικοινωνιών δικτύου στους αισθητήρες δικτύου ως μια παραλλαγή του χρωματισμού ακμών. Σε αυτό το πρόβλημα, κάποιος πρέπει να επιλέξει τα χρονικά διαστήματα για τις άκρες ενός ασύρματου δικτύου επικοινωνιών, έτσι ώστε κάθε κόμβος του δικτύου να μπορεί να επικοινωνήσει με κάθε γειτονικό κόμβο χωρίς παρεμβολές. Χρησιμοποιώντας κάποιος τον ισχυρό χρωματισμό ακμών (και χρησιμοποιώντας δύο χρονικά διαστήματα για κάθε χρωματιστή ακμή, ένα για κάθε κατεύθυνση) θα έλυνε το πρόβλημα, αλλά θα χρησιμοποιούσε περισσότερα χρονικά διαστήματα απ' όσα χρειάζονται. Αντ 'αυτού, ζητούν ένα χρωματισμόν του κατευθυνόμενου γραφήματος που σχηματίζεται με διπλασιάζοντας κάθε μη-κατευθυνόμενο άκρο του δικτύου, με την ιδιότητα ότι κάθε κατευθυνόμενη ακμή uv έχει διαφορετικό χρώμα από τις άκρες που βγαίνουν από v και από τους γείτονες της v. Προτείνουν μια πειραματική λύση για το πρόβλημα αυτό που βασίζεται σε έναν κατανεμημένο αλγόριθμο για (Δ + 1)-άκρες χρωματισμένες, μαζί με μια φάση τελικής επεξεργασίας που αναδιοργανώνει τις ακμές που θα μπορούσαν να αλληλεπιδρούν μεταξύ τους.

Στην επικοινωνία οπτικών ινών, το πρόβλημα διαδρομής χρωματισμού είναι το πρόβλημα της ανάθεσης χρωμάτων (συχνότητες του φωτός) σε ζεύγη κόμβων που θέλουν να επικοινωνούν μεταξύ τους, με τον περιορισμό για τις διαδρομές μέσα από ένα δίκτυο επικοινωνιών οπτικών ινών για κάθε ζεύγος, ότι δεν υπάρχουν δύο διαδρομές που μοιράζονται ένα τμήμα των ινών που χρησιμοποιεί την ίδια συχνότητα, το ένα με τ' άλλο. Διαδρομές που περνούν μέσα από το ίδιο κύκλωμα επικοινωνίας, αλλά όχι μέσα από οποιοδήποτε τμήμα των ινών, επιτρέπεται να χρησιμοποιούν την ίδια συχνότητα. Όταν το δίκτυο επικοινωνιών διατάσσεται ως δίκτυο αστέρι, με ένα μόνο κεντρικό διακόπτη που είναι συνδεδεμένος με χωριστές ίνες σε κάθε ένα από τους κόμβους, τότε το πρόβλημα διαδρομής χρωματισμού μπορεί να μοντελοποιηθεί ακριβώς όπως ένα πρόβλημα χρωματισμού ακμών ενός γραφήματος ή ενός πολυγράφου, στα οποία οι κόμβοι που επικοινωνούν σχηματίζουν τις κορυφές του γραφήματος, τα ζεύγη των κόμβων που επικοινωνούν σχηματίζουν τις ακμές του γραφήματος, και οι συχνότητες που μπορεί να χρησιμοποιηθούν για κάθε ζεύγος σχηματίζουν τα χρώματα του προβλήματος χρωματισμού ακμών. Για τα δίκτυα επικοινωνιών, με μια πιο γενική τοπολογία, οι λύσεις των διαδρομών για τον χρωματισμό των δικτύων αστέρι που ορίζεται από κάθε διακόπτη στο δίκτυο, μπορεί να καταναμηθούν μαζί για να σχηματίσουν μια ενιαία συνολική λύση.

Ανοικτά Προβλήματα

Οι Jensen & Toft (1995) δημιούργησαν μια λίστα από 23 ανοικτά προβλήματα που αφορούν τον χρωματισμό ακμών. Αυτά είναι:

• Η εικασία του Goldberg (1973) ότι ο χρωματικός δείκτης και ο κλασματικός δείκτης περιλαμβάνονται το ένα μέσα στο άλλο, πράγμα το οποίο επιτρέπει στον χρωματικό δείκτη να προσεγγιστεί με ένα χρώμα σε πολυωνυμικό χρόνο.
• Πολλές υποθέσεις του Jakobsen και άλλων σχετικά με τη δομή του κύριου γραφήματος για τον χρωματισμό ακμών, γραφήματα κλάσης 2, έτσι ώστε κάθε υπόγραφος να έχει είτε τον μικρότερο μέγιστο βαθμό ή να είναι κλάσης 1. Ο Jakobsen αρχικά θεωρεί ότι όλα τα κύρια γραφήματα έχουν έναν μοναδικό αριθμό κορυφών, αλλά αυτό τελικά διαψεύστηκε. Αρκετές άλλες εικασίες που πλησιάζουν αυτή, ή που οριοθετούν τους αριθμούς των κορυφών των κύριων γραφημάτων και κύριων πολύγραφων, παραμένουν ανοικτές.
• Το πρόβλημα του Vizing της ταξινόμησης των ανώτατων βαθμών που είναι πιθανοί για την κλάση 2 των επίπεδων γραφημάτων.
• Οι εικασίες για το πλήρες υπόγραφο του AJW Hilton, δηλώνοντας ότι γραφήματα με βαθμό τουλάχιστον n/3 είναι είτε κλάσης 1 ή περιέχουν έναν υπόγραφο με τον ίδιο βαθμό Δ με το αρχικό γράφημα, και με μοναδικό αριθμό kτων κορυφών, έτσι ώστε ο αριθμός των ακμών στον υπόγραφο να είναι μεγαλύτερος από Δ(k − 1)/2, και μια παρόμοια θεωρία των Herbert Grötzsch και Paul Seymour σχετικά με τα επίπεδα γραφήματα στη θέση των γραφημάτων υψηλού βαθμού.
• Μια θεωρία των Chetwynd και Hilton (ενδεχομένως να σχετίζεται με αυτήν του Gabriel Andrew Dirac) ότι τα τυπικά γραφήματα με ζυγό αριθμό n των κορυφών και με βαθμό τουλάχιστον n/2 είναι κλάσης 1.
• Μια υπόθεση των Claude Berge και D. R. Fulkerson ότι ο 6-τυπικός πολύγραφος σχηματίζεται διπλασιάζοντας κάθε άκρη ενός bridgeless 3-τυπικού γραφήματος απλού μπορεί να έχει χρωματισμένες άκρες με έξι χρώματα.
• Μια εικασία των Fiorini και Wilson ότι κάθε τρίγωνο χωρίς επίπεδη γραφική παράσταση, εκτός από το νύχι Κ _1,3 , δεν είναι μοναδικά 3-edge-απατηλός.
• Μια τρέχουσα υπόθεση είναι ότι αν G είναι ένας d-τυπικός πολυγράφος επίπεδος, τότε το G είναι -edge-απατηλός αν και μόνο αν G είναι περίεργο d άκρη συνδεδεμένη. Αυτή η εικασία μπορεί να θεωρηθεί ως μια γενίκευση της Τέσσερις χρώμα θεώρημα όταν d = 3. Μαρία Τσουντνόφσκι, Katherine Edwards, και Paul Seymour απέδειξαν ότι ένα 8-τυπικό πολυγράφημα επίπεδο έχει 8 χρωματικές ακμές.

Πηγές

• Akiyama, Jin; Exoo, Geoffrey; Harary, Frank (1980), «Covering and packing in graphs. III. Cyclic and acyclic invariants», Mathematica Slovaca 30 (4): 405–417 .
• Alon, Noga (2003), «A simple algorithm for edge-coloring bipartite multigraphs», Information Processing Letters 85 (6): 301–302, doi:10.1016/S0020-0190(02)00446-5 .
• Alon, Noga; Sudakov, Benny; Zaks, Ayal (2001), «Acyclic edge colorings of graphs», Journal of Graph Theory 37 (3): 157–167, doi:10.1002/jgt.1010 .
• Andersen, Lars Døvling (1977), «On edge-colourings of graphs», Mathematica Scandinavica 40 (2): 161–175 . As cited by Chen, Yu & Zang (2011).
• Appel, K.; Haken, W. (1976), «Every planar map is four colorable», Bulletin of the American Mathematical Society 82 (5): 711–712, doi:10.1090/S0002-9904-1976-14122-5 .
• Bahmani, Bahman; Mehta, Aranyak; Motwani, Rajeev (2010), «A 1.43-competitive online graph edge coloring algorithm in the random order arrival model», Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '10), σελ. 31–39, http://portal.acm.org/citation.cfm?id=1873601.1873605 .
• Bar-Noy, Amotz; Motwani, Rajeev; Naor, Joseph (1992), «The greedy algorithm is optimal for on-line edge coloring», Information Processing Letters 44 (5): 251–253, doi:10.1016/0020-0190(92)90209-E .
• Barrett, C.L.; Istrate, G.; Kumar, V.S.A.; Marathe, M.V.; Thite, S.; Thulasidasan, S. (2006), «Strong edge coloring for channel assignment in wireless radio networks», Proc. Fourth Annual IEEE International Conference on Pervasive Computing and Communications Workshops (PerCom Workshops 2006), σελ. 106, doi:10.1109/PERCOMW.2006.129, ISBN 0-7695-2520-2 .
• Biggs, Norman (1972), An edge-colouring problem, στο: Guy, Richard K., επιμ., «Research Problems», American Mathematical Monthly 79 (9): 1018–1020 .
• Biggs, Norman (1979), Some odd graph theory, «Second International Conference on Combinatorial Mathematics», Annals of the New York Academy of Sciences, Annals of the New York Academy of Sciences 319: 71–81, doi:10.1111/j.1749-6632.1979.tb32775.x .
• Björklund, Andreas; Husfeldt, Thore; Koivisto, Mikko (2009), «Set partitioning via inclusion-exclusion», SIAM Journal on Computing 39 (2): 546–563, doi:10.1137/070683933 .
• Bosák, Juraj (1972), «Chromatic index of finite and infinite graphs», Czechoslovak Mathematical Journal 22(97): 272–290 .
• Bosák, Juraj; Nešetřil, Jaroslav (1976), «Complete and pseudocomplete colourings of a graph», Matematicky Časopis Slovenskej Akadémie Vied 26 (3): 171–184 .
• Burke, E.; De Werra, D.; Kingston, J. (2004), «5.6.5 Sports Timetabling», στο: J. L., Gross; J., Yellen, επιμ., Handbook of Graph Theory, CRC Press, σελ. 462, ISBN 978-1-58488-090-5, http://books.google.com/books?id=mKkIGIea_BkC&pg=PA462 .
• Chen, Guantao; Yu, Xingxing; Zang, Wenan (2011), «Approximating the chromatic index of multigraphs», Journal of Combinatorial Optimization 21 (2): 219–246, doi:10.1007/s10878-009-9232-y .
• Cole, Richard; Hopcroft, John (1982), «On edge coloring bipartite graphs», SIAM Journal on Computing 11 (3): 540–546, doi:10.1137/0211043 .
• Cole, Richard; Kowalik, Łukasz (2008), «New linear-time algorithms for edge-coloring planar graphs», Algorithmica 50 (3): 351–368, doi:10.1007/s00453-007-9044-3 .
• Cole, Richard; Ost, Kirstin; Schirra, Stefan (2001), «Edge-coloring bipartite multigraphs in O(E log D) time», Combinatorica 21 (1): 5–12, doi:10.1007/s004930170002 .
• Cranston, Daniel W. (2006), «Strong edge-coloring of graphs with maximum degree 4 using 22 colors», Discrete Mathematics 306 (21): 2772–2778, doi:10.1016/j.disc.2006.03.053 .
• Eppstein, David (2008), «The topology of bendless three-dimensional orthogonal graph drawing», στο: Tollis, Ioannis G.; Patrignani, Marizio, επιμ., Proc. 16th Int. Symp. Graph Drawing, Lecture Notes in Computer Science, 5417, Heraklion, Crete: Springer-Verlag, σελ. 78–89 .
• Eppstein, David (2010), «Regular labelings and geometric structures», Proc. 22nd Canadian Conference on Computational Geometry (CCCG 2010), University of Manitoba, http://www.cs.umanitoba.ca/~cccg2010/electronicProceedings/invitedpaper2.pdf, ανακτήθηκε στις 2014-06-12 .
• Erdős, Paul; Wilson, Robin J. (1977), «Note on the chromatic index of almost all graphs», Journal of Combinatorial Theory, Series B 23 (2–3): 255–257, doi:10.1016/0095-8956(77)90039-9, http://www.renyi.hu/~p_erdos/1977-20.pdf .
• Erlebach, Thomas; Jansen, Klaus (2001), «The complexity of path coloring and call scheduling», Theoretical Computer Science 255 (1–2): 33–50, doi:10.1016/S0304-3975(99)00152-8 .
• Fiorini, S.; Wilson, Robin James (1977), Edge-colourings of graphs, Research Notes in Mathematics, 16, London: Pitman, ISBN 0-273-01129-4 .
• Folkman, Jon; Fulkerson, D. R. (1969), «Edge colorings in bipartite graphs», Combinatorial Mathematics and its Applications (Proc. Conf., Univ. North Carolina, Chapel Hill, N.C., 1967), Chapel Hill, N.C.: Univ. North Carolina Press, σελ. 561–577 .
• Fouquet, J.-L.; Jolivet, J.-L. (1983), «Strong edge-colorings of graphs and applications to multi-k-gons», Ars Combinatoria 16 (A): 141–150 .
• Frieze, Alan M.; Krivelevich, Michael; Sudakov, Benny (2005), «The strong chromatic index of random graphs», SIAM Journal on Discrete Mathematics 19 (3): 719–727 (electronic), doi:10.1137/S0895480104445757 .
• Gabow, Harold N. (1976), «Using Euler partitions to edge color bipartite multigraphs», International Journal of Computer and Information Sciences 5 (4): 345–355, doi:10.1007/BF00998632 .
• Gabow, Harold N.; Nishizeki, Takao; Kariv, Oded; Leven, Daniel; Terada, Osamu (1985), Algorithms for edge-coloring graphs, Tech. Report TRECIS-8501, Tohoku University .
• Gabow, Harold N.; Westermann, Herbert H. (1992), «Forests, frames, and games: algorithms for matroid sums and applications», Algorithmica 7 (5–6): 465–497, doi:10.1007/BF01758774 .
• F. Galvin (1995), «The list chromatic index of a bipartite multigraph», Journal of Combinatorial Theory, Series B 63 (1): 153–158, doi:10.1006/jctb.1995.1011 .
• Gandham, S.; Dawande, M.; Prakash, R. (2005), «Link scheduling in sensor networks: distributed edge coloring revisited», Proc. 24th INFOCOM, 4, σελ. 2492–2501, doi:10.1109/INFCOM.2005.1498534, ISBN 0-7803-8968-9 .
• Gol'dberg, M. K. (1973), «Multigraphs with a chromatic index that is nearly maximal», Diskret. Analiz. (23): 3–7, 72 . As cited by Chen, Yu & Zang (2011).
• Habib, M.; Péroche, B. (1982), «Some problems about linear arboricity», Discrete Mathematics 41 (2): 219–220, doi:10.1016/0012-365X(82)90209-6 .
• Holyer, Ian (1981), «The NP-completeness of edge-coloring», SIAM Journal on Computing 10 (4): 718–720, doi:10.1137/0210055 .
• Horák, Peter; Niepel, Ľudovít (1982), «A short proof of a linear arboricity theorem for cubic graphs», Acta Mathematica Universitatis Comenianae 40/41: 275–277 .
• Jensen, Tommy R.; Toft, Bjarne (1995), Graph Coloring Problems, New York: Wiley-Interscience, ISBN 0-471-02865-7 .
• Karloff, Howard J.; Shmoys, David B. (1987), «Efficient parallel algorithms for edge coloring problems», Journal of Algorithms 8 (1): 39–52, doi:10.1016/0196-6774(87)90026-5 .
• Kőnig, D. (1916), «Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre», Mathematische Annalen 77 (4): 453–465, doi:10.1007/BF01456961, http://gdz.sub.uni-goettingen.de/index.php?id=11&PPN=PPN235181684_0077&DMDID=DMDLOG_0051&L=1, ανακτήθηκε στις 2014-06-12 .
• Kowalik, Łukasz (2009), «Improved edge-coloring with three colors», Theoretical Computer Science 410 (38–40): 3733–3742, doi:10.1016/j.tcs.2009.05.005 .
• Mahdian, Mohammad (2002), «On the computational complexity of strong edge coloring», Discrete Applied Mathematics 118 (3): 239–248, doi:10.1016/S0166-218X(01)00237-2 .
• Meredith, Guy H. J.; Lloyd, E. Keith (1973), «The footballers of Croam», Journal of Combinatorial Theory, Series B 15 (2): 161–166, doi:10.1016/0095-8956(73)90016-6 .
• Misra, J.; Gries, David (1992), «A constructive proof of Vizing's Theorem», Information Processing Letters 41 (3): 131–133, doi:10.1016/0020-0190(92)90041-S .
• Muthu, Rahul; Narayanan, N.; Subramanian, C. R. (2007), «Improved bounds on acyclic edge colouring», Discrete Mathematics 307 (23): 3063–3069, doi:10.1016/j.disc.2007.03.006 .
• Nash-Williams, C. St. J. A. (1964), «Decomposition of finite graphs into forests», Journal of the London Mathematical Society, Second Series 39: 12 
• Nemhauser, George L.; Park, Sungsoo (1991), «A polyhedral approach to edge coloring», Operations Research Letters 10 (6): 315–322, doi:10.1016/0167-6377(91)90003-8 .
• Richter, David A. (2011), «How to draw a Tait-colorable graph», στο: Brandes, Ulrik; Cornelsen, Sabine, επιμ., Proc. 18th International Symposium on Graph Drawing (GD 2010), Lecture Notes in Computer Science, 6502, Springer-Verlag, σελ. 353–364, doi:10.1007/978-3-642-18469-7_32, ISBN 978-3-642-18468-0 .
• Sanders, Daniel P.; Zhao, Yue (2001), «Planar graphs of maximum degree seven are class I», Journal of Combinatorial Theory, Series B 83 (2): 201–212, doi:10.1006/jctb.2001.2047 .
• Seymour, P. D. (1979), «On multicolourings of cubic graphs, and conjectures of Fulkerson and Tutte», Proceedings of the London Mathematical Society, Third Series 38 (3): 423–460, doi:10.1112/plms/s3-38.3.423 .
• Schwenk, Allen J. (1989), «Enumeration of Hamiltonian cycles in certain generalized Petersen graphs», Journal of Combinatorial Theory, Series B 47 (1): 53–59, doi:10.1016/0095-8956(89)90064-6 .
• Shannon, Claude E. (1949), «A theorem on coloring the lines of a network», J. Math. Physics 28: 148–151 .
• Skiena, Steven S. (2008), «16.8 Edge Coloring», The Algorithm Design Manual (2nd έκδοση), Springer-Verlag, σελ. 548–550, doi:10.1007/978-1-84800-070-4_16, ISBN 978-1-84800-069-8 . See also web site for this section of the book in the Stony Brook Algorithm Repository.
• Soifer, Alexander (2008), The Mathematical Coloring Book, Springer-Verlag, ISBN 978-0-387-74640-1 .
• Tait, P. G. (1880), «Remarks on the colourings of maps», Proc. R. Soc. Edinburgh 10: 729 .
• Trahtman, Avraham N. (2009), «The road coloring problem», Israel Journal of Mathematics 172 (1): 51–60, doi:10.1007/s11856-009-0062-5 .
• Vizing, V. G. (1964), «On an estimate of the chromatic class of a p-graph», Diskret. Analiz. 3: 25–30 .
• Vizing, V. G. (1965), «Critical graphs with given chromatic class», Metody Diskret. Analiz. 5: 9–17 . (In Russian.)
• Williamson, D. P.; Hall, L. A.; Hoogeveen, J. A.; Hurkens, C. A. J.; Lenstra, J. K.; Sevast'janov, S. V.; Shmoys, D. B. (1997), «Short shop schedules», Operations Research 45 (2): 288–294, doi:10.1287/opre.45.2.288 .
• Zhou, Xiao; Nakano, Shin-ichi; Nishizeki, Takao (1996), «Edge-coloring partial k-trees», Journal of Algorithms 21 (3): 598–617, doi:10.1006/jagm.1996.0061 .