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

Direct link
Cite
Citation style
  • apa
  • 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

fulltext(252 kB)103 downloads
File information
File name FULLTEXT01.pdfFile size 252 kBChecksum SHA-512
5fd10fbfa64d64916ac6c37a72c60ff6a0c2da8a54c954ec4ab787671e7195f94f9f2e0577b7e1e9528f10e00032fb4dbaf70752968f022694661667263a4180
Type fulltextMimetype application/pdf

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
Total: 103 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
urn-nbn

Altmetric score

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

Direct link
Cite
Citation style
  • apa
  • 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