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

preprint2016arXivOpen access

Abstract

An \emph{interval tt-coloring} of a multigraph GG is a proper edge coloring with colors 1,…,t1,\dots,t such that the colors on the edges incident to every vertex of GG are colored by consecutive colors. A \emph{cyclic interval tt-coloring} of a multigraph GG is a proper edge coloring with colors 1,…,t1,\dots,t such that the colors on the edges incident to every vertex of GG are colored by consecutive colors, under the condition that color 11 is considered as consecutive to color tt. Denote by w(G)w(G) (wc(G)w_{c}(G)) and W(G)W(G) (Wc(G)W_{c}(G)) the minimum and maximum number of colors in a (cyclic) interval coloring of a multigraph GG, respectively. We present some new sharp bounds on w(G)w(G) and W(G)W(G) for multigraphs GG satisfying various conditions. In particular, we show that if GG is a 22-connected multigraph with an interval coloring, then W(G)≤1+⌊∣V(G)∣2⌋(Δ(G)−1)W(G)\leq 1+\left\lfloor \frac{|V(G)|}{2}\right\rfloor(Δ(G)-1). We also give several results towards the general conjecture that Wc(G)≤∣V(G)∣W_{c}(G)\leq |V(G)| for any triangle-free graph GG 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 44.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.