MATHEMATICA BOHEMICA, Vol. 128, No. 3, pp. 263-275 (2003)

Hamiltonian colorings of graphs with long cycles

Ladislav Nebesky

Ladislav Nebesky, Univerzita Karlova v Praze, Filozoficka fakulta, nam. J. Palacha 2, 116 38 Praha 1, e-mail:

Abstract: By a hamiltonian coloring of a connected graph $G$ of order $n \geq1$ we mean a mapping $c$ of $V(G)$ into the set of all positive integers such that $\vert c(x) - c(y)\vert\geq n - 1 - D_G(x, y)$ (where $D_G(x, y)$ denotes the length of a longest $x-y$ path in $G$) for all distinct $x, y \in G$. In this paper we study hamiltonian colorings of non-hamiltonian connected graphs with long cycles, mainly of connected graphs of order $n \geq5$ with circumference $n - 2$.

Keywords: connected graphs, hamiltonian colorings, circumference

Classification (MSC2000): 05C15, 05C38, 05C45, 05C78

Full text of the article:

[Previous Article] [Next Article] [Contents of this Number] [Journals Homepage]
© 2004–2010 FIZ Karlsruhe / Zentralblatt MATH for the EMIS Electronic Edition