@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-00957453v1> a dcat:Dataset ;
    dct:description """
              An {\\it orientation} of a graph~$G$ is a digraph~$D$ obtained from~$G$ by replacing each edge by exactly one of the two possible arcs with the same endvertices. For each~$v \\in V(G)$, the \\emph{indegree} of~$v$ in~$D$, denoted by~$d^-_D(v)$, is the number of arcs with head~$v$ in~$D$. An orientation~$D$ of~$G$ is \\emph{proper} if~$d^-_D(u)\\neq d^-_D(v)$, for all~$uv\\in E(G)$. The \\emph{proper orientation number} of a graph~$G$, denoted by~$\\po(G)$, is the minimum of the maximum indegree over all its proper orientations. In this paper, we prove that~$\\po(G) \\leq \\left\\lfloor \\left(\\Delta(G) + \\sqrt{\\Delta(G)}\\right)/2 \\right\\rfloor+ 1$ if~$G$ is a bipartite graph, and~$\\po(G)\\leq 4$ if~$G$ is a tree. % Moreover, we show that deciding whether the proper orientation number is at most~2 and at most~3 % is an $\\NP$-complete problem for planar subcubic graphs and planar bipartite graphs, respectively. It is well-known that~$\\po(G)\\leq \\Delta(G)$, for every graph~$G$. However, we prove that deciding whether~$\\po(G)\\leq \\Delta(G)-1$ is already an~$\\NP$-complete problem. We also show that it is~$\\NP$-complete to decide whether~$\\po(G)\\leq 2$, for planar \\emph{subcubic} graphs~$G$. Moreover, we prove that it is~$\\NP$-complete to decide whether $\\po(G)\\leq 3$, for planar bipartite graphs~$G$ with maximum degree~5.
            """ ;
    dct:identifier "Report N°: RR-8492" ;
    dct:issued "2026-05-06T02:25:09.964682"^^xsd:dateTime ;
    dct:language "en" ;
    dct:modified "2026-05-06T02:25:09.964686"^^xsd:dateTime ;
    dct:publisher <https://rec.harvest-normandie.data4citizen.com/organization/cce9db95-46d9-4dc2-84b6-764215d0a002> ;
    dct:title "On the proper orientation number of bipartite graphs" ;
    dcat:contactPoint [ a vcard:Organization ;
            vcard:fn "CCSD" ] ;
    dcat:distribution <https://rec.harvest-normandie.data4citizen.com/dataset/oai-hal-hal-00957453v1/resource/510cc889-a74d-4f4a-a035-11e2af771c94> ;
    dcat:keyword "bipartite-graph",
        "graph-colouring",
        "infoeu-reposemanticsreport",
        "infoinfo-cccomputer-science-cscomputational-complexity-cscc",
        "mathmath-comathematics-mathcombinatorics-mathco",
        "proper-orientation",
        "reports" ;
    dcat:landingPage <https://inria.hal.science/hal-00957453> .

<https://rec.harvest-normandie.data4citizen.com/dataset/oai-hal-hal-00957453v1/resource/510cc889-a74d-4f4a-a035-11e2af771c94> a dcat:Distribution ;
    dct:format "HTML" ;
    dct:issued "2026-05-06T02:25:09.978148"^^xsd:dateTime ;
    dct:modified "2026-05-06T02:25:09.954867"^^xsd:dateTime ;
    dct:title "On the proper orientation number of bipartite graphs" ;
    dcat:accessURL <https://inria.hal.science/hal-00957453> .

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

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