Publications by Tinaz Ekim | EPFL Graph Search

Polar cographs (vol 156, pg 1652, 2008)

Elsevier Science Bv2014

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

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

Elsevier2009

A tutorial on the use of graph coloring for some problems in robotics

Dominique de Werra, Tinaz Ekim

We study the problem where a robot has to pick up items of different sizes which are stored along a corridor. A natural requirement is that the items have to be collected in decreasing order of their sizes. We deal with various systems according to the loc ...

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

Polar cographs

Dominique de Werra, Tinaz Ekim

Polar graphs are a natural extension of some classes of graphs like bipartite graphs, split graphs and complements of bipartite graphs. A graph is (s, k)-polar if there exists a partition A, B of its vertex set such that A induces a complete s-partite grap ...

Elsevier2008

Construction of balanced sports schedules using partitions into subleagues

Dominique de Werra, Tinaz Ekim

Direct constructions for balanced tournaments known so far solve problems with 2n teams if 2n mod 3 not equal 1 or 2n = 2(p), p >= 3 or n is odd. Our construction uses an arbitrary partition of the league into subleagues. It solves more than half of the mi ...

2008

Generalized vertex coloring problems using split graphs

Tinaz Ekim

Graph theory experienced a remarkable increase of interest among the scientific community during the last decades. The vertex coloring problem (Min Coloring) deserves a particular attention rince it has been able to capture a wide variety of applications. ...

EPFL2006

On the approximation of Min Split-coloring and Min Cocoloring

Dominique de Werra, Tinaz Ekim

2006

Construction of sports schedules with multiple venues

Dominique de Werra, Tinaz Ekim

2006