Publication
Triangle-Free Geometric Intersection Graphs with Large Chromatic Number
Publications associées (44)
Coloring 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 Berlin2014Triangle-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 ...
Springer2014Applications of a New Separator Theorem for String Graphs
An intersection graph of curves in the plane is called a string graph. Matousek almost completely settled a conjecture of the authors by showing that every string graph with m edges admits a vertex separator of size O(root m log m). In the present note, th ...
Cambridge University Press2014Coloring 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). ...
2013On some coloring problems in grids
We study complexity issues related to some coloring problems in grids: we examine in particular the case of List coloring, of Precoloring extension and of (p, q)-List coloring, the case of List coloring in bipartite graphs where lists in the first part of ...
2013On coloring problems with local constraints
We deal with some generalizations of the graph coloring problem on classes of perfect graphs. Namely we consider the μ-coloring problem (upper bounds for the color on each vertex), the precoloring extension problem (a subset of vertices colored beforehand) ...
Elsevier2012Coloring K-k-free intersection graphs of geometric objects in the plane
The intersection graph of a collection C of sets is the graph on the vertex set C, in which C-1 . C-2 is an element of C are joined by an edge if and only if C-1 boolean AND C-2 not equal empty set. Erdos conjectured that the chromatic number of triangle-f ...
2012A note on chromatic properties of threshold graphs
Dominique de Werra, Bernard Ries, Rico Zenklusen
In threshold graphs one may find weights for the vertices and a threshold value t such that for any subset S of vertices, the sum of the weights is at most the threshold t if and only if the set S is a stable (independent) set. In this note we ask a simila ...
2012Coloring fuzzy circular interval graphs
Friedrich Eisenbrand, Martin Niemeier
Given a graph G with nonnegative node labels w, a multiset of stable sets S_1,...,S_k\subseteq V(G) such that each vertex v \in V(G) is contained in w(v) many of these stable sets is called a weighted coloring. The weighted coloring number \chi_w(G) is the ...
Elsevier2012