Publication

Triangle-Free Geometric Intersection Graphs with Large Chromatic Number

Related publications (44)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Coloring Relatives of Interval Overlap Graphs via On-line Games

Bartosz Maria Walczak

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 Berlin2014

Triangle-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 Science2014

Coloring 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 ...

Springer2014

Applications of a New Separator Theorem for String Graphs

János Pach

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 Press2014

Coloring Triangle-Free Rectangular Frame Intersection Graphs with O(loglogn) Colors

Bartosz Maria Walczak

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). ...

2013

On some coloring problems in grids

Dominique de Werra

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 ...

2013

On coloring problems with local constraints

Yuri Faenza

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) ...

Elsevier2012

Coloring K-k-free intersection graphs of geometric objects in the plane

János Pach

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 ...

2012

A 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 ...

2012

Coloring 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