Abstract | ||
---|---|---|
The chromatic sum of a graph is the smallest sum of colors among all proper colorings with natural numbers. The strength of a graph is the minimum number of colors necessary to obtain its chromatic sum. A natural generalization of chromatic sum is optimum cost chromatic partition (OCCP) problem, where the costs of colors can be arbitrary positive numbers. Existing results about chromatic sum, strength of a graph, and OCCP problem are presented together with some recent developments. The focus is on polynomial algorithms for some families of graphs and NP-completeness issues. |
Year | DOI | Venue |
---|---|---|
2004 | 10.1155/S0161171204306216 | Int. J. Math. Mathematical Sciences |
Field | DocType | Volume |
Discrete mathematics,Edge coloring,Combinatorics,Foster graph,Friendship graph,Chromatic polynomial,Windmill graph,Moser spindle,Butterfly graph,Mathematics,Critical graph | Journal | 2004 |
Issue | Citations | PageRank |
30 | 10 | 1.11 |
References | Authors | |
15 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ewa Kubicka | 1 | 66 | 9.61 |