Highly irregular m-chromatic graphs (Q1117253)

As the authors note, regular graphs have been much studied. Therefore they have turned their attention to highly irregular graphs. These are characterised by the requirement that no two vertices with a common neighbour have the same valency. The bulk of this paper is devoted to trees and bipartite graphs. I will list most of the main results, not all in their strongest form. They observe that a highly irregular tree with maximum valency \(\Delta\) must have at least \(2^{\Delta}\) vertices. (The study of the class of trees with maximum valency \(\Delta\) is made more significant, in their view, by the fact that trees with maximum valency four are of interest in chemistry.) The authors prove that a highly irregular tree on n vertices exists for all n greater than 13, and that a highly irregular tree with maximum valency three on n vertices exists if and only if \(n>8\) and \(n\equiv 2,3\) or 4 (modulo 6). They then turn their attention to bipartite graphs. Here they prove that a highly irregular unicyclic graph with maximum valency three and girth g exists if and only if g is divisible by four. They prove that if a highly irregular bipartite graph with maximum valency four and girth g on n vertices exists then \(n\geq 3g/2\). Finally, they show that if \(n\geq 2\Delta \geq 8\) then there is highly irregular graph on n vertices with maximum valency \(\Delta\).