0
$\begingroup$

I have a problem I am working on that can be reduced to the following case of edge coloring with a special condition.

Let $G$ be a directed graph with infinite vertices that are colored with $m$ colors $\{1,2,...,m\}$, now I want to color edges (with respect to coloring of vertices) in a way that all input edges of every vertex don't have a same color (i.e. For each vertex there exist at least two input edges with different colors). Colors of edges can be different from colors of vertices. Assume that each vertex has more than $2$ inputs.

In other words, I am looking for a spanning subgraph of the initial graph that has two inputs of different colors and at most one output. How can we do this edge coloring? Are there some conditions to guarantee what we want?

Has anyone seen this problem before? Are there any results? Would you recommend any references or perhaps additional directions to search.

$\endgroup$
  • 1
    $\begingroup$ What's the role the vertex coloring playing? Must the colors of edges be different from the colors of vertices? $\endgroup$ – Bullet51 Jul 6 '18 at 14:37
  • 1
    $\begingroup$ Am I missing something? The colors of the vertices have nothing to do with the colors of the edges right? And there are also no conditions on the outputs? Then it seems that there is absolutely nothing stopping you from just taking up a pen and do it. E.g. first color all edges black and then for each vertex randomly select exactly one input and color it white. $\endgroup$ – Vincent Jul 6 '18 at 14:37
  • 1
    $\begingroup$ So what does "dependent" mean? Following @Vincent 's comment, we can color the input edge from the vertex with the "largest" color. $\endgroup$ – Bullet51 Jul 6 '18 at 14:41
  • 1
    $\begingroup$ I am looking for a spanning subgraph of the initial graph that has two inputs of different colors and at most one output @Vincent $\endgroup$ – mahdi meisami Jul 6 '18 at 14:44
  • 1
    $\begingroup$ It is obvious that what you want (two inputs and at least one output, ignore the colors for now) is impossible in finite graphs. So the question if there are conditions on your graph that guarantee that you can find a spanning subgraph of the initial graph that has two inputs and at most one output is already interesting in its own right, with no colors mentioned. On the other hand, once you have such a graph it is clear that you can color the two inputs in each vertex differently because there are no other conditions to reckon with. $\endgroup$ – Vincent Jul 6 '18 at 14:56

Your Answer

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

Browse other questions tagged or ask your own question.