Համահեղինակ(ներ):

Khachatrian Hrant ; Petrosyan Petros

Ամփոփում:

An interval t-coloring of a multigraph G is a proper edge coloring with colors 1,…,t such that the colors of the edges incident with 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 of the edges incident with 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+[V(G)/2](Δ(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.

Հրատարակիչ:

Springer

Հրատարակման ամսաթիվ:

2018

Նույնականացուցիչ:

oai:noad.sci.am:136098

DOI:

10.1016/j.disc.2017.11.001

ISSN:

0012-365X

Լեզու:

English

Ամսագրի կամ հրապարակման վերնագիր:

Discrete Mathematics

Հատոր:

341

Համար:

3

URL:

սեղմել այստեղ՝ կապին հետևելու համար

Կազմակերպության անվանում:

Linköping University ; Yerevan State University ; Institute for Informatics and Automation Problems of NAS RA

Երկիր:

Armenia ; Sweden

Ինդեքսավորում:

WOS