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

Nebeský, Ladislav

Math. Bohem. 128, No. 3, 263-275 (2003).

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\).

MSC:

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

Keywords:

connected graphs; hamiltonian colorings; circumference