(H,C,K)-coloring: Fast, easy, and hard cases

Josep Díaz, Maria Serna, Dimitrios M. Thilikos

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We define a variant of the H-coloring problem by fixing the number of preimages of a subset C of the vertices of H, thus allowing parameterization. We provide sufficient conditions to guarantee that the problem can be solved in O(kn + f(k,H)) steps where f is a function depending only on the number k of fixed preimages and the graph H, and in O(nk+c) steps where c is a constant independent of k. Finally, we prove that whenever the non parameterized vertices induce in G a graph that is bipartite and loopless the problem is NP-complete.

Original languageEnglish (US)
Title of host publicationMathematical Foundations of Computer Science 2001 - 26th International Symposium, MFCS 2001, Proceedings
EditorsJiri Sgall, Ales Pultr, Petr Kolman
PublisherSpringer Verlag
Pages304-315
Number of pages12
ISBN (Print)9783540446835
DOIs
StatePublished - 2001
Event26th International Symposium on Mathematical Foundations of Computer Science, MFCS 2001 - Marianske Lazne, Czech Republic
Duration: Aug 27 2001Aug 31 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2136
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference26th International Symposium on Mathematical Foundations of Computer Science, MFCS 2001
Country/TerritoryCzech Republic
CityMarianske Lazne
Period8/27/018/31/01

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of '(H,C,K)-coloring: Fast, easy, and hard cases'. Together they form a unique fingerprint.

Cite this