On the palette index of complete bipartite graphs

Mirko Hor\v n\'ak
P.J. \v Saf\'arik University Ko\v sice, Slovakia

Juraj Hud\'ak
P.J. \v Saf\'arik University Ko\v sice, Slovakia

PDF

Minisymposium: VERTEX COLOURINGS AND FORBIDDEN SUBGRAPHS

Content: Let $G$ be a graph, $C$ a set of colours and $\varphi:E(G)\to C$ a proper edge colouring of $G$. The $\varphi$-palette of a vertex $v\in V(G)$ is the set $\{\varphi(vw):vw\in E(G)\}$. The $\varphi$-diversity is the number of distinct $\varphi$-palettes of vertices of $G$ and the palette index of $G$ is the minimum of $\varphi$-diversities over all proper edge colourings $\varphi$ of $G$. We present some results on the palette index of complete bipartite graphs $K_{m,n}$, $m\le n$, namely the exact values for $m\le5$ as well as several upper bounds for general $m$. Moreover, we formulate three conjectures based on the proved statements.

Back to all abstracts