<div dir="ltr"><div style="text-align:center"><span style="background-color:rgb(255,255,255)"><font size="4"><b>Meghívó</b></font><br></span></div><span style="background-color:rgb(255,255,255)"><font size="4"><br></font></span><div style="text-align:left"><div style="text-align:center"><span style="background-color:rgb(255,255,255)"><font>Szeretettel várunk minden</font> kedves érdeklődőt a BME<br>Optimalizálás Szemináriumán!<br></span></div><span style="background-color:rgb(255,255,255)"><br></span></div><div style="text-align:left"><span style="background-color:rgb(255,255,255)"><br>Az előadás részletei:<br><br></span></div><div style="text-align:left"><span style="background-color:rgb(255,255,255)"><span style="font-family:arial,helvetica,sans-serif"><i><b>február 26. (csütörtök), 14.15, H306</b></i><br></span></span></div><div style="text-align:left"><span style="background-color:rgb(255,255,255)"><span style="font-family:arial,helvetica,sans-serif"><br></span></span></div><div style="text-align:left"><span style="background-color:rgb(255,255,255)"><span style="font-family:arial,helvetica,sans-serif"><i><b>Hujter Mihály (BME):<br></b></i><span style="font-size:13px;font-weight:normal;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline">Gráfok színezése és jól karakterizálás</span><b><span style="font-size:13px;font-weight:normal;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline"><br></span></b><i><b><span style="font-size:13px;font-weight:normal;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline"><br></span></b></i></span></span></div><span style="background-color:rgb(255,255,255)"><span style="font-family:arial,helvetica,sans-serif"><i><b><span style="font-size:13px;font-weight:normal;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline"><i><b>Absztrakt:</b></i></span></b></i></span></span><br>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.<br>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.<br>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.<br>A gyakorlati alkalmazások szempontjából fontos speciális esetekre külön figyelmet fordítunk.<br><br><br><span><span style="font-size:10pt;color:rgb(87,87,87);font-family:Arial,sans-serif;line-height:15pt"><font color="#000000">A <b>következő alkalmak</b> részleteit</font></span><span style="text-align:justify"><font face="arial, helvetica, sans-serif"> itt találhatják:<br><br><a href="http://www.math.bme.hu/diffe/szeminarium/opt.shtml" target="_blank">http://www.math.bme.hu/diffe/szeminarium/opt.shtml</a><br><br><br>Üdvözlettel,<br><br>Majoros Csilla</font></span></span><br></div>