Počet záznamů: 1  

Matching polytons

  1. 1.
    0512063 - MÚ 2020 RIV US eng J - Článek v odborném periodiku
    Doležal, Martin - Hladký, Jan
    Matching polytons.
    Electronic Journal of Combinatorics. Roč. 26, č. 4 (2019), č. článku P4.38. ISSN 1077-8926
    Grant CEP: GA ČR GA16-07378S
    GRANT EU: European Commission(XE) 628974 - PAECIDM
    Institucionální podpora: RVO:67985840
    Klíčová slova: graphon * matching polytope
    Kód oboru RIV: BA - Obecná matematika
    Obor OECD: Pure mathematics
    Impakt faktor: 0.762, rok: 2018
    https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i4p38

    Hladký, Hu, and Piguet [Tilings in graphons, preprint] introduced the notions of matching and fractional vertex covers in graphons. These are counterparts to the corresponding notions in finite graphs. Combinatorial optimization studies the structure of the matching polytope and the fractional vertex cover polytope of a graph. Here, in analogy, we initiate the study of the structure of the set of all matchings and of all fractional vertex covers in a graphon. We call these sets the matching polyton and the fractional vertex cover polyton. We also study properties of matching polytons and fractional vertex cover polytons along convergent sequences of graphons.As an auxiliary tool of independent interest, we prove that a graphon is r -partite if and only if it contains no graph of chromatic number r+1. This in turn gives a characterization of bipartite graphons as those having a symmetric spectrum.
    Trvalý link: http://hdl.handle.net/11104/0302266
    Název souboruStaženoVelikostKomentářVerzePřístup
    Dolezal3.pdf0489.2 KBVydavatelský postprintvyžádat