Hamiltonian colorings of graphs with long cycles. (English) Zbl 1050.05055

Summary: By a Hamiltonian coloring of a connected graph \(G\) of order \(n \geq 1\) we mean a mapping \(c\) of \(V(G)\) into the set of all positive integers such that \(| c(x) - c(y)| \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 \geq 5\) with circumference \(n - 2\).


05C15 Coloring of graphs and hypergraphs
05C38 Paths and cycles
05C45 Eulerian and Hamiltonian graphs
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
Full Text: EuDML