Premium
Vertex‐distinguishing edge colorings of random graphs
Author(s) -
Balister P. N.
Publication year - 2002
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.10002
Subject(s) - combinatorics , edge coloring , fractional coloring , vertex (graph theory) , complete coloring , mathematics , random graph , brooks' theorem , graph , discrete mathematics , list coloring , struct , graph power , computer science , line graph , programming language
A proper edge coloring of a simple graph G is called vertex‐distinguishing if no two distinct vertices are incident to the same set of colors. We prove that the minimum number of colors required for a vertex‐distinguishing coloring of a random graph of order n is almost always equal to the maximum degree Δ( G ) of the graph. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 89–97, 2002