https://scholars.lib.ntu.edu.tw/handle/123456789/30207
Title: | A note on the Gallai-Roy-Vitaver Theorem | Authors: | Chang, Gerard-J. Tong, Li-Da Yan, Jing-Ho Yeh, Hong-Gwa |
Keywords: | Coloring;k-Coloring;Chromatic number;Path;Tournament | Issue Date: | 2002 | Start page/Pages: | 441-444 | Source: | Discrete mathematics 256 | Abstract: | The well-known theorem by Gallai–Roy–Vitaver says that every digraph G has a directed path with at least X(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 X(G)-coloring, he proved that the path can be required to start at any vertex & 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. |
URI: | http://ntur.lib.ntu.edu.tw//handle/246246/200609271211154455 | Other Identifiers: | 200609271211154455 |
Appears in Collections: | 數學系 |
File | Description | Size | Format | |
---|---|---|---|---|
000111.pdf | 73.39 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.