Publications related to Optimistic chordal coloring: a coalescing heuristic for SSA form programs

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

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

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

Partitioning graphs into complete and empty graphs

Tinaz Ekim

Given integers j and k and a graph G, we consider partitions of the vertex set of G into j + k parts where j of these parts induce empty graphs and the remaining k induce cliques. If such a partition exists, we say G is a (j, k)-graph. For a fixed j and k ...

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

On the inapproximability of independent domination in 2P3-free perfect graphs

Dominique de Werra

We consider the complexity of approximation for the INDEPENDENT DOMINATING SET problem in 2P(3)-free graphs, i.e., graphs that do not contain two disjoint copies of the chordless path on three vertices as all induced subgraph. We show that, if P not equal ...

2009

Graph coloring with cardinality constraints on the neighborhoods

Dominique de Werra, Bernard Ries

Extensions and variations of the basic problem of graph coloring are introduced. The problem consists essentially in finding in a graph G a k-coloring, i.e., a partition V-1,...,V-k of the vertex set of G such that, for some specified neighborhood (N) over ...

2009

Polarity of chordal graphs

Dominique de Werra, Tinaz Ekim

Polar graphs are a common generalization of bipartite, cobipartite, and split graphs. They are defined by the existence of a certain partition of vertices, which is NP-complete to decide for general graphs. It has been recently proved that for cographs, th ...

2008

Optimistic chordal coloring: a coalescing heuristic for SSA form programs

Graph Chatbot

Chat with Graph Search

A note on chromatic properties of threshold graphs

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

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

Split-critical and uniquely split-colorable graphs

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

Partitioning graphs into complete and empty graphs

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

On the inapproximability of independent domination in 2P3-free perfect graphs

Graph coloring with cardinality constraints on the neighborhoods

Polarity of chordal graphs

A note on chromatic properties of threshold graphs

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

Partitioning graphs into complete and empty graphs

Graph coloring with cardinality constraints on the neighborhoods

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

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

On the inapproximability of independent domination in 2P3-free perfect graphs

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

Split-critical and uniquely split-colorable graphs

Polarity of chordal graphs