https://scholars.lib.ntu.edu.tw/handle/123456789/30207
標題: | A note on the Gallai-Roy-Vitaver Theorem | 作者: | Chang, Gerard-J. Tong, Li-Da Yan, Jing-Ho Yeh, Hong-Gwa |
關鍵字: | Coloring;k-Coloring;Chromatic number;Path;Tournament | 公開日期: | 2002 | 起(迄)頁: | 441-444 | 來源出版物: | Discrete mathematics 256 | 摘要: | 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 | 其他識別: | 200609271211154455 |
顯示於: | 數學系 |
檔案 | 描述 | 大小 | 格式 | |
---|---|---|---|---|
000111.pdf | 73.39 kB | Adobe PDF | 檢視/開啟 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。