So I gather that this is what you are doing:
1. You are using NodeXL, Analysis, Autofill Columns.
2. In the Vertices tab of the Autofill Columns dialog box, you are specifying Department as the source column for Vertex Color.
3. In the Options for the Vertex Color, you are specifying that the source column's values are Categories.
If that is the case, then NodeXL is assigning a unique color to each set of vertices that have the same Department -- all vertices in the Sociology department might get assigned the color dark blue, for example, while all vertices in the Physics department
might be orange. The colors that NodeXL assigns are predetermined and cannot be changed.
The Edges worksheet and the additional attribute columns you have added to it have nothing to do with how NodeXL autofills the Color column on the Vertices worksheet, so your relationship types are irrelevant.
For more information on Autofill Columns, see the "Automatically Calculating Visual Properties for All Edges, Vertices or Groups" topic at NodeXL, Help, Help.