The hamiltonian chromatic number of a connected graph without large hamiltonian-connected subgraphs |
| |
Authors: | Ladislav Nebeský |
| |
Affiliation: | (1) Univerzita Karlova v Praze, Filozofická fakulta, nám. J. Palacha 2, 116 38 Praha 1 |
| |
Abstract: | If G is a connected graph of order n ⩾ 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)| ⩾ 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 ∈ V (G). Let G be a connected graph. By the hamiltonian chromatic number of G we mean , 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 ⩾ 3. Assume that there exists a subgraph F of G such that F is a hamiltonian-connected graph of order i, where 2 ⩽ i ⩽ 1/2 (n+1). Then hc(G) ⩽ (n−2)2+1−2(i−1)(i−2). |
| |
Keywords: | connected graphs hamiltonian-connected subgraphs hamiltonian colorings hamiltonian chromatic number |
本文献已被 SpringerLink 等数据库收录! |
|