Object

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

Co-author(s) :

Khachatrian Hrant ; Petrosyan Petros

Abstract:

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.

Publisher:

Springer

Date of publication:

2018

Identifier:

oai:noad.sci.am:136098

DOI:

10.1016/j.disc.2017.11.001

ISSN:

0012-365X

Language:

English

Journal or Publication Title:

Discrete Mathematics

Volume:

341

Number:

3

URL:

click here to follow the link

Affiliation:

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

Country:

Armenia ; Sweden

Indexing:

WOS

Object collections:

Last modified:

May 3, 2021

In our library since:

Apr 19, 2021

Number of object content hits:

18

All available object's versions:

https://noad.sci.am/publication/149545

Show description in RDF format:

RDF

Show description in OAI-PMH format:

OAI-PMH

Objects

Similar

This page uses 'cookies'. More information