Description
Azt mondjuk, hogy egy (nem feltétlenül helyesen) élszínezett gráf színelkerülően összefüggő, ha bármely színű összes élt elhagyva a gráf összefüggő marad. A színelkerülő összefüggőség definiálható csúcs-színezett gráfokra is, valamint a definíciók általánosíthatók többszörös összefüggőségre, illetve több szín egyidejű elhagyására is. Az előadás során néhány klasszikus összefüggőségi problémát vizsgálunk színelkerülő összefüggőségre nézve, miközben bonyolultságelméleti, matroidelméleti és valószínűségszámítási feladatok is előkerülnek.