Concept

Edge coloring

Related publications (169)

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.

Fast Computation of Small Cuts via Cycle Space Sampling

David Pritchard

We describe a new sampling-based method to determine cuts in an undirected graph. For a graph (V, E), its cycle space is the family of all subsets of E that have even degree at each vertex. We prove that with high probability, sampling the cycle space iden ...

2011

A computational approach to Conway's thrackle conjecture

János Pach, Radoslav Fulek

A drawing of a graph in the plane is called a thrackle if every pair of edges meets precisely once, either at a common vertex or at a proper crossing. Let t(n) denote the maximum number of edges that a thrackle of n vertices can have. According to a 40 yea ...

2011

Pipeline Synthesis and Optimization of FPGA-based Video Processing Applications with CAL

Marco Mattavelli, Ab Al Hadi Bin Ab Rahman, Anatoly Prihozhy

This paper describes a pipeline synthesis and optimization technique that increases data throughput of FPGA-based system using minimum pipeline resources. The technique is applied on \CAL dataflow language, and designed based on relations, matrices and gra ...

Hindawi Publishing Corporation2011

IMPEDANCE EFFECTS IN THE CLIC DAMPING RINGS

Nicolas Frank Mounet, Eirini Koukovini Platia, Benoît Salvant, Giovanni Rumolo

Due to the unprecedented brilliance of the beams, the performance of the Compact Linear Collider (CLIC) damping rings (DR) is affected by collective effects. Single bunch instability thresholds based on a broad-band resonator model and the associated coher ...

2011

Drawing planar graphs of bounded degree with few slopes

János Pach, Balázs Keszegh, Doemoetoer Palvoelgyi

We settle a problem of Dujmovic, Eppstein, Suderman, and Wood by showing that there exists a function f with the property that every planar graph G with maximum degree d admits a drawing with noncrossing straight-line edges, using at most f(d) different sl ...

Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa2011

Approximating Graphic TSP by Matchings

Ola Nils Anders Svensson

We present a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges in order to make a given graph Eulerian, whereas our approach also allows for the removal of certain edges leadi ...

IEEE Computer Society2011

Split-critical and uniquely split-colorable graphs

Dominique de Werra, Bernard Ries, Tinaz Ekim

The split-coloring problem is a generalized vertex coloring problem where we partition the vertices into a minimum number of split graphs. In this paper, we study some notions which are extensively studied for the usual vertex coloring and the cocoloring p ...

2010

The potential to improve the choice: list conflict-free coloring for geometric hypergraphs

Shakhar Smorodinsky

Given a geometric hypergraph (or a range-space)

H=(V,\cal E)

, a coloring of its vertices is said to be conflict-free if for every hyperedge

S \in \cal E

there is at least one vertex in

S

whose color is distinct from the colors of all other vertices i ...

2010

A bipartite strengthening of the Crossing Lemma

János Pach

Let G = (V, E) be a graph with n vertices and m >= 4n edges drawn in the plane. The celebrated Crossing Lemma states that G has at least Omega(m(3)/n(2)) pairs of crossing edges; or equivalently, there is an edge that crosses Omega(m(2)/n(2)) other edges. ...

2010

Coloring axis-parallel rectangles

János Pach, Gábor Tardos

For every k and r, we construct a finite family of axis-parallel rectangles in the plane such that no matter how we color them with k colors, there exists a point covered by precisely r members of the family, all of which have the same color. For r = 2, th ...

2010

The potential to improve the choice: list conflict-free coloring for geometric hypergraphs

Shakhar Smorodinsky

Given a geometric hypergraph (or a range-space)

H=(V,\cal E)

, a coloring of its vertices is said to be conflict-free if for every hyperedge

S \in \cal E

there is at least one vertex in

S

whose color is distinct from the colors of all other vertices i ...

2010