| Title:
|
Orientations and $3$-colourings of graphs (English) |
| Author:
|
Chouinard-Prévost, Vincent |
| Author:
|
Côté, Alexandre |
| Author:
|
Tardif, Claude |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
45 |
| Issue:
|
3 |
| Year:
|
2004 |
| Pages:
|
549-553 |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
graph colourings |
| Keyword:
|
paths |
| Keyword:
|
Hasse-Gallai-Roy Theorem |
| MSC:
|
05C15 |
| MSC:
|
05C20 |
| idZBL:
|
Zbl 1099.05033 |
| idMR:
|
MR2103149 |
| . |
| Date available:
|
2009-05-05T16:47:24Z |
| Last updated:
|
2012-04-30 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/119482 |
| . |
| Reference:
|
[1] Gallai T.: On directed paths and circuits.Theory of Graphs (Proc. Colloq., Tihany, 1966), Academic Press, New York, 1968, pp.115-118. Zbl 0159.54403, MR 0233733 |
| Reference:
|
[2] Hasse M.: Zur algebraischen Begründung der Graphentheorie. I..Math. Nachr. 28 (1964/1965), 275-290. MR 0179105 |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[5] Roy B.: Nombre chromatique et plus longs chemins d'un graphe.Rev. Francaise Informat. Recherche Opérationelle 1 (1967), 129-132. Zbl 0157.31302, MR 0225683 |
| Reference:
|
[6] Švejdarová I.: Colouring of graphs and dual objects (in Czech).Thesis, Charles University, 2003. |
| . |
