Name
Abstract | ||
|---|---|---|
We investigate a restricted list-coloring problem. Given a graph G = ( V , E ), a non empty set of colors L , and a nonempty subset L ( v ) of L for each vertex v , find an L -coloring of G with the size of each class of colors being equal to a given integer. This restricted list-coloring problem was proposed by de Werra. We prove that this problem is N P-Complete even if the graph is a path with at most two colors on each vertex list. We then give a polynomial algorithm which solves this problem for the case where the total number of colors occurring in all lists is fixed. |
Year | DOI | Venue |
|---|---|---|
1999 | 10.1016/S0012-365X(98)00169-1 | Discrete Mathematics |
Keywords | Field | DocType |
restricted list-coloring problem,list coloring | Integer,Complete coloring,Discrete mathematics,Empty set,Combinatorics,Fractional coloring,Vertex (geometry),List coloring,Vertex cover,Feedback vertex set,Mathematics | Journal |
Volume | Issue | ISSN |
195 | 1-3 | Discrete Mathematics |
Citations | PageRank | References |
7 | 0.61 | 1 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Moshe Dror | 1 | 574 | 64.77 |
| Gerd Finke | 2 | 181 | 15.63 |
| Sylvain Gravier | 3 | 486 | 59.01 |
| Wieslaw Kubiak | 4 | 540 | 62.61 |