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

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


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


[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.