8
$\begingroup$

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?

Examples:
$\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.

$\endgroup$

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.