Ljubljana - Leoben Graph Theory Seminar 2014

Palette index of 4-regular graphs

Not scheduled

Velika predavalnica (UP FAMNIT, Koper, Slovenia)

Speaker

Dr Simona Bonvicini (University of Modena and Reggio Emilia)

Description

A proper edge-coloring of a graph $G$ is an assignment of colors to the edges of $G$ such that adjacent edges receive distinct colors. A proper edge-coloring defines at each vertex the set of colors of its incident edges. Following the terminology introduced by Hor\v{n}\'ak, Kalinowski, Meszka and Wo\'zniak, we call such a set of colors the palette of the vertex. The minimum number of distinct palettes taken over all proper edge-colorings of $G$ is called the palette index of $G$ and is denoted by $\check s(G)$ (see \cite{HoKaMe}). In \cite{HoKaMe} the authors determine the palette index of cubic graphs and complete graphs; they also note that the palette index of a $d$-regular graph is $1$ if and only if the graph is class $1$; moreover, $\check s(G)\neq 2$ for every class $2$ $d$-regular graph $G$. By Vizing's Theorem and the results in \cite{HoKaMe}, one can see that the palette index of a class $2$ $d$-regular graph satisfies the inequalities $3\leq\check s(G)\leq d+1$. We wonder whether the upper bound for the palette index of a class $2$ $d$-regular graph is really achieved, that is, we wonder whether for any fixed $d\geq 2$ there exists a class $2$ $d$-regular graph with palette index $d+1$. For $d=2$ and $d=3$ there exist $d$-regular graphs with palette index $d+1$: for $d=2$, we can take a $2$-regular graph with at least one circuit of odd length; for $d=3$, we can take a cubic graph with no perfect matching (see \cite{HoKaMe}). We consider the case $d=4$: we can construct $4$-regular graphs with palette index $5$. We also study in more detail the palette index of $4$-regular graphs. In particular, we show that a $4$-regular graph with no perfect matching and palette index $3$ has an even cycle decomposition of size $3$. An even cycle decomposition of a graph $G$ is a partition $\mathcal E$ of the edge-set of $G$ into $2$-regular subgraphs (cycles) whose connected components are circuits of even length. If $\mathcal E$ consists of $m$ cycles, then we say that $G$ has an even cycle decomposition of size $m$. We can extend the result to $4r$-regular graphs: we can prove that a $4r$-regular graph with no perfect matching and palette index $3$ has an even cycle decomposition of size $3r$. \begin{thebibliography}{99} \bibitem{HoKaMe} M. Hor$\check{\mbox{n}}$\'ak, R. Kalinowski, M. Meszka, M. M. Wo\'zniak, Minimum number of palettes in edge colorings, Graphs Combin., DOI 10.007/s00373-013-1298-8. \end{thebibliography}