A note on the Gallai-Roy-Vitaver Theorem

Gerard J. Chang, Li Da Tong, Jing Ho Yan, Hong Gwa Yeh

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

The well-known theorem by Gallai-Roy-Vitaver says that every digraph G has a directed path with at least χ(G) vertices; hence this holds also for graphs. Li strengthened the digraph result by showing that the directed path can be constrained to start from any vertex that can reach all others. For a graph G given a proper χ(G)-coloring, he proved that the path can be required to start at any vertex and visit vertices of all colors. We give a shorter proof of this. He conjectured that the same holds for digraphs; we provide a strongly connected counterexample. We also give another extension of the Gallai-Roy-Vitaver Theorem on graphs.

Original languageEnglish
Pages (from-to)441-444
Number of pages4
JournalDiscrete Mathematics
Volume256
Issue number1-2
DOIs
StatePublished - 28 Sep 2002

Keywords

  • Chromatic number
  • Coloring
  • K-Coloring
  • Path
  • Tournament

Fingerprint

Dive into the research topics of 'A note on the Gallai-Roy-Vitaver Theorem'. Together they form a unique fingerprint.

Cite this