Article
Full entry |
PDF
(0.1 MB)
Feedback
PDF
(0.1 MB)
Feedback
Keywords:
graph colourings; paths; Hasse-Gallai-Roy Theorem
graph colourings; paths; Hasse-Gallai-Roy Theorem
Summary:
We provide the list of all paths with at most $16$ arcs with the property that if a graph $G$ admits an orientation $\vec{G}$ such that one of the paths in our list admits no homomorphism to $\vec{G}$, then $G$ is $3$-colourable.
References:
[1] Gallai T.: On directed paths and circuits. Theory of Graphs (Proc. Colloq., Tihany, 1966), Academic Press, New York, 1968, pp.115-118. MR 0233733 | Zbl 0159.54403
[2] Hasse M.: Zur algebraischen Begründung der Graphentheorie. I. Math. Nachr. 28 (1964/1965), 275-290. MR 0179105
[3] Nešetřil J., C. Tardif C.: Duality Theorems for Finite Structures (Characterizing Gaps and Good Characterizations). J. Combin. Theory Ser B 80 (2000), 80-97. MR 1778201
[4] Nešetřil J., C. Tardif C.: A dualistic approach to bounding the chromatic number of a graph. preprint, 2001, 9 pages ms. MR 2368632
[5] Roy B.: Nombre chromatique et plus longs chemins d'un graphe. Rev. Francaise Informat. Recherche Opérationelle 1 (1967), 129-132. MR 0225683 | Zbl 0157.31302
[6] Švejdarová I.: Colouring of graphs and dual objects (in Czech). Thesis, Charles University, 2003.
Search
Partner of
