przypuszczenie Dinitza
W kombinatoryce twierdzenie Dinitza (wcześniej znane jako hipoteza Dinitza ) jest stwierdzeniem dotyczącym rozszerzenia tablic na częściowe kwadraty łacińskie , zaproponowane w 1979 r. przez Jeffa Dinitza i udowodnione w 1994 r. przez Freda Galvina .
Twierdzenie Dinitza mówi, że mając kwadratową tablicę n × n , zbiór m symboli z m ≥ n , oraz dla każdej komórki tablicy zestaw n elementów wylosowany z puli m symboli, można wybrać sposób oznaczania każdej komórki jednym z tych elementów w taki sposób, aby żaden wiersz ani kolumna nie powtarzały symbolu. W teorii grafów można również sformułować , że indeks chromatyczny listy pełnego wykresu dwudzielnego równy . Oznacza to, że jeśli każdej krawędzi kompletnego wykresu przypisano zestaw , możliwe jest wybranie jednego z przypisanych kolorów dla każdej krawędzi w taki sposób, że żadne dwie krawędzie padające na ten sam wierzchołek nie mają tego samego kolor.
Dowód Galvina uogólnia się do stwierdzenia, że dla każdego multigrafu dwudzielnego indeks chromatyczny listy jest równy jego indeksowi chromatycznemu . Bardziej ogólna hipoteza kolorowania listy krawędzi mówi, że to samo dotyczy nie tylko grafów dwudzielnych, ale także dowolnego multigrafu bez pętli. Jeszcze bardziej ogólna hipoteza głosi, że liczba chromatyczna grafów bez pazurów jest zawsze równa ich liczbie chromatycznej . Twierdzenie Dinitza jest również powiązane z hipotezą bazową Roty .
Linki zewnętrzne