Előadó: Hujter Mihály

Előadásának címe: Gráfok színezése és jól karakterizálás

Gráfokat helyesen színezni adott számú színnel általában nem könnyű feladat. Ha sikerrel járunk, az eredmény önmagáért beszél: könnyen ellenőrizhető, hogy helyes a színezés. Ha viszont nem sikerül, általában sokkal nehezebb igazolni, hogy nincs megfelelő színezés. Öt és fél évtizede Hajós György megmutatta, hogy adott k-ra a k színnel nem színezhető gráfokat hogyan lehet felépíteni négyféle operáció váltogatása révén, kiindulva a k+1 pontú teljes gráfból: pont hozzáadása / él hozzáadása / duplikátum pontok közül az egyik elhagyása / két gráfnak egy közös pont mentén történő összekovácsolása egy-egy régi él elhagyásával és egy új él behúzásával.
Gyakorlati alkalmazhatóságtól indíttatva az előadásban azt a problémaváltozatot vizsgáljuk, amikor már egy részben kiszínezett gráf helyes teljes színezésének lehetetlenségét akarjuk konstruktívan megmutatni. A már definiált műveletekhez három újabbat adunk: a fenti módszerrel legyártott gráfokban egy teljes részgráf pontjait különböző színekkel kiszínezzük (de ezt csak egyszer tehetjük meg) / színezett pontokból duplikátumként azonos színű pontokat gyártunk / színezett pontok közötti éleket törlünk.
Bizonyítjuk, hogy ezekkel a műveletekkel olyan és csak olyan előszínezett gráfokhoz jutunk, melyek helyes teljes színezése k színnel lehetetlen.
A gyakorlati alkalmazások szempontjából fontos speciális esetekre külön figyelmet fordítunk.

A következő alkalmak részleteit itt találhatják: http://www.math.bme.hu/diffe/szeminarium/opt.shtml