Digitala Vetenskapliga Arkivet

Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • 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 results on the palette index of graphs
Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, Faculty of Science & Engineering.
Yerevan State Univ, Armenia.
2019 (English)In: Discrete Mathematics & Theoretical Computer Science, ISSN 1462-7264, E-ISSN 1365-8050, Vol. 21, no 3, article id UNSP 11Article in journal (Refereed) Published
Abstract [en]

Given a proper edge coloring phi of a graph G, we define the palette S-G (v, phi) of a vertex v is an element of V(G) as the set of all colors appearing on edges incident with v. The palette index s(G) of G is the minimum number of distinct palettes occurring in a proper edge coloring of G. In this paper we give various upper and lower bounds on the palette index of G in terms of the vertex degrees of G, particularly for the case when G is a bipartite graph with small vertex degrees. Some of our results concern (a, b)-biregular graphs; that is, bipartite graphs where all vertices in one part have degree a and all vertices in the other part have degree b. We conjecture that if G is (a, b)-biregular, then. s(G) amp;lt;= 1 + max {a, b}, and we prove that this conjecture holds for several families of (a, b)-biregular graphs. Additionally, we characterize the graphs whose palette index equals the number of vertices.

Place, publisher, year, edition, pages
London, United Kingdom: Chapman & Hall Ltd. , 2019. Vol. 21, no 3, article id UNSP 11
Keywords [en]
edge coloring; palette index; cyclic interval edge coloring
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:liu:diva-160070ISI: 000480436900013OAI: oai:DiVA.org:liu-160070DiVA, id: diva2:1348150
Note

Funding Agencies|Swedish Research Council [2017-05077]

Available from: 2019-09-03 Created: 2019-09-03 Last updated: 2023-08-18Bibliographically approved

Open Access in DiVA

fulltext(222 kB)79 downloads
File information
File name FULLTEXT01.pdfFile size 222 kBChecksum SHA-512
7d65b0902e96a98f3038fa08d3c94ebbe92e938e2b4c47da5008f0d62c79cd57d511c966236e91e9079b11a959987dfd6abc7567099713e845c859044796df8d
Type fulltextMimetype application/pdf

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar
Total: 79 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

urn-nbn

Altmetric score

urn-nbn
Total: 96 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • 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