Publication

Precoloring with cliques and stable sets in cographs

2006
Reports

Abstract

Precoloring extension problems are known to be NP-complete in several classes of graphs. Here, we consider precolorings of cographs with not only stable sets but also with cliques. We give polynomial time algorithms to extend such a precoloring in an optimal way according to several objective functions.

Official source

Graph Chat

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.

Precoloring with cliques and stable sets in cographs

Chat with Graph Search

(p,q) - Choosability of Grid Graphs

A branch and bound algorithm for disassembly scheduling with assembly product structure⋆

On Linear Arithmetic with Stars