| 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 (print) |
| ISSN:
|
1572-9141 (online) |
| 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)$. (English) |
| 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:
|
2020-07-03 |
| 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, 10.1016/j.dam.2004.08.007 |
| Reference:
|
[3] G. Chartrand, L. Nebeský, and P. Zhang: On hamiltonian colorings of graphs.Discrete Mathematics 290 (2005), 133–134. MR 2123385, 10.1016/j.disc.2004.10.009 |
| 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 |
| . |
