Abstract
In this note we give simple proofs of two results which concerns paths representing all colors in optimal proper vertex-colorings of graphs. One result, due to Fung [2], is about the existence of colorful paths. The other one, due to Li [4], is about the existence of paths starting at any given vertex and representing all colors. Besides, we propose some open problems.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. London: Macmillan, New York: Elsevier 1976
Fung, T.-S.: A colorful path. The Mathematical Gazette 73, 186–188 (1989)
Gallai, T.: On directed paths and circuits. In: Erdös, P., Katona, G.: Theory of Graphs. pp. 115–118 Tihany, New York: Academic Press 1968
Li, H.: A generalization of the Gallai-Roy Theorem. Graphs and Combinatorics 17, 681–685 (2001)
Roy, B.: Nombre chromatique et plus longs chemins d'un graph. Rev. AFIRO 1, 127–132 (1967)
West, D.B.: Introduction to Graph Theory. NJ: Prentice-Hall 1996
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Lin, C. Simple Proofs of Results on Paths Representing All Colors in Proper Vertex-Colorings. Graphs and Combinatorics 23, 201–203 (2007). https://doi.org/10.1007/s00373-007-0694-3
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s00373-007-0694-3