VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
PDF
  • Star edge-coloring of square grids
    Holub, Přemysl ...
    A star edge-coloring of a graph ▫$G$▫ is a proper edge-coloring without bichromatic paths or cycles of length four. The smallest integer ▫$k$▫ such that ▫$G$▫ admits a star edge-coloring with ▫$k$▫ ... colors is the star chromatic index of ▫$G$▫. In the seminal paper on the topic, Dvořák, Mohar, and Šámal asked if the star chromatic index of complete graphs is linear in the number of vertices and gave an almost linear upper bound. Their question remains open, and consequently, to better understand the behavior of the star chromatic index, this parameter has been studied for a number of other classes of graphs. In this paper, we consider star edge-colorings of square grids; namely, the Cartesian products of paths and cycles and the Cartesian products of two cycles. We improve previously established bounds and, as a main contribution, we prove that the star chromatic index of graphs in both classes is either ▫$6$▫ or ▫$7$▫ except for prisms. Additionally, we give a number of exact values for many considered graphs.
    Vir: Applied mathematics and computation. - ISSN 0096-3003 (Vol. 392, 2021, atr. 125741 (16 str.))
    Vrsta gradiva - članek, sestavni del
    Leto - 2021
    Jezik - angleški
    COBISS.SI-ID - 33826307

    Povezava(-e):

    https://www.sciencedirect.com/science/article/pii/S0096300320306949#!
    DOI

Vnos na polico