Orientations and 3 -colourings of graphs

Vincent Chouinard-Prévost; Alexandre Côté; Claude Tardif

Commentationes Mathematicae Universitatis Carolinae (2004)

  • Volume: 45, Issue: 3, page 549-553
  • ISSN: 0010-2628

Abstract

top
We provide the list of all paths with at most 16 arcs with the property that if a graph G admits an orientation G → such that one of the paths in our list admits no homomorphism to G → , then G is 3 -colourable.

How to cite

top

Chouinard-Prévost, Vincent, Côté, Alexandre, and Tardif, Claude. "Orientations and $3$-colourings of graphs." Commentationes Mathematicae Universitatis Carolinae 45.3 (2004): 549-553. <http://eudml.org/doc/249327>.

@article{Chouinard2004,
abstract = {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.},
author = {Chouinard-Prévost, Vincent, Côté, Alexandre, Tardif, Claude},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {graph colourings; paths; Hasse-Gallai-Roy Theorem; graph colouring; Hasse-Gallai-Roy theorem},
language = {eng},
number = {3},
pages = {549-553},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {Orientations and $3$-colourings of graphs},
url = {http://eudml.org/doc/249327},
volume = {45},
year = {2004},
}

TY - JOUR
AU - Chouinard-Prévost, Vincent
AU - Côté, Alexandre
AU - Tardif, Claude
TI - Orientations and $3$-colourings of graphs
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 2004
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 45
IS - 3
SP - 549
EP - 553
AB - 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.
LA - eng
KW - graph colourings; paths; Hasse-Gallai-Roy Theorem; graph colouring; Hasse-Gallai-Roy theorem
UR - http://eudml.org/doc/249327
ER -

References

top
  1. Gallai T., On directed paths and circuits, Theory of Graphs (Proc. Colloq., Tihany, 1966), Academic Press, New York, 1968, pp.115-118. Zbl0159.54403MR0233733
  2. Hasse M., Zur algebraischen Begründung der Graphentheorie. I., Math. Nachr. 28 (1964/1965), 275-290. (1964/1965) MR0179105
  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. (2000) MR1778201
  4. Nešetřil J., C. Tardif C., A dualistic approach to bounding the chromatic number of a graph, preprint, 2001, 9 pages ms. MR2368632
  5. Roy B., Nombre chromatique et plus longs chemins d'un graphe, Rev. Francaise Informat. Recherche Opérationelle 1 (1967), 129-132. (1967) Zbl0157.31302MR0225683
  6. Švejdarová I., Colouring of graphs and dual objects (in Czech), Thesis, Charles University, 2003. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.