UP - logo
Fakulteta za informacijske študije v Novem mestu (FIS)
  • Variations on the Petersen colouring conjecture [Elektronski vir]
    Pirot, François ; Sereni, Jean-Sébastien ; Škrekovski, Riste
    The Petersen colouring conjecture states that every bridgeless cubic graph admits an edge-colouring with 5 colours such that for every edge e, the set of colours assigned to the edges adjacent to e ... has cardinality either 2 or 4, but not 3. We prove that every bridgeless cubic graph G admits an edge-colouring with 4 colours such that at most 8|E(G)|/15 edges do not satisfy the above condition. This bound is tight and the Petersen graph is the only connected graph for which the bound cannot be decreased. We obtain such a 4-edge-colouring by using a carefully chosen subset of edges of a perfect matching, and the analysis relies on a simple discharging procedure with essentially no reductions and very few rules.
    Vir: The Electronic journal of combinatorics [Elektronski vir]. - ISSN 1077-8926 (Vol. 27, iss. 1, 2020, str. 1-14)
    Vrsta gradiva - e-članek
    Leto - 2020
    Jezik - angleški
    COBISS.SI-ID - 2048633619

    Povezava(-e):

    https://www.combinatorics.org/ojs/index.php/eljc/article/view/v27i1p8/7993

Vnos na polico