This research project is a part of GraDR and so far has been conducted by the following team of researchers from Jagiellonian University in Kraków:
The team is responsible for WP09 "Coloring graphs with geometric representations" and contributes to WP01, WP06, WP10. Complete list of workpackages:
The full description of the project can be found here.
The intersection graph of a family of sets in the plane contains an edge between each pair of intersecting objects. Many researchers have asked whether the chromatic number and the size of the largest clique are related for particular classes of intersection graphs.
In 1970s Paul Erdős asked this question for the case of line segments. We provided a negative answer in:
A. Pawlik, J. Kozik, T. Krawczyk, M. Lasoń, P. Micek, W. T. Trotter, and B. Walczak. Triangle-free intersection graphs of line segments with large chromatic number.
Our construction also disproved a conjecture of Scott [1] that graphs excluding induced subdivisions of any fixed graph have chromatic number bounded by a function of their clique number.
We further generalized the result to any arcwise connected compact set under translation and independent horizontal and vertical scaling. In particular, we answered negatively the question of Gyárfás and Lehel [2] concerning L-shapes. Furthermore, we were
able to restrict the transformation group to homotheties in the case of some common shapes
like circles, square boundaries or equilateral L-shapes. Our result contrasts with the results of Asplund and Grünbaum [3] and Kim, Kostochka, and Nakprasit [4], who give positive answers for rectangles and convex sets, respectively. The results appear in:
A. Pawlik, J. Kozik, T. Krawczyk, M. Lasoń, P. Micek, W. T. Trotter, and B. Walczak. Triangle-free geometric intersection graphs with large chromatic number.
The main underlying idea behind our results is an embedding of on-line one dimensional coloring problems in off-line two dimensional coloring problems. We further expoited this connection and determined that the exact asymptotic worst-case chromatic number of n vertex rectangular frame intersection graphs is O(log log n). We are working on
extending this idea to other shapes, including segments, which appear in the original problem of Erdős. The result has been submitted to SoCG 2013:
T. Krawczyk, A. Pawlik, and B. Walczak. Coloring triangle-free rectangular frame intersection graphs with O(log log n) colors.
Suk [5] gave a positive answer to the question of Erdős in the case of unit-length intervals by generalizing the result of McGuinness [6] concerning triangle-free intersection graphs of simple families of compact sets pierced by a line. We generalized both of these results. In particular, simple families of compact sets pierced by a line have bounded chromatic number when the size of the largest clique is bounded.
More details can be found in the following paper currently in preparation:
M. Lasoń, P. Micek, A. Pawlik, and B. Walczak. Coloring intersection graphs of arcwise connected sets in the plane.
For more complete information on the progress in this area, see GraDR Invididual Project 1.
It is well known that every planar graph has a
Fáry embedding.
Dujmović et al. [1] asked how many different slopes are needed in
such an embedding, relative to the maximum degree of the graph.
Jelínek et al. [2] and later Keszegh et al. [3] answered this question positively for outerplanar and planar graphs, respectively.
For outerplanar drawings of outerplanar graphs, we have shown that Delta-1 directions suffice
for all graphs and are necessary for some:
K. B. Knauer, P. Micek, and B. Walczak. Outerplanar graph drawings with few slopes. COCOON 2012, LNCS 7434, pp. 323-334, Springer, 2012.
What is the minimum number p(k) such that for any point set in the
plane P and a triangle T there is a k-coloring of P such that any
triangle T' a homothetic copy of T containing at least p(k) points
from P contains also one point of each color? We proved that p(k)
=O(k8). This is the first polynomial bound for range spaces induced
by homthetic polygons.
J. Cardinal, K. Knauer, P. Micek, and T. Ueckerdt, Making triangles colorful.
What is the minimum number p(k) such that for any point set in the
plane P there is a k-coloring of P such that any axis-aligned
bottomless rectangle R containing at least p(k) points from P contains
also one point of each color? We proved that 1.67k ≤ p(k) ≤ 3k-2.
A. Asinowski, J. Cardinal, N. Cohen, S. Collette,
T. Hackl, M. Hoffmann, K. Knauer, S. Langerman, M.
Lasoń, P. Micek, G. Rote and T. Ueckerdt,
Coloring hypergraphs induced by dynamic point sets and bottomless rectangles.