Timeline for edge coloring a directed acyclic graph
Current License: CC BY-SA 4.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 14, 2021 at 8:04 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Apr 16, 2021 at 7:53 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Mar 17, 2021 at 4:58 | answer | added | D.W.♦ | timeline score: 1 | |
| Mar 12, 2021 at 14:17 | history | edited | user7586019 | CC BY-SA 4.0 |
edited body
|
| Mar 12, 2021 at 14:04 | comment | added | user7586019 | I have this problem from a research project. Generally, L is between 3 and 10. The number of paths between s and e is smaller than L!. While there might be multiple solutions for a given graph, only one is wanted as long as it satisfies the requirements. | |
| Mar 12, 2021 at 11:15 | comment | added | D.W.♦ | Can you tell us the motivation or the context where you encountered this task? Was this an exercise in a textbook or class? If so, what have you been studying most recently? Is it a practical problem? If so, how large will $L$ be in practice? | |
| Mar 12, 2021 at 4:01 | comment | added | user7586019 | The solution needs to satisfy your observation: All subpaths between two vertices must have the same length and must be coloured with permutations of the same subset of colours | |
| Mar 12, 2021 at 3:58 | comment | added | user7586019 | Thanks for the reply. L! paths indeed, and the solution is not unique. But my question: is there a systematic way to find one of possible solutions? | |
| Mar 12, 2021 at 3:35 | comment | added | j_random_hacker | There could be more than $L!$ paths, in which case no such edge colouring exists. Restricting to instances with solutions, a simple observation: All subpaths between two vertices must have the same length and must be coloured with permutations of the same subset of colours. | |
| Mar 12, 2021 at 2:47 | review | First posts | |||
| Mar 26, 2021 at 2:45 | |||||
| Mar 12, 2021 at 2:41 | history | asked | user7586019 | CC BY-SA 4.0 |