0
$\begingroup$

When is it possible to properly color the vertices of a given regular graph uniformly? By uniformly, it is implied that between any two color classes, there exist at least one adjacency(edge) from a vertex in one color class to some vertex in the other color class.

I think this is possible in most Cayley grpahs, and is easily seen in powers of cycles. I suspect the same for any vertex transitive graph. But given any graph(regular), is it always possible to do such a coloring? If the graph be perfect, then I think it would satisfy the above criterion of uniformity. What if the coloring be equitable, that is, if each color class differed by at most one vertex? Thanks beforehand.

Improve this question
$\endgroup$
4
  • $\begingroup$ I presume you mean proper colorings, so that no vertices connected by an edge have distinct colors? $\endgroup$ – Wojowu Apr 23 '19 at 10:34
  • $\begingroup$ @Wojowu yes, the colorings are proper $\endgroup$ – vidyarthi Apr 23 '19 at 10:35
  • 6
    $\begingroup$ If there's no adjacency between two different color classes, then we can define a new proper coloring by merging the color classes. Thus every coloring minimal in the above sense is uniform. $\endgroup$ – LeechLattice Apr 23 '19 at 10:41
  • $\begingroup$ @Bullet51 That was a silly miss! anyways thank you! $\endgroup$ – vidyarthi Apr 23 '19 at 10:44
2
$\begingroup$

(Not a full answer, but too long for a comment)

Fact: there are regular graphs where every equitable coloring has color classes with no edges between them. (As mentioned in comments, if we remove the restriction that the coloring be equitable, the question is no longer interesting.)

Moreover, there are regular, perfect graphs satisfying the above as well (so be careful).

Let $H$ be any $r$-regular graph on $m$ vertices with $\chi(H) > m / (m-r-1)$. Then construct an $m$-regular graph by adding an independent set $S$ of $m-r$ new vertices, which are each connected to all the vertices of $H$. Any coloring of the type we want must have $S$ as one of its independent sets. This means there's a coloring like you want iff there is an equitable coloring of $H$ (of the form you like) having color classes of size roughly $|S| = m-r$. But since $\chi(H) > m / (m-r-1)$, the graph $H$ has no coloring where the sets all have size at least $m-r-1$. Thus, the graph constructed in this way has no coloring of the type we're looking for.

By starting with various graphs $H$, this can be used to construct lots of regular graphs without any colors that you want. For instance, if $H$ is perfect, this construction gives a perfect graph without these colorings.

For concreteness, if $H$ is the disjoint union of $2$ triangles, then $\chi(H) = 3 > m/(m-r-1) = 6 / (6-2-1) = 6/3 = 2$. And the above construction gives a graph with $10$ vertices and no equitable coloring of the type you're asking for.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I hope the graphs you constructed do not cover vertex transitive graphs. Would it? As the new vertices added may not be mapped to the vertices in $H$ $\endgroup$ – vidyarthi Apr 29 '19 at 10:38
  • $\begingroup$ Without thinking too hard, it would probably be difficult to get a vertex-transitive graph in this way. Unsure if vertex-transitive graphs have colorings like you want. $\endgroup$ – Pat Devlin May 6 '19 at 2:49
  • $\begingroup$ Since any vertex can be mapped to any other vertex under an automorphism, I think the colorings also should be uniform in any proper coloring, for otherwise those colorclass that contain vertices which are not adjacent to any other vertex in other color class would be able to be mapped to other color class where uniformity exists. So, I think vertex transitive graphs have the uniformity property. $\endgroup$ – vidyarthi May 6 '19 at 8:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.