Publications by Tinaz Ekim | EPFL Graph Search

Related publications (13)

Polar cographs

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

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

Partitioning cographs into cliques and stable sets

Dominique de Werra, Tinaz Ekim

We consider the problem of partitioning the node set of a graph into p cliques and k stable sets, namely the (p,k)-coloring problem. Results have been obtained for general graphs \cite{hellcomp}, chordal graphs \cite{hellchordal} and cacti for the case whe ...

2005

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

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

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

Split-critical and uniquely split-colorable graphs

Dominique de Werra, Tinaz Ekim, Bernard Ries

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

(p,k)-coloring problems in line graphs

Dominique de Werra, Tinaz Ekim

2005

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

Tinaz Ekim

Graph Chatbot

Polar cographs

Partitioning graphs into complete and empty graphs

Partitioning cographs into cliques and stable sets

Polarity of chordal graphs

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

Generalized vertex coloring problems using split graphs

Split-critical and uniquely split-colorable graphs

(p,k)-coloring problems in line graphs

Construction of balanced sports schedules using partitions into subleagues

On the approximation of Min Split-coloring and Min Cocoloring

On split-coloring problems

Polar cographs (vol 156, pg 1652, 2008)

Construction of sports schedules with multiple venues