The k-metric colorings of a graph

Title:

The k-metric colorings of a graph

Creator:

Fujie-Okamoto, Futaba, Renzema, Willem, and Zhang, Ping

Identifier:

https://cdk.lib.cas.cz/client/handle/uuid:1a104ad3-4a65-4a0f-b354-d55cdfeea462
uuid:1a104ad3-4a65-4a0f-b354-d55cdfeea462
doi:10.21136/MB.2012.142787

Subject:

detour distance and metric coloring

Type:

model:article and TEXT

Format:

bez média and svazek

Description:

For a nontrivial connected graph G of order n, the detour distance D(u, v) between two vertices u and v in G is the length of a longest u − v path in G. Detour distance is a metric on the vertex set of G. For each integer k with 1 ≤ k ≤ n−1, a coloring c : V (G) → N is a k-metric coloring of G if |c(u) − c(v)| + D(u, v) ≥ k + 1 for every two distinct vertices u and v of G. The value χ k m(c) of a k-metric coloring c is the maximum color assigned by c to a vertex of G and the k-metric chromatic number χ k m(G) of G is the minimum value of a k-metric coloring of G. For every nontrivial connected graph G of order n, χ 1m(G) ≤ χ 2m(G) ≤ . . . ≤ χ n−1 m (G). Metric chromatic numbers provide a generalization of several well-studied coloring parameters in graphs. Upper and lower bounds have been established for χ k m(G) in terms of other graphical parameters of a graph G and exact values of k-metric chromatic numbers have been determined for complete multipartite graphs and cycles. For a nontrivial connected graph G, the anti-diameter adiam(G) is the minimum detour distance between two vertices of G. We show that the adiam(G)-metric chromatic number of a graph G provides information on the Hamiltonian properties of the graph and investigate realization results and problems on this parameter.

Language:

English

Rights:

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

Coverage:

45-63

Source:

Mathematica bohemica | 2012 Volume:137 | Number:1

Harvested from:

CDK

Metadata only:

false