Joint seminar in COMBINATORIAL GEOMETRY AND OPTIMIZATION:
Event details
| Date | 18.10.2012 |
| Hour | 16:00 › 17:00 |
| Speaker | Bartosz Walczak |
| Location |
MA B1 524
|
| Category | Conferences - Seminars |
The chromatic number of geometric intersection graphs and related problems
In 1965, Burling found a construction of triangle-free intersection
graphs of three-dimensional boxes with arbitrarily large chromatic
number. Recently, Pawlik et al. proved, using essentially the same
construction, that triangle-free intersection graphs of segments in
the plane have unbounded chromatic number. This works as well for
other types of plane geometric objects, e.g. L-shapes, rectangular
boundaries, or even square boundaries. A natural question arises: Is
the construction optimal?
What is the maximum chromatic number of triangle-free segment
intersection graphs? What is the minimum size of an independent set in
these graphs?
The graphs obtained from the construction have chromatic number
Theta(log log n) and linear independence number. On the other hand,
the upper bound of O(log n) for the chromatic number and the lower
bound of Omega(n/log n) for the independence number follow from
results of McGuinness from 2000.
We establish a relation between geometric intersection graphs and
strategies in some specific games on graphs, which gives us a new
insight into the problems. Consequently, we show the upper bound of
O(log log n) on the chromatic number of triangle-free intersection
graphs of axis-aligned rectangular boundaries. We also show the linear
lower bound on the independence number of such graphs satisfying an
additional technical condition. Hopefully, this will bring us closer
to the solution of the original problems for segments.
This is a joint work with Tomasz Krawczyk and Arkadiusz Pawlik.
In 1965, Burling found a construction of triangle-free intersection
graphs of three-dimensional boxes with arbitrarily large chromatic
number. Recently, Pawlik et al. proved, using essentially the same
construction, that triangle-free intersection graphs of segments in
the plane have unbounded chromatic number. This works as well for
other types of plane geometric objects, e.g. L-shapes, rectangular
boundaries, or even square boundaries. A natural question arises: Is
the construction optimal?
What is the maximum chromatic number of triangle-free segment
intersection graphs? What is the minimum size of an independent set in
these graphs?
The graphs obtained from the construction have chromatic number
Theta(log log n) and linear independence number. On the other hand,
the upper bound of O(log n) for the chromatic number and the lower
bound of Omega(n/log n) for the independence number follow from
results of McGuinness from 2000.
We establish a relation between geometric intersection graphs and
strategies in some specific games on graphs, which gives us a new
insight into the problems. Consequently, we show the upper bound of
O(log log n) on the chromatic number of triangle-free intersection
graphs of axis-aligned rectangular boundaries. We also show the linear
lower bound on the independence number of such graphs satisfying an
additional technical condition. Hopefully, this will bring us closer
to the solution of the original problems for segments.
This is a joint work with Tomasz Krawczyk and Arkadiusz Pawlik.
Practical information
- Informed public
- Free