Publications related to On coloring problems with local constraints

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.

Extended Formulations from Communication Protocols in Output-Efficient Time

Yuri Faenza, Manuel Francesco Aprile

Deterministic protocols are well-known tools to obtain extended formulations, with many applications to polytopes arising in combinatorial optimization. Although constructive, those tools are not output-efficient, since the time needed to produce the exten ...

SPRINGER INTERNATIONAL PUBLISHING AG2019

Fast Approximate Spectral Clustering for Dynamic Networks

Pierre Vandergheynst, Lionel Jérémie Martin, Andreas Loukas

Spectral clustering is a widely studied problem, yet its complexity is prohibitive for dynamic graphs of even modest size. We claim that it is possible to get information from past cluster assignments to expedite computation. Our approach builds on a recen ...

2018

On vertices and facets of combinatorial 2-level polytopes

Yuri Faenza, Manuel Francesco Aprile, Alfonso Bolívar Cevallos Manzano

2-level polytopes naturally appear in several areas of mathematics, including combinatorial optimization, polyhedral combinatorics, communication complexity, and statistics. We investigate upper bounds on the product of the number of facets and the number ...

Springer2016

The Erdos-Hajnal conjecture for rainbow triangles

János Pach

We prove that every 3-coloring of the edges of the complete graph on n vertices without a rainbow triangle contains a set of order ohm(n(1/3) log(2) n) which uses at most two colors, and this bound is tight up to a constant factor. This verifies a conjectu ...

Academic Press Inc Elsevier Science2015

Detecting nanoscale vibrations as signature of life

Giovanni Dietler, Sandor Kasas, Giovanni Longo, Francesco Simone Ruggeri, Petar Stupar

The existence of life in extreme conditions, in particular in extraterrestrial environments, is certainly one of the most intriguing scientific questions of our time. In this report, we demonstrate the use of an innovative nanoscale motion sensor in life-s ...

National Academy of Sciences2015

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

On coloring problems with local constraints

Graph Chatbot

Chat with Graph Search

Extended Formulations from Communication Protocols in Output-Efficient Time

Fast Approximate Spectral Clustering for Dynamic Networks

A Dichotomy for Real Weighted Holant Problems

On vertices and facets of combinatorial 2-level polytopes

The Erdos-Hajnal conjecture for rainbow triangles

Detecting nanoscale vibrations as signature of life

Coloring Relatives of Interval Overlap Graphs via On-line Games

Triangle-free intersection graphs of line segments with large chromatic number

Coloring Intersection Graphs of Arc-Connected Sets in the Plane

Applications of a New Separator Theorem for String Graphs

Coloring Relatives of Interval Overlap Graphs via On-line Games

A Dichotomy for Real Weighted Holant Problems

Extended Formulations from Communication Protocols in Output-Efficient Time

Fast Approximate Spectral Clustering for Dynamic Networks

On vertices and facets of combinatorial 2-level polytopes

The Erdos-Hajnal conjecture for rainbow triangles

Detecting nanoscale vibrations as signature of life

Triangle-free intersection graphs of line segments with large chromatic number

Coloring Intersection Graphs of Arc-Connected Sets in the Plane

Applications of a New Separator Theorem for String Graphs