Concept

Graph coloring

Related publications (321)

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.

Pliable Index Coding

Christina Fragouli, Siddhartha Brahma

We formulate a new variant of the index coding problem, where instead of demanding a specific message, clients are pliable, and are interested in receiving any t messages that they do not have. We term this problem pliable index coding or PICOD(t). We prov ...

Ieee-Inst Electrical Electronics Engineers Inc2015

Multi-Graph Learning of Spectral Graph Dictionaries

Pascal Frossard

We study the problem of learning constitutive features for the effective representation of graph signals, which can be considered as observations collected on different graph topologies. We propose to learn graph atoms and build graph dictionaries that pro ...

2015

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

Local topological properties of brain connectivity in minimally-disabled multiple sclerosis patients

Dimitri Nestor Alice Van De Ville, Djalel Eddine Meskaldji, Jonas Richiardi

Understanding brain diseases can benefit from studying network organization of functional connectivity (FC) during resting state. Here we study the local topological properties of FC in minimally-disabled multiple sclerosis (MS) patients by comparison of t ...

2014

PrefEdge: SSD Prefetcher for Large-Scale Graph Traversal

Amitabha Roy

Mining large graphs has now become an important aspect of multiple diverse applications and a number of computer systems have been proposed to provide runtime support. Recent interest in this area has led to the construction of single machine graph computa ...

2014

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

Scale-up Graph Processing in the Cloud: Challenges and Solutions

Willy Zwaenepoel, Amitabha Roy, Jasmina Malicevic

Processing large graphs is an important part of the big-data problem. Recently a number of scale-up systems such as X-Stream, Graphchi and Turbograph have been proposed for processing large graphs using secondary storage on a single machine. The design and ...

Luminance coding in graph-based representation of multiview images

Pascal Frossard, Thomas Maugey

Multi-view video transmission poses great challenges because of its data size and dimension. Therefore, how to design efficient 3D scene representations and coding (of luminance and geometry) has become a critical research topic. Recently, the graph-based ...

2014