Department of
Applied
Mathematics

Partitioning graphs into forests of stars

Paul Dorbec

LaBRI Bordeaux

Abstract

In this talk, we focus on partitions of the vertices of a graph such that the induced subgraph on each part have special property. This generalizes graph coloring, where it is asked that each induced subgraph is a stable set. Recently, Gimbel and Nesetril asked whether there exist triangle free graph that are not partitionable into two cographs. In this talk, we show that there are such graphs, that deciding whether a triangle free graph is cograph 2-partitionable is NP-complete, but that this is always do-able when the maximum average degree (MAD) of the graph is at most 14/5.

This is joint work with Mickael Montassier and Pascal Ochem.