Personne
Bartosz Maria Walczak
Cette personne n’est plus à l’EPFL
Publications associées (9)
Decomposition of Multiple Packings with Subquadratic Union Complexity
János Pach, Bartosz Maria Walczak
Suppose k is a positive integer and X is a k-fold packing of the plane by infinitely many arc-connected compact sets, which means that every point of the plane belongs to at most k sets. Suppose there is a function f(n) = o(n(2)) with the property that any ...
Cambridge Univ Press2016Triangle-free intersection graphs of line segments with large chromatic number
Bartosz Maria Walczak, Michal Lason
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 no. Specifically, for each positive integer k we construct a triangle-free fam ...
Academic Press Inc Elsevier Science2014Coloring Intersection Graphs of Arc-Connected Sets in the Plane
Bartosz Maria Walczak, Michal Lason
A family of sets in the plane is simple if the intersection of any subfamily is arc-connected, and it is pierced by a line L if the intersection of any member with L is a nonempty segment. It is proved that the intersection graphs of simple families of com ...
Springer2014Outerplanar graph drawings with few slopes
We consider straight-line outerplanar drawings of outerplanar graphs in which a small number of distinct edge slopes are used, that is, the segments representing edges are parallel to a small number of directions. We prove that Delta - 1 edge slopes suffic ...
Elsevier Science Bv2014Coloring Relatives of Interval Overlap Graphs via On-line Games
The main goal of this paper is to formalize and explore a connection between chromatic properties of graphs defined by geometric representations and competitivity analysis of on-line algorithms. This connection became apparent after the recent construction ...
Springer-Verlag Berlin2014An extremal problem on crossing vectors
Bartosz Maria Walczak, Michal Lason
For positive integers w and k, two vectors A and B from Z(w) are called k-crossing if there are two coordinates i and j such that A[i] - B[i] >= k and B[j] - A[j] >= k. What is the maximum size of a family of pairwise 1-crossing and pairwise non-k-crossing ...
Academic Press Inc Elsevier Science2014Triangle-Free Geometric Intersection Graphs with Large Chromatic Number
Bartosz Maria Walczak, Michal Lason
Several classical constructions illustrate the fact that the chromatic number of a graph may be arbitrarily large compared to its clique number. However, until very recently no such construction was known for intersection graphs of geometric objects in the ...
Springer US2013Coloring Triangle-Free Rectangular Frame Intersection Graphs with O(loglogn) Colors
Recently, Pawlik et al. have shown that triangle-free intersection graphs of line segments in the plane can have arbitrarily large chromatic number. Specifically, they construct triangle-free segment intersection graphs with chromatic number Θ(log log n). ...
2013New Bounds on the Maximum Number of Edges in k-Quasi-Planar Graphs
A topological graph is k-quasi-planar if it does not contain k pairwise crossing edges. An old conjecture states that for every fixed k, the maximum number of edges in a k-quasi-planar graph on n vertices is O(n). Fox and Pach showed that every k-quasi-pla ...
Springer International Publishing2013