Loading...
Please wait, while we are loading the content...
Similar Documents
The vertex-colouring {a,b}-edge-weighting problem is NP-complete for every pair of weights
| Content Provider | Hyper Articles en Ligne (HAL) |
|---|---|
| Author | Bensmail, Julien |
| Copyright Year | 2013 |
| Abstract | Let G be a graph. From an edge-weighting w : E(G) -> {a,b} of G such that a and b are two distinct real numbers, one obtains a vertex-colouring chi_w of G defined as chi_w(u) = sum_{v in N(u)} w(uv) for every u in V(G). If chi_w is a proper colouring of G, i.e. two adjacent vertices of G receive distinct colours by chi_w, then we say that w is vertex-colouring. We investigate the complexity of the problem of deciding whether a graph admits a vertex-colouring edge-weighting taking values among a given pair {a,b}, which is already known to be NP-complete when {a,b} is either {0,1} or {1,2}. We show this problem to be NP-complete for every pair of real weights. |
| Related Links | https://hal.science/hal-00826346/file/1-2-3_complexity.pdf |
| Language | English |
| Publisher | HAL CCSD |
| Access Restriction | Open |
| Subject Keyword | complexity vertex-colouring edge-weighting of graphs two weights |
| Content Type | Text |
| Resource Type | Report |
| Subject | Mathematics Computer Science |
