2016/11/21 by Carl Johan Casselgren, Casselgren, Carl Johan, Hrant H. Khachatrian +3
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1611.07011
18 pages, 2 figures
arxiv created 2016/11/21 · arxiv updated 2016/11/22
An interval t-coloring of a multigraph G is a proper edge coloring with colors 1,…,t such that the colors on the edges incident to every vertex of G are colored by consecutive colors. A cyclic interval t-coloring of a multigraph G is a proper edge coloring with colors 1,…,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) (wc(G)) and W(G) (Wc(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)≤ 1+\lfloor (|V(G)|)/(2)\rfloor(Δ(G)-1). We also give several results towards the general conjecture that Wc(G)≤ |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.