The hamiltonian chromatic number of a connected graph without large hamiltonian-connected subgraphs. (English) Zbl 1164.05356

Nebeský, Ladislav

Czech. Math. J. 56, No. 2, 317-338 (2006).

Summary: If \(G\)  is a connected graph of order \(n \geq 1\), then by a hamiltonian coloring of  \(G\) 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 V(G)\). Let \(G\)  be a connected graph. By the hamiltonian chromatic number of \(G\) we mean \[ \min (\max (c(z);\, z \in V(G))), \] where the minimum is taken over all hamiltonian colorings  \(c\) of  \(G\).
The main result of this paper can be formulated as follows: Let \(G\)  be a connected graph of order \(n \geq 3\). Assume that there exists a subgraph  \(F\) of  \(G\) such that \(F\)  is a hamiltonian-connected graph of order  \(i\), where \(2 \leq i \leq \frac 12(n + 1)\). Then \(\text{hc}(G) \leq (n - 2)^2 + 1 - 2(i - 1)(i - 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-connected subgraphs; hamiltonian colorings; hamiltonian chromatic number

References:

[1]	G. Chartrand and L. Lesniak: Graphs & Digraphs. Third edition. Chapman & Hall, London, 1996. · Zbl 0890.05001
[2]	G. Chartrand, L. Nebeský, and P. Zhang: Hamiltonian colorings of graphs. Discrete Appl. Math. 146 (2005), 257–272. · Zbl 1056.05054
[3]	G. Chartrand, L. Nebeský, and P. Zhang: On hamiltonian colorings of graphs. Discrete Mathematics 290 (2005), 133–134. · Zbl 1059.05046
[4]	G. Chartrand, L. Nebeský, and P. Zhang: Bounds for the hamiltonian chromatic number of a graph. Congressus Numerantium 157 (2002), 113–125. · Zbl 1029.05059
[5]	L. Nebeský: Hamiltonian colorings of connected graphs with long cycles. Math. Bohem. 128 (2003), 263–275. · Zbl 1050.05055