Akademska digitalna zbirka SLovenije - logo
FMF in IMFM, Matematična knjižnica, Ljubljana (MAKLJ)
  • ▫$\Theta$▫-graphs of partial cubes and strong edge colorings
    Kraner Šumenjak, Tadeja
    It was conjectured that the upper bound for the strong chromatic index ▫$s'(G)$▫ of bipartite graphs is ▫$\Delta (G)^2$▫, where ▫$\Delta (G)$▫ is the largest degree of vertices in ▫$G$▫. We study the ... strong edge coloring of some classes of bipartite graphs that belong to the class of partial cubes. We introduce the concept of ▫$\Theta$▫-graph ▫$\Theta (G)$▫ of a partial cube ▫$G$▫, and show that ▫$s'(G) \le \chi(\Theta(G))$▫ for every tree-like partial cube ▫$G$▫. As an application of this bound we derive that ▫$s'(G) \le 2\Delta (G)$▫ if ▫$G$▫ is a ▫$p$▫-expansion graph.
    Vir: Electronic notes in discrete mathematics [Elektronski vir]. - ISSN 1571-0653 (Vol. 28, 2007, str. 521-526)
    Vrsta gradiva - prispevek na konferenci
    Leto - 2007
    Jezik - angleški
    COBISS.SI-ID - 2504492

Vnos na polico