The hamiltonian chromatic number of a connected graph without large hamiltonian-connected subgraphs

Nebeský, Ladislav. "The hamiltonian chromatic number of a connected graph without large hamiltonian-connected subgraphs." Czechoslovak Mathematical Journal 56.2 (2006): 317-338. <http://eudml.org/doc/31031>.

@article{Nebeský2006,
abstract = {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 \{h\}c\}(G) \le (n - 2)^2 + 1 - 2(i - 1)(i - 2)$.},
author = {Nebeský, Ladislav},
journal = {Czechoslovak Mathematical Journal},
keywords = {connected graphs; hamiltonian-connected subgraphs; hamiltonian colorings; hamiltonian chromatic number; connected graphs; hamiltonian-connected subgraphs; hamiltonian colorings; hamiltonian chromatic number},
language = {eng},
number = {2},
pages = {317-338},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {The hamiltonian chromatic number of a connected graph without large hamiltonian-connected subgraphs},
url = {http://eudml.org/doc/31031},
volume = {56},
year = {2006},
}

TY - JOUR
AU - Nebeský, Ladislav
TI - The hamiltonian chromatic number of a connected graph without large hamiltonian-connected subgraphs
JO - Czechoslovak Mathematical Journal
PY - 2006
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 56
IS - 2
SP - 317
EP - 338
AB - 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 {h}c}(G) \le (n - 2)^2 + 1 - 2(i - 1)(i - 2)$.
LA - eng
KW - connected graphs; hamiltonian-connected subgraphs; hamiltonian colorings; hamiltonian chromatic number; connected graphs; hamiltonian-connected subgraphs; hamiltonian colorings; hamiltonian chromatic number
UR - http://eudml.org/doc/31031
ER -