Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6874187 | Information Processing Letters | 2018 | 4 Pages |
Abstract
A total coloring of a graph is an assignment of colors to both its vertices and edges so that adjacent or incident elements acquire distinct colors. In this note, we give a simple greedy algorithm to totally color a rooted path graph G with at most Î(G)+2 colors, where Î(G) is the maximum vertex degree of G. Our algorithm is inspired by a method by Bojarshinov (2001) [3] for interval graphs and provides a new proof that the Total Coloring Conjecture, posed independently by Behzad (1965) [1] and Vizing (1968) [15], holds for rooted path graphs. In the process, we also prove a useful property of greedy neighborhood coloring for chordal graphs.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Martin Charles Golumbic,