Description
Absztrakt:
A kutatás során az irányított gráfok csúcsainak színezésével foglalkoztunk, hangsúlyt fektetve a hét és nyolc csúcsú orientált gráfokra, a listaszínezésre és az irányított három hosszú köröket nem tartalmazó orientált gráfokra.
Egy irányított gráf dikromatikus száma azt mutatja meg, hogy legalább hány színre van szükség a csúcsok színezéséhez úgy, hogy ne legyen a gráfban egyszínű irányított kör. Egy orientált gráf úgy keletkezik egy irányítatlan egyszerű gráfból, hogy az éleit a két lehetséges irány valamelyikébe irányítjuk. Olyan orientált gráfokat vizsgálunk, melyeknek a dikromatikus száma nagyobb, mint 2. Egy ilyen D gráf 3-dikritikus, ha D bármelyik irányított élének eltávolítása a dikromatikus számot 2-re csökkenti.
A kutatás során végtelen sok 3-dikritikus orientált gráfot konstruáltunk. Neumann-Lara megtalálta a négy 7 csúcsú 3-dikromatikus tournamentet. [1] Mi megkerestük azokat a 8 csúcsú 3-dikromatikus tournamenteket, amelyek ezeket nem tartalmazzák, és az összes 3-dikritikus orientált gráfot 8 csúcson, ezekből 64, illetve 159 van. Meghatároztuk azon irányított élek minimális számát, amivel egy 3-dikritikus orientált gráf rendelkezhet. Létezik egy egyedi orientált gráf 7 csúccsal és 20 irányított éllel.
Konstruáltunk olyan gráfokat, melyeknek listadikromatikus száma nagyobb, mint a dikromatikus száma, és 3-dikromatikus orientált gráfokat irányított három hosszú körök nélkül.
[1] V. Neumann-Lara. The 3 and 4-dichromatic tournaments of minimum order. Discrete Mathematics Volume 135, Issues 1–3, 233–243, (1994)
Join Zoom Meeting
https://us05web.zoom.us/j/89241661674?pwd=SEFKajlNNndid2crbmMyK2xkRUhBZz09
Meeting ID: 892 4166 1674
Passcode: J0K7NK