# Article

 Title: The hamiltonian chromatic number of a connected graph without large hamiltonian-connected subgraphs  (English) Author: Nebeský, Ladislav Language: English Journal: Czechoslovak Mathematical Journal ISSN: 0011-4642 Volume: 56 Issue: 2 Year: 2006 Pages: 317-338 Summary lang: English . Category: math . Summary: If $G$ is a connected graph of order $n \ge 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 $\vert c(x) - c(y)\vert \ge 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 \ge 3$. Assume that there exists a subgraph $F$ of $G$ such that $F$ is a hamiltonian-connected graph of order $i$, where $2 \le i \le \frac{1}{2}(n + 1)$. Then $\mathop {\mathrm hc}(G) \le (n - 2)^2 + 1 - 2(i - 1)(i - 2)$. Keyword: connected graphs Keyword: hamiltonian-connected subgraphs Keyword: hamiltonian colorings Keyword: hamiltonian chromatic number MSC: 05C15 MSC: 05C38 MSC: 05C45 MSC: 05C78 idZBL: Zbl 1164.05356 idMR: MR2291739 . Date available: 2009-09-24T11:33:22Z Last updated: 2012-05-31 Stable URL: http://hdl.handle.net/10338.dmlcz/128069 . Reference: [1] G.  Chartrand and L.  Lesniak: Graphs & Digraphs. Third edition.Chapman & Hall, London, 1996. MR 1408678 Reference: [2] G.  Chartrand, L.  Nebeský, and P.  Zhang: Hamiltonian colorings of graphs.Discrete Appl. Math. 146 (2005), 257–272. MR 2115148 Reference: [3] G.  Chartrand, L.  Nebeský, and P.  Zhang: On hamiltonian colorings of graphs.Discrete Mathematics 290 (2005), 133–134. MR 2123385 Reference: [4] G.  Chartrand, L.  Nebeský, and P.  Zhang: Bounds for the hamiltonian chromatic number of a graph.Congressus Numerantium 157 (2002), 113–125. MR 1985129 Reference: [5] L.  Nebeský: Hamiltonian colorings of connected graphs with long cycles.Math. Bohem. 128 (2003), 263–275. MR 2012604 .

## Files

Files Size Format View
CzechMathJ_56-2006-2_4.pdf 339.0Kb application/pdf View/Open

Partner of