VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • Proper conflict-free and unique-maximum colorings of planar graphs with respect to neighborhoods
    Fabrici, Igor ...
    A conflict-free coloring of a graph with respect to open (resp., closed) neighborhood is a coloring of vertices such that for every vertex there is a color appearing exactly once in its open (resp., ... closed) neighborhood. Similarly, a unique-maximum coloring of a graph with respect to open (resp., closed) neighborhood is a coloring of vertices such that for every vertex the maximum color appearing in its open (resp., closed) neighborhood appears exactly once. In this paper, we study both colorings in the proper setting (i.e., we require adjacent vertices to receive distinct colors), focusing mainly on planar graphs. Among other results, we prove that every planar graph admits a proper unique-maximum coloring with respect to open neighborhood using at most ▫$10$▫ colors, and give examples of planar graphs needing at least ▫$6$▫ colors for such a coloring. We also establish tight upper bounds for outerplanar graphs.
    Vir: Discrete applied mathematics. - ISSN 0166-218X (Vol. 324, 2023, str. 80-92)
    Vrsta gradiva - članek, sestavni del ; neleposlovje za odrasle
    Leto - 2023
    Jezik - angleški
    COBISS.SI-ID - 143073795
    DOI

Vnos na polico