𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the Vertex-Distinguishing Proper Edge-Colorings of Graphs

✍ Scribed by Cristina Bazgan; Amel Harkat-Benhamdine; Hao Li; Mariusz Woźniak

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
189 KB
Volume
75
Category
Article
ISSN
0095-8956

No coin nor oath required. For personal study only.

✦ Synopsis

We prove the conjecture of Burris and Schelp: a coloring of the edges of a graph of order n such that a vertex is not incident with two edges of the same color and any two vertices are incident with different sets of colors is possible using at most n+1 colors.

1999 Academic Press

1. Introduction

In this paper we consider only undirected and simple graphs and we use the standard notation of graph theory (see [3]). Let G=(V, E) be a graph with n vertices with the set of vertices V and the edge set E. We denote by

The problem in which we are interested is a particular case of the great variety of different ways of labeling a graph. The original motivation of studying this problem came from irregular networks. The idea was to weight the edges by positive integers such that the sum of the weights of edges incident to each vertex formed a set of distinct numbers. Consider a function f: E Ä [1, ..., m]. Let f (e) be the number associated to the edge e. Denote by F(v)=[ f(e) | e=uv # E] the multi-set of numbers assigned to the set of edges incident to v and by f (v)= e # F(v) f (e). We call a function f admissible if the function f gives distinct values to the vertices of G. The minimum number m such that an admissible function exists for a graph G (introduced in [7]) is denoted s(G) and is called the irregularity strength

📜 SIMILAR VOLUMES

Vertex-distinguishing proper edge-colori
Vertex-distinguishing proper edge-colorings
✍ Burris, A. C.; Schelp, R. H. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 146 KB

An edge-coloring is called vertex-distinguishing if every two distinct vertices are incident to different sets of colored edges. The minimum number of colors required for a vertex-distinguishing proper edge-coloring of a simple graph G is denoted by χ s (G). A simple count shows that χ s (G) ≥ max{(

On the two-edge-colorings of perfect gra
On the two-edge-colorings of perfect graphs
✍ Chính T. Hoàng 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 409 KB 👁 1 views

## Abstract We investigate the conjecture that a graph is perfect if it admits a two‐edge‐coloring such that two edges receive different colors if they are the nonincident edges of a __P__~4~ (chordless path with four vertices). Partial results on this conjecture are given in this paper. © 1995 Joh

Vertex signatures and edge-4-colorings o
Vertex signatures and edge-4-colorings of 4-regular plane graphs
✍ François Jaeger; Gerhard Koester 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 231 KB 👁 1 views

## Abstract We associate partitions of the edge‐set of a 4‐regular plane graph into 1‐factors or 2‐factors to certain 3‐valued vertex signatures in the spirit of the work by H. Grötzsch [1]. As a corollary we obtain a simple proof of a result of F. Jaeger and H. Shank [2] on the edge‐4‐colorability

Investigation on Interval Edge-Colorings
Investigation on Interval Edge-Colorings of Graphs
✍ A.S. Asratian; R.R. Kamalian 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 380 KB

An edge-coloring of a simple graph \(G\) with colors \(1,2, \ldots, t\) is called an interval \(t\)-coloring [3] if at least one edge of \(G\) is colored by color \(i, i=1, \ldots, t\) and the edges incident with each vertex \(x\) are colored by \(d_{G}(x)\) consecutive colors, where \(d_{G}(x)\) is