Some bounds on the number of colors in interval and cyclic interval edge colorings of graphs |
| |
Authors: | Carl Johan Casselgren Hrant H Khachatrian Petros A Petrosyan |
| |
Institution: | 1. Department of Mathematics, Linköping University, SE-581 83 Linköping, Sweden;2. Department of Informatics and Applied Mathematics, Yerevan State University, 0025, Armenia |
| |
Abstract: | An interval-coloring of a multigraph is a proper edge coloring with colors such that the colors of the edges incident with every vertex of are colored by consecutive colors. A cyclic interval-coloring of a multigraph is a proper edge coloring with colors such that the colors of the edges incident with 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 . |
| |
Keywords: | Interval edge coloring Cyclic interval edge coloring Edge coloring |
本文献已被 ScienceDirect 等数据库收录! |
|