Hamiltonian coloring

Hamiltonian coloring is a type of graph coloring. Hamiltonian coloring uses a concept called detour distance between two vertices of the graph.^[1] It has many applications in different areas of science and technology.

Terminologies

The detour distance between u and v in C₅ is 4

Detour distance

The distance between two vertices in a graph is defined as the minimum of lengths of paths connecting those vertices. The detour distance between two vertices, say, u and v is defined as the length of the longest u-v path in the graph.^[1] In the case of a tree the detour distance between any two vertices is same as the distance between the two vertices.

References

1. 1 2 Chartrand, Gary; Zhang, Ping (2009). "14. Colorings, Distance, and Domination". Chromatic Graph Theory. CRC Press. pp. 397–438.