A note on the Gallai-Roy-Vitaver Theorem
Resource
Discrete mathematics 256,441-444
Journal
Discrete mathematics 256
Pages
441-444
Date Issued
2002
Date
2002
Author(s)
Chang, Gerard-J.
Tong, Li-Da
Yan, Jing-Ho
Yeh, Hong-Gwa
DOI
200609271211154455
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.
Subjects
Coloring
k-Coloring
Chromatic number
Path
Tournament
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
000111.pdf
Size
73.39 KB
Format
Adobe PDF
Checksum
(MD5):95ad8ab7e139d4ed1a90bec1d4142857