Anzeige
Erschienen in:
14.10.2017
Upper bounds for adjacent vertex-distinguishing edge coloring
Erschienen in: Journal of Combinatorial Optimization | Ausgabe 2/2018
EinloggenAktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
An adjacent vertex-distinguishing edge coloring of a graph is a proper edge coloring such that no pair of adjacent vertices meets the same set of colors. The adjacent vertex-distinguishing edge chromatic number is the minimum number of colors required for an adjacent vertex-distinguishing edge coloring, denoted as \(\chi '_{as}(G)\). In this paper, we prove that for a connected graph G with maximum degree \(\Delta \ge 3\), \(\chi '_{as}(G)\le 3\Delta -1\), which proves the previous upper bound. We also prove that for a graph G with maximum degree \(\Delta \ge 458\) and minimum degree \(\delta \ge 8\sqrt{\Delta ln \Delta }\), \(\chi '_{as}(G)\le \Delta +1+5\sqrt{\Delta ln \Delta }\).