Publications related to The Erdos-Hajnal conjecture for rainbow triangles

Universal Sets for Straight-Line Embeddings of Bicolored Graphs

A set S of n points is 2-color universal for a graph G on n vertices if for every proper 2-coloring of G and for every 2-coloring of S with the same sizes of color classes as G has, G is straight-line embeddable on S. We show that the so-called double chai ...

2011

A complete graph effective medium approximation for lattice and continuum percolation

Claudio Grimaldi

In this paper we introduce an effective medium theory that is capable of describing site percolation in both lattice and continuum three-dimensional systems. By exploiting self-consistency with a complete graph or network of identical conductors, the resul ...

2011

Weighted Gossip: Distributed Averaging Using Non-Doubly Stochastic Matrices

Martin Vetterli, Patrick Thiran, Florence Bénézit

This paper presents a general class of gossip-based averaging algorithms, which are inspired from Uniform Gossip [1]. While Uniform Gossip works synchronously on complete graphs, weighted gossip algorithms allow asynchronous rounds and converge on any conn ...

IEEE2010

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

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

An Optimal Linear-Time Algorithm for Interprocedural Register Allocation in High Level Synthesis Using SSA Form

Paolo Ienne, Philip Brisk, Ajay Kumar Verma

An optimal linear-time algorithm for interprocedural register allocation in high level synthesis is presented. Historically, register allocation has been modeled as a graph coloring problem, which is nondeterministic polynomial time-complete in general; ho ...

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

Degree-constrained edge partitioning in graphs arising from discrete tomography

Dominique de Werra, Bernard Ries

Starting from the basic problem of reconstructing a 2-dimensional image given by its projections on two axes, one associates a model of edge coloring in a complete bipartite graph. The complexity of the case with k=3 colors is open. Variations and special ...

2009

Blockers and transversals

Dominique de Werra, Bernard Ries, Rico Zenklusen

Given an undirected graph G = (V, E) with matching number v(G), we define d-blockers as subsets of edges B such that nu((V, E \ B)) = d. ...

2009

Weighted coloring on planar, bipartite and split graphs: Complexity and approximation

Dominique de Werra

We study complexity and approximation of MIN WEIGHTED NODE COLORING in planar, bipartite and split graphs. We show that this problem is NP-hard in planar graphs, even if they are triangle-free and their maximum degree is bounded above by 4. Then, we prove ...

2009

The Erdos-Hajnal conjecture for rainbow triangles

Graph Chatbot

Chat with Graph Search

Universal Sets for Straight-Line Embeddings of Bicolored Graphs

A complete graph effective medium approximation for lattice and continuum percolation

Weighted Gossip: Distributed Averaging Using Non-Doubly Stochastic Matrices

A bipartite strengthening of the Crossing Lemma

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

An Optimal Linear-Time Algorithm for Interprocedural Register Allocation in High Level Synthesis Using SSA Form

Coloring axis-parallel rectangles

Degree-constrained edge partitioning in graphs arising from discrete tomography

Blockers and transversals

Weighted coloring on planar, bipartite and split graphs: Complexity and approximation

Degree-constrained edge partitioning in graphs arising from discrete tomography

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

Weighted coloring on planar, bipartite and split graphs: Complexity and approximation

A complete graph effective medium approximation for lattice and continuum percolation

A bipartite strengthening of the Crossing Lemma

Coloring axis-parallel rectangles

Blockers and transversals

Universal Sets for Straight-Line Embeddings of Bicolored Graphs

Weighted Gossip: Distributed Averaging Using Non-Doubly Stochastic Matrices

An Optimal Linear-Time Algorithm for Interprocedural Register Allocation in High Level Synthesis Using SSA Form