Kolorowanie grafów uporządkowanych niezawierających indukowanych wzorców

W niniejszej pracy zajmujemy się problemem -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 -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 -ograniczoności.

We study the problem of -boundedness for ordered graphs excluding a fixed structure (pattern) as an induced subgraph. We present a full characterisation of -bounding patterns on up to 4 vertices, and we characterise all -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 -boundedness problem.