Abstract | ||
---|---|---|
Given a graph G = (V; E) and a weight function omega : E -> R, a coloring of vertices of G, induced by omega, is defined by chi(omega) (nu) = Sigma(e(sic)nu) omega (e) for all nu is an element of V. In this paper, we show that determining whether a particular graph has a weighting of the edges from {1, 2} that induces a proper vertex coloring is NP-complete. |
Year | Venue | Keywords |
---|---|---|
2011 | DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE | vertex-coloring,1-2-3 conjecture,NP-completeness |
Field | DocType | Volume |
Discrete mathematics,Graph,Combinatorics,Weight function,Vertex (geometry),Omega,Sigma,Mathematics | Journal | 13.0 |
Issue | ISSN | Citations |
3.0 | 1462-7264 | 10 |
PageRank | References | Authors |
0.87 | 2 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Andrzej Dudek | 1 | 114 | 23.10 |
David Wajc | 2 | 29 | 6.67 |