67 citations · 244 across the 17 of their papers we have counts for
3 papers · 1 filter
Triangle-free geometric intersection graphs with large chromatic number
Arkadiusz Pawlik, Jakub Kozik, Tomasz Krawczyk +4
Several classical constructions illustrate the fact that the chromatic number of a graph can be arbitrarily large compared to its clique number. However, until very recently, no su…
Triangle-free intersection graphs of line segments with large chromatic number
Arkadiusz Pawlik, Jakub Kozik, Tomasz Krawczyk +4
In the 1970s, Erdos asked whether the chromatic number of intersection graphs of line segments in the plane is bounded by a function of their clique number. We show the answer is n…
Nonrepetitive choice number of trees
Jakub Kozik, Piotr Micek
A nonrepetitive coloring of a path is a coloring of its vertices such that the sequence of colors along the path does not contain two identical, consecutive blocks. The remarkable…