𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Vertex-distinguishing proper edge-colorings

✍ Scribed by Burris, A. C.; Schelp, R. H.

Publisher
John Wiley and Sons
Year
1997
Tongue
English
Weight
146 KB
Volume
26
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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{(i!n i ) 1/i : 1 ≤ i ≤ ∆} where n i denotes the number of vertices of degree i in G. We prove that χ s (G) ≤ C max{n

where C is a constant depending only on ∆. Some results for special classes of graphs, notably trees, are also presented.

📜 SIMILAR VOLUMES

On the Vertex-Distinguishing Proper Edge
On the Vertex-Distinguishing Proper Edge-Colorings of Graphs
✍ Cristina Bazgan; Amel Harkat-Benhamdine; Hao Li; Mariusz Woźniak 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 189 KB

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. Introducti

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

Kr-Free Uniquely Vertex Colorable Graphs
Kr-Free Uniquely Vertex Colorable Graphs with Minimum Possible Edges
✍ S. Akbari; V.S. Mirrokni; B.S. Sadjad 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 112 KB

We construct counterexamples to the conjecture of Xu (1990, J. Combin. Theory Ser. B 50, 319 320) that every uniquely r-colorable graph of order n with exactly (r&1) n&( r2 ) edges must contain a K r . ## 2001 Academic Press Harary et al. [4] constructed uniquely r-colorable graphs containing no

Proper path-factors and interval edge-co
Proper path-factors and interval edge-coloring of (3,4)-biregular bigraphs
✍ Armen S. Asratian; Carl Johan Casselgren; Jennifer Vandenbussche; Douglas B. Wes 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 138 KB

## Abstract An __interval coloring__ of a graph __G__ is a proper coloring of __E__(__G__) by positive integers such that the colors on the edges incident to any vertex are consecutive. A (3,4)‐__biregular bigraph__ is a bipartite graph in which each vertex of one part has degree 3 and each vertex