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

Title:

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

Creator:

Nebeský, Ladislav

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:6d9cddcc-7d3a-4127-aa9c-ed59465c943d
uuid:6d9cddcc-7d3a-4127-aa9c-ed59465c943d

Subject:

connected graphs, hamiltonian-connected subgraphs, hamiltonian colorings, and hamiltonian chromatic number

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

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

Language:

English

Rights:

http://creativecommons.org/publicdomain/mark/1.0/
policy:public

Coverage:

317-338

Source:

Czechoslovak Mathematical Journal | 2006 Volume:56 | Number:2

Harvested from:

CDK

Metadata only:

false