GraDR Invididual Project 5 - Poland

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.

Progress in WP09 "Coloring graphs with geometric representations"

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.


[1] A. D. Scott. Induced trees in graphs of large chromatic number. J. Graph Theory, 24(4):297-311, 1997.
[2] A. Gyárfás and J. Lehel. Covering and coloring problems for relatives of intervals. Discrete Math. 55(2):167-180, 1985.
[3] E. Asplund and B. Grünbaum. On a coloring problem. Math. Scand., 8:181-188, 1960.
[4] S.-J. Kim, A. Kostochka, and K. Nakprasit. On the chromatic number of intersection graphs of convex sets in the plane. Electron. J. Combin., 11(1):#R52, 12 pp., 2004.
[5] A. Suk. Coloring intersection graphs of x-monotone curves in the plane.
[6] S. McGuinness. Colouring arcwise connected sets in the plane I. Graph. Combinator., 16(4):429-439, 2000.

Contributions to WP01 "Slope number"

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.


[1] V. Dujmović, D. Eppstein, M. Suderman, and D. Wood. Drawings of planar graphs with few slopes and segments. Comput. Geom. Theory Appl. 38(3):194-212, 2007.
[2] V. Jelínek, E. Jelínková, J. Kratochvíl, B. Lidický, M. Tesař, and T. Vyskočil. The planar slope number of planar partial 3-trees of bounded degree. GD 2009, LNCS 5849, pp. 304-315, Springer, 2010.
[3] B. Keszegh, D. Pálvölgyi, and J. Pach. Drawing planar graphs of bounded degree with few slopes. GD 2010, LNCS 6502, pp. 293-304, Springer, 2011.

Contributions to WP10 "Intersection and contact representations"

We studied the problem of partial representaton extension, a generalization of the recognition problem for classes of graphs represented geometrically. Namely, some vertices of the graph are represented in the input and the goal is to decide whether this partial representation can be extended to a representation of the entire graph. This problem has been introduced by Klavík, Kratochvíl, and Vyskočil [1]. We have proved that the partial representation extension problem is polynomial-time solvable for permutation graphs and function graphs. We have also proved that the problem for function graphs becomes NP-complete when the partial representation consists of partial functions that should be extended on the whole domain:
P. Klavík, J. Kratochvíl, T. Krawczyk, and B. Walczak. Extending partial representations of function graphs and permutation graphs. ESA 2012, LNCS 7501, pp. 671-682, Springer, 2012.


[1] P. Klavík, J. Kratochvíl, and T. Vyskočil. Extending partial representations of interval graphs. TAMC 2011, LNCS 6648, pp. 276-285, Springer, 2011.

Interactions with ComPoSe project

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.67kp(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.