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
Cyclic deficiency of graphs
Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, Faculty of Science & Engineering.
Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, Faculty of Science & Engineering.
Yerevan State Univ, Armenia; Natl Acad Sci, Armenia.
2019 (English)In: Discrete Applied Mathematics, ISSN 0166-218X, E-ISSN 1872-6771, Vol. 266, p. 171-185Article in journal (Refereed) Published
Abstract [en]

A proper edge coloring of a graph G with colors 1, 2, . . . , t is called a cyclic interval t-coloring if for each vertex v of G the edges incident to v are colored by consecutive colors, under the condition that color 1 is considered as consecutive to color t. In this paper we introduce and investigate a new notion, the cyclic deficiency of a graph G, defined as the minimum number of pendant edges whose attachment to G yields a graph admitting a cyclic interval coloring; this number can be considered as a measure of closeness of G of being cyclically interval colorable. We determine or bound the cyclic deficiency of several families of graphs. In particular, we present examples of graphs of bounded maximum degree with arbitrarily large cyclic deficiency, and graphs whose cyclic deficiency approaches the number of vertices. Finally, we conjecture that the cyclic deficiency of any graph does not exceed the number of vertices, and we present several results supporting this conjecture. (C) 2018 Elsevier B.V. All rights reserved.

Place, publisher, year, edition, pages
ELSEVIER , 2019. Vol. 266, p. 171-185
Keywords [en]
Edge coloring; Interval edge coloring; Cyclic interval edge coloring; Deficiency; Cyclic deficiency
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-160431DOI: 10.1016/j.dam.2018.12.003ISI: 000483450700019OAI: oai:DiVA.org:liu-160431DiVA, id: diva2:1353459
Available from: 2019-09-23 Created: 2019-09-23 Last updated: 2019-09-23

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 10 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