- Tytuł:
-
Kolorowanie grafów uporządkowanych niezawierających indukowanych wzorców
Colouring ordered graphs excluding induced patterns. - Autorzy:
- Mikołajczyk, Piotr
- Opis:
-
W niniejszej pracy zajmujemy się problemem $\chi$-ograniczoności dla grafów uporządkowanych niezawierających ustalonej struktury (wzorca) jako podgrafu indukowanego. Przedstawiamy pełną klasyfikację wzorców na co najwyżej 4 wierzchołkach i charakteryzujemy wszystkie $\chi$-ograniczające wzorce pośród grafów uporządkowanych o nieprzecinających się krawędziach. Wraz ze znanymi uprzednio wynikami, zamieszczamy nowe dowody kolorowalności oraz nową konstrukcję rodziny grafów bez trójkątów o nieograniczonej liczbie chromatycznej. Ponadto prezentujemy przegląd uogólnionych metod i narzędzi, które mogą okazać się pomocne przy podobnych problemach. Na koniec przedstawiamy ciekawe powiązanie pomiędzy kolorowaniem grafów on-line a problemem $\chi$-ograniczoności.
We study the problem of $\chi$-boundedness for ordered graphs excluding a fixed structure (pattern) as an induced subgraph. We present a full characterisation of $\chi$-bounding patterns on up to 4 vertices, and we characterise all $\chi$-bounding patterns among ordered graphs with no crossing edges. Alongside previously known results, we provide new colourability proofs and a new construction of triangle-free graphs with unbounded chromatic number. Additionally, we gather some general methods and tools that can be helpful for similar problems. Finally, we discuss an interesting connection between on-line graph colouring and the $\chi$-boundedness problem. - Dostawca treści:
- Repozytorium Uniwersytetu Jagiellońskiego
Inne