@prefix dcat: <http://www.w3.org/ns/dcat#> .
@prefix dct: <http://purl.org/dc/terms/> .
@prefix foaf: <http://xmlns.com/foaf/0.1/> .
@prefix vcard: <http://www.w3.org/2006/vcard/ns#> .
@prefix xsd: <http://www.w3.org/2001/XMLSchema#> .

<https://rec.harvest-normandie.data4citizen.com/dataset/oai-hal-hal-00826346v1> a dcat:Dataset ;
    dct:description """
              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.
            """ ;
    dct:identifier "hal-00826346" ;
    dct:issued "2026-05-11T00:20:15.306682"^^xsd:dateTime ;
    dct:language "en" ;
    dct:modified "2026-05-11T00:20:15.306686"^^xsd:dateTime ;
    dct:publisher <https://rec.harvest-normandie.data4citizen.com/organization/cce9db95-46d9-4dc2-84b6-764215d0a002> ;
    dct:title "The vertex-colouring {a,b}-edge-weighting problem is NP-complete for every pair of weights" ;
    dcat:contactPoint [ a vcard:Organization ;
            vcard:fn "CCSD" ] ;
    dcat:distribution <https://rec.harvest-normandie.data4citizen.com/dataset/oai-hal-hal-00826346v1/resource/1c206ede-fa47-4b49-a3c0-572a3110dae7> ;
    dcat:keyword "1-2-3-conjecture",
        "complexity",
        "infoeu-reposemanticsreport",
        "infoinfo-dmcomputer-science-csdiscrete-mathematics-csdm",
        "reports",
        "two-weights",
        "vertex-colouring-edge-weighting-of-graphs" ;
    dcat:landingPage <https://hal.science/hal-00826346> .

<https://rec.harvest-normandie.data4citizen.com/dataset/oai-hal-hal-00826346v1/resource/1c206ede-fa47-4b49-a3c0-572a3110dae7> a dcat:Distribution ;
    dct:format "HTML" ;
    dct:issued "2026-05-11T00:20:15.316919"^^xsd:dateTime ;
    dct:modified "2026-05-11T00:20:15.298058"^^xsd:dateTime ;
    dct:title "The vertex-colouring {a,b}-edge-weighting problem is NP-complete for every pair of weights" ;
    dcat:accessURL <https://hal.science/hal-00826346> .

<https://rec.harvest-normandie.data4citizen.com/organization/cce9db95-46d9-4dc2-84b6-764215d0a002> a foaf:Agent ;
    foaf:name "test_moissonnage_selune" .

<https://hal.science/hal-00826346> a foaf:Document .