Graph theory question
Jan. 20th, 2024 11:05 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
jackQuestion 1
You have a graph on an even number P people where each node has E=3 edges connected to it. You colour in one edge. Then you colour in another edge such that each person has at most one coloured edge, aka not touching a previous coloured edge (without planning ahead). You keep doing this as long as you can.
I think for some graphs (e.g. 4 people, or 6 people each connected to the adjacent people and the opposite person) you are guaranteed to be able to colour P/2 edges so that each person touches exactly one coloured edge, whatever your early choices were. Whereas for other graphs (e.g. the corners of a triangular prism?) you can end up in a "dead end" where you've coloured two edges and then the two people left over with no coloured edge have no edge between them to colour.
Is there a description of which graphs guarantee and which don't? What about if E=2 (probably usually not guaranteed?). Or E=4?
Question 2
You have a graph with even P nodes each with E=3 edges. There are A=3 acts. In the first, you colour P/2 non-touching edges. In the second you colour P/2 non-touching edges, not colouring edges that were coloured in act 1 (without planning ahead to act 3). In the third act, you also try to colour P/2 non-touching edges that weren't coloured in acts 1 or 2. Are there graphs where if you colour the edges one at a time you're guaranteed to fill in all the edges without discovering you need to backtrack?
What about for different values of E and A? If E is greater than A? If E is ALL the possible edges then it's always possible, but for values less than that?
Question 3
You have a graph with even P nodes each with E=3 edges. There are A=3 acts. In the first, you colour P/2 non-touching edges with +1, 0 or -1. In the second you colour P/2 non-touching edges, not colouring edges that were coloured in act 1, with +1, 0 or -1 (without planning ahead to act 3). In the third act, you also try to colour P/2 non-touching edges that weren't coloured in acts 1 or 2, also with +1, 0 or -1, but try to ensure that three values each node touches sum to 0. Are there graphs that guarantee that's possible in act 3, regardless of what you did in acts 1 and 2?
What if you had E=4 and coloured +1 or -1?
You have a graph on an even number P people where each node has E=3 edges connected to it. You colour in one edge. Then you colour in another edge such that each person has at most one coloured edge, aka not touching a previous coloured edge (without planning ahead). You keep doing this as long as you can.
I think for some graphs (e.g. 4 people, or 6 people each connected to the adjacent people and the opposite person) you are guaranteed to be able to colour P/2 edges so that each person touches exactly one coloured edge, whatever your early choices were. Whereas for other graphs (e.g. the corners of a triangular prism?) you can end up in a "dead end" where you've coloured two edges and then the two people left over with no coloured edge have no edge between them to colour.
Is there a description of which graphs guarantee and which don't? What about if E=2 (probably usually not guaranteed?). Or E=4?
Question 2
You have a graph with even P nodes each with E=3 edges. There are A=3 acts. In the first, you colour P/2 non-touching edges. In the second you colour P/2 non-touching edges, not colouring edges that were coloured in act 1 (without planning ahead to act 3). In the third act, you also try to colour P/2 non-touching edges that weren't coloured in acts 1 or 2. Are there graphs where if you colour the edges one at a time you're guaranteed to fill in all the edges without discovering you need to backtrack?
What about for different values of E and A? If E is greater than A? If E is ALL the possible edges then it's always possible, but for values less than that?
Question 3
You have a graph with even P nodes each with E=3 edges. There are A=3 acts. In the first, you colour P/2 non-touching edges with +1, 0 or -1. In the second you colour P/2 non-touching edges, not colouring edges that were coloured in act 1, with +1, 0 or -1 (without planning ahead to act 3). In the third act, you also try to colour P/2 non-touching edges that weren't coloured in acts 1 or 2, also with +1, 0 or -1, but try to ensure that three values each node touches sum to 0. Are there graphs that guarantee that's possible in act 3, regardless of what you did in acts 1 and 2?
What if you had E=4 and coloured +1 or -1?