Some bounds on the number of colors in interval and cyclic interval edge colorings of graphs

Abstract

An \emph{interval $t$-coloring} of a multigraph $G$ is a proper edge coloring with colors $1,\dots ,t$ such that the colors on the edges incident to every vertex of $G$ are colored by consecutive colors. A \emph{cyclic interval $t$-coloring} of a multigraph $G$ is a proper edge coloring with colors $1,\dots ,t$ such that the colors on the edges incident to every vertex of $G$ are colored by consecutive colors, under the condition that color $1$ is considered as consecutive to color $t$. Denote by $w(G)$ ($w_c(G)$) and $W(G)$ ($W_c(G)$) the minimum and maximum number of colors in a (cyclic) interval coloring of a multigraph $G$, respectively. We present some new sharp bounds on $w(G)$ and $W(G)$ for multigraphs $G$ satisfying various conditions. In particular, we show that if $G$ is a $2$-connected multigraph with an interval coloring, then $W(G)\le 1+\lfloor \frac{|V(G)|}{2}\rfloor (\Delta (G)-1)$. We also give several results towards the general conjecture that $W_c(G)\le |V(G)|$ for any triangle-free graph $G$ with a cyclic interval coloring; we establish that approximate versions of this conjecture hold for several families of graphs, and we prove that the conjecture is true for graphs with maximum degree at most $4$.

18 pages, 2 figures