Let $G$ be a plane graph (or more generally, a graph embedded on a surface) with a proper edge-coloring of $G$ with $k$ colors $\{1,\ldots,k\}$. I am interested in studying the cyclic permutations of colors that appear in the coloring (with respect to the embedding). More precisely, looking at the cyclic ordering of the edges around a particular vertex, one obtains a cyclic permutation of colors.

Do you know a reference where a problem of the following sort has been studied?

$\bullet$ Determining the minimum number of distinct cyclic permutations that one needs in a $k$-edge-coloring of $G$.
$\bullet$ Determining the maximum number of distinct cyclic permutations that one can obtain in a $k$-edge-coloring of $G$.
$\bullet$ Determining whether there exists a restricted $k$-coloring of $G$ where a particular set of cyclic permutations is forbidden.
$\bullet$ ...

Any reference of this kind would be welcome! The only one I found using a search engine is this website (where the cyclic permutations are used as a tool to study edge-colorings of the Icosahedron), but unfortunately it contains no further references.



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.