Hamiltonian coloring

Hamiltonian coloring, named after William Rowan Hamilton, is a type of graph coloring. Hamiltonian coloring uses a concept called detour distance between two vertices of the graph. It has many applications in different areas of science and technology.

Terminologies

Radio coloring

A graph G with diameter D with n nodes that is colored (i.e. has a positive integer assigned to each vertex) with k colors is called a radio k-coloring G if for every pair of vertices a and b, the sum of the distance between them and the difference between their labels ("colors") is greater than k. For example, two nodes labelled 3 and 7 with a distance of 5 is acceptable for a radio 8-coloring, but not for a radio 9-coloring, since $(7-3)+5=9$, which is not greater than 9.

Antipodal coloring

A radio (d-1)-coloring, that is, where k is equal to one less than the graph's diameter, is known as an antipodal coloring because antipodal vertices may be colored the same, but all nodes between them must be different.

Detour distance

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

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. In the case of a tree the detour distance between any two vertices is same as the distance between the two vertices.

Hamiltonian coloring

Hamiltonian colorings are a variation on antipodal colorings where, instead of considering the regular distance between nodes, the detour distance is instead considered. Specifically, a Hamiltonian coloring's nodes have the property that the detour distance plus the difference in colors is greater than or equal to one less than n, the number of nodes in the graph. If the graph G is a path, then any Hamiltonian coloring is also an antipodal coloring, which is the inspiration for the definition of Hamiltonian coloring.

References

• Chartrand, Gary et al. "Hamiltonian Coloring of Graphs." Discrete Applied Mathematics, vol. 146, no. 3, 15 Mar. 2005, doi:10.1016/j.dam.2004.08.007.