Załóżmy, że dana jest macierz kwadratowa o $n$ wierszach i kolumnach,
której każdemu elementowi przypisano listę $n$ kolorów. Czy można tak
wybrać po jednym kolorze z każdej listy, aby każdy wiersz i każda
kolumna były tęczowe? Problem ten (tzw. problem Dinitza) jest
szczególnym przypadkiem hipotezy o kolorowaniu z list (List Coloring
Conjecture, LCC), gdzie każdej krawędzi grafu przypisujemy listę złożoną
z tylu kolorów, ile wynosi indeks chromatyczny tego grafu. Hipoteza
mówi, że dla każdego grafu można wybrać z list po jednym kolorze i
uzyskać w ten sposób poprawne kolorowanie krawędziowe. LCC dla grafów
dwudzielnych, czyli problem Dinitza (a w zasadzie jego ogólniejszą
wersję dla multigrafów dwudzielnych) rozwiązał Galvin, wykorzystując
jądra digrafów. W pracy wspomniał o możliwym wyrażeniu części dowodu w
języku stabilnych przydziałów, choć nie skorzystał z tej możliwości.
Wykorzystał ją natomiast Fleiner, który uogólnił wynik na grafy, w
których listy przypisane do dowolnego nieparzystego cyklu nie mają
wspólnego koloru. W czasie wystąpienia przedstawię dowody obu twierdzeń.