Premium
A passage time for greedy‐coloring cycles
Author(s) -
Preater J.
Publication year - 1995
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.3240060110
Subject(s) - greedy coloring , colored , fractional coloring , greedy algorithm , vertex (graph theory) , edge coloring , complete coloring , combinatorics , brooks' theorem , graph coloring , mathematics , list coloring , computer science , graph , algorithm , graph power , chordal graph , 1 planar graph , materials science , line graph , composite material
We consider the progress of the greedy vertex coloring algorithm applied to cycle graphs. In particular we study the asymptotic distribution of the number of vertices colored by the algorithm when the third color is first used (if it is).