liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Some bounds on the number of colors in interval and cyclic interval edge colorings of graphs
Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, Faculty of Science & Engineering.
Yerevan State Univ, Armenia.
Yerevan State Univ, Armenia.
2018 (English)In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 341, no 3, p. 627-637Article in journal (Refereed) Published
Abstract [en]

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) (w(c)(G)) and W(G) (W-c(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) amp;lt;= 1 + left perpendicular vertical bar V(G)vertical bar/2 right perpendicular (Delta(G) - 1). We also give several results towards the general conjecture that W-c(G) amp;lt;= I vertical bar V(G)vertical bar 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. (C) 2017 Elsevier B.V. All rights reserved.

Place, publisher, year, edition, pages
ELSEVIER SCIENCE BV , 2018. Vol. 341, no 3, p. 627-637
Keywords [en]
Interval edge coloring; Cyclic interval edge coloring; Edge coloring
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-145231DOI: 10.1016/j.disc.2017.11.001ISI: 000424171200005OAI: oai:DiVA.org:liu-145231DiVA, id: diva2:1188352
Available from: 2018-03-07 Created: 2018-03-07 Last updated: 2018-03-23

Open Access in DiVA

The full text will be freely available from 2019-11-27 16:26
Available from 2019-11-27 16:26

Other links

Publisher's full text

Search in DiVA

By author/editor
Casselgren, Carl Johan
By organisation
Mathematics and Applied MathematicsFaculty of Science & Engineering
In the same journal
Discrete Mathematics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 70 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf