@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-00926924v1> a dcat:Dataset ;
    dct:description """
              A b-coloring of a graph is a proper coloring such that every color class contains a vertex that is adjacent to all other color classes. The b-chromatic number of a graph G, denoted by \\chi_b(G), is the maximum number t such that G admits a b-coloring with t colors. A graph G is called b-continuous if it admits a b-coloring with t colors, for every t = \\chi(G),\\ldots,\\chi_b(G), and b-monotonic if \\chi_b(H_1) \\geq \\chi_b(H_2) for every induced subgraph H_1 of G, and every induced subgraph H_2 of H_1. We investigate the b-chromatic number of graphs with stability number two. These are exactly the complements of triangle-free graphs, thus including all complements of bipartite graphs. The main results of this work are the following: - We characterize the b-colorings of a graph with stability number two in terms of matchings with no augmenting paths of length one or three. We derive that graphs with stability number two are b-continuous and b-monotonic. - We prove that it is NP-complete to decide whether the b-chromatic number of co-bipartite graph is at most a given threshold. - We describe a polynomial time dynamic programming algorithm to compute the b-chromatic number of co-trees. - Extending several previous results, we show that there is a polynomial time dynamic programming algorithm for computing the b-chromatic number of tree-cographs. Moreover, we show that tree-cographs are b-continuous and b-monotonic.
            """ ;
    dct:identifier "hal-00926924" ;
    dct:issued "2026-05-07T13:27:20.192097"^^xsd:dateTime ;
    dct:language "en" ;
    dct:modified "2026-05-07T13:27:20.192102"^^xsd:dateTime ;
    dct:publisher <https://rec.harvest-normandie.data4citizen.com/organization/cce9db95-46d9-4dc2-84b6-764215d0a002> ;
    dct:title "b-coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs" ;
    dcat:contactPoint [ a vcard:Organization ;
            vcard:fn "CCSD" ] ;
    dcat:distribution <https://rec.harvest-normandie.data4citizen.com/dataset/oai-hal-hal-00926924v1/resource/97f0e3bd-bb88-4104-8854-114210ec8454> ;
    dcat:keyword "infoeu-reposemanticspreprint",
        "infoinfo-cccomputer-science-cscomputational-complexity-cscc",
        "infoinfo-dmcomputer-science-csdiscrete-mathematics-csdm",
        "mathmath-comathematics-mathcombinatorics-mathco",
        "preprints-working-papers-" ;
    dcat:landingPage <https://hal.science/hal-00926924> .

<https://rec.harvest-normandie.data4citizen.com/dataset/oai-hal-hal-00926924v1/resource/97f0e3bd-bb88-4104-8854-114210ec8454> a dcat:Distribution ;
    dct:format "HTML" ;
    dct:issued "2026-05-07T13:27:20.196770"^^xsd:dateTime ;
    dct:modified "2026-05-07T13:27:20.184729"^^xsd:dateTime ;
    dct:title "b-coloring is NP-hard on co-bipartite graphs and polytime solvable on tree-cographs" ;
    dcat:accessURL <https://hal.science/hal-00926924> .

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

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