Skip to main content
Springer Nature Link
Log in

Simple Proofs of Results on Paths Representing All Colors in Proper Vertex-Colorings

  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

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.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
€32.70 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (France)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. London: Macmillan, New York: Elsevier 1976

  2. Fung, T.-S.: A colorful path. The Mathematical Gazette 73, 186–188 (1989)

    Google Scholar 

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

  4. Li, H.: A generalization of the Gallai-Roy Theorem. Graphs and Combinatorics 17, 681–685 (2001)

    Google Scholar 

  5. Roy, B.: Nombre chromatique et plus longs chemins d'un graph. Rev. AFIRO 1, 127–132 (1967)

    Google Scholar 

  6. West, D.B.: Introduction to Graph Theory. NJ: Prentice-Hall 1996

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, National Central University, Chung-Li, 320, Taiwan, R.O.C

    Chiang Lin

Authors
  1. Chiang Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints 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

Download citation

  • Received:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-007-0694-3

Keywords

Search

Navigation