No label defined (Q4344207)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1033812
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 1033812

      Statements

      0 references
      0 references
      25 November 1997
      0 references
      precoloring
      0 references
      color
      0 references
      perfect graphs
      0 references
      The following precoloring extension problem \(\text{PE}(m_1,\dots,m_k)\) is considered. Instance: A graph \(G\) and its pairwise disjoint stable sets \(X_1,\dots,X_k\) such that \(|X_i|\leq m_i\). Question: Is there an \(\omega\)-coloring of \(G\) such that each \(X_i\) is contained in a different color class? The main result is the following one: The problem \(\text{PE}(m_1,\dots,m_k)\) restricted to perfect graphs is polynomially solvable iff \(k\leq 2\) and \(m_2\leq 1\), and it is NP-complete otherwise.
      0 references

      Identifiers