Name
Abstract | ||
|---|---|---|
J. Makowsky and B. Zilber (2004) showed that many variations of graph colorings, called CP-colorings in the sequel, give rise to graph polynomials. This is true in particular for harmonious colorings, convex colorings, mcct-colorings, and rainbow colorings, and many more. N. Linial (1986) showed that the chromatic polynomial χ(G;X) is #P-hard to evaluate for all but three values X=0,1,2, where evaluation is in P. This dichotomy includes evaluation at real or complex values, and has the further property that the set of points for which evaluation is in P is finite. We investigate how the complexity of evaluating univariate graph polynomials that arise from CP-colorings varies for different evaluation points. We show that for some CP-colorings (harmonious, convex) the complexity of evaluation follows a similar pattern to the chromatic polynomial. However, in other cases (proper edge colorings, mcct-colorings, H-free colorings) we could only obtain a dichotomy for evaluations at non-negative integer points. We also discuss some CP-colorings where we only have very partial results. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.aam.2017.04.005 | Advances in Applied Mathematics |
Keywords | Field | DocType |
05C15,05C31,05C85,68Q17,68W05 | Integer,Discrete mathematics,Graph,Combinatorics,Chromatic scale,Polynomial,Mathematical analysis,Regular polygon,Chromatic polynomial,Univariate,Rainbow,Mathematics | Journal |
Volume | ISSN | Citations |
94 | 0196-8858 | 0 |
PageRank | References | Authors |
0.34 | 20 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrew Goodall | 1 | 12 | 4.91 |
| M. Hermann | 2 | 0 | 0.34 |
| tomer kotek | 3 | 66 | 10.97 |
| Johann A. Makowsky | 4 | 509 | 130.82 |
| S. D. Noble | 5 | 83 | 9.56 |