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
25 November 1997
0 references
precoloring
0 references
color
0 references
perfect graphs
0 references
0 references
0 references
0 references
0 references
0.9142214
0 references
0.91379213
0 references
0 references
0.9107756
0 references
0.90849525
0 references
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