Timeline for When is edge colored circulant isomorphism polynomial?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 18, 2015 at 16:58 | comment | added | Dima Pasechnik | @joro - sure, they use the definition I mentioned, too. | |
| Jan 18, 2015 at 16:31 | comment | added | joro | @DimaPasechnik the second paper mentions "edge-colored graphs" without assuming circulants, does your argument still apply? | |
| Jan 18, 2015 at 16:22 | comment | added | Dima Pasechnik | In your reduction attempt, you lose the needed automorphisms, so it does not work. | |
| Jan 18, 2015 at 16:20 | comment | added | Dima Pasechnik | Edge-coloured circulant graphs are edge-coloured graphs admitting a cyclic transitive automorphism group. Colouring here is just a map from a set of colours to the edges. | |
| Jan 18, 2015 at 12:08 | comment | added | joro | @EmilJeřábek In GI edge coloring doesn't necessarily mean PROPER edge coloring. | |
| Jan 18, 2015 at 12:05 | comment | added | Emil Jeřábek | Oh, but Odena defines his terminology clearly: his edge-coloured circulants are not subject to the restriction above, but instead the whole edge-coloured graph structure is supposed to have an $n$-cycle automorphism as in the definition of a circulant. So, your $G'$ is not an edge-coloured circulant unless $G$ was a circulant in the first place. | |
| Jan 18, 2015 at 11:52 | comment | added | Emil Jeřábek | The standard definition of an edge colouring is that no vertex is incident to two edges of the same colour. | |
| Jan 18, 2015 at 10:16 | history | asked | joro | CC BY-SA 3.0 |