Concept

Trivially perfect graph

Related publications (59)

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.

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

Optimistic chordal coloring: a coalescing heuristic for SSA form programs

Paolo Ienne, Philip Brisk, Ajay Kumar Verma

The interference graph for a procedure in Static Single Assignment (SSA) Form is chordal. Since the k-colorability problem can be solved in polynomial-time for chordal graphs, this result has generated interest in SSA-based heuristics for spilling and coal ...

Springer US2009

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

Some coloring and walking problems in graphs

Benjamin Leroy-Beaulieu

Graph theory is an important topic in discrete mathematics. It is particularly interesting because it has a wide range of applications. Among the main problems in graph theory, we shall mention the following ones: graph coloring and the Hamiltonian circuit ...

EPFL2008

Densification Arising from Sampling Fixed Graphs

Matthias Grossglauser, Pedram Pedarsani

During the past decade, a number of different studies have identified several peculiar properties of networks that arise from a diverse universe, ranging from social to computer networks. A recently observed feature is known as network densification, which ...

ACM2008

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

Online Coloring of Comparability Graphs: some results

Benjamin Leroy-Beaulieu

We study online partitioning of posets from a graph theoretical point of view, which is coloring and cocoloring in comparability graphs. For the coloring problem, we analyse the First-Fit algorithm and show a ratio of

O(\sqrt{n})

; furthermore, we devise ...

2007

Robust Routing for Dynamic Wireless Networks Based on Stable Embeddings

Matthias Grossglauser, Suhas Diggavi, Dominique Florian Tschopp, Jörg Widmer

Routing packets is a central function of multi-hop wireless networks. Traditionally, there have been two paradigms for routing, either based on the geographical coordinates of the nodes (geographic routing), or based on the connectivity graph (topology-bas ...

2007

Variations of split-coloring in permutation graphs

Dominique de Werra, Tinaz Ekim

Combinatorial optimization problems related to permutations have been widely studied. Here, we consider different generalizations of the usual coloring problem in permutation graphs. A cocoloring is a partition of a permutation into increasing and decreasi ...

2006

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

Online Coloring of Comparability Graphs: some results

Benjamin Leroy-Beaulieu

O(\sqrt{n})

; furthermore, we devise ...

2007