Abstract
An \emph{interval -coloring} of a multigraph is a proper edge coloring with colors such that the colors on the edges incident to every vertex of are colored by consecutive colors. A \emph{cyclic interval -coloring} of a multigraph is a proper edge coloring with colors such that the colors on the edges incident to every vertex of are colored by consecutive colors, under the condition that color is considered as consecutive to color . Denote by () and () the minimum and maximum number of colors in a (cyclic) interval coloring of a multigraph , respectively. We present some new sharp bounds on and for multigraphs satisfying various conditions. In particular, we show that if is a -connected multigraph with an interval coloring, then . We also give several results towards the general conjecture that for any triangle-free graph 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 .
Connections
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 review
No reviews yet.
Discussion 0
Add a comment
No comments yet.