Umeå universitets logga

umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Avoiding and Extending Partial Edge Colorings of Hypercubes
Department of Mathematics, Linköping University, Linköping, Sweden.
Department of Mathematics, Linköping University, Linköping, Sweden.
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
2022 (Engelska)Ingår i: Graphs and Combinatorics, ISSN 0911-0119, E-ISSN 1435-5914, Vol. 38, nr 3, artikel-id 79Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We consider the problem of extending and avoiding partial edge colorings of hypercubes; that is, given a partial edge coloring φ of the d-dimensional hypercube Qd, we are interested in whether there is a proper d-edge coloring of Qd that agrees with the coloring φ on every edge that is colored under φ; or, similarly, if there is a proper d-edge coloring that disagrees with φ on every edge that is colored under φ. In particular, we prove that for any d≥ 1 , if φ is a partial d-edge coloring of Qd, then φ is avoidable if every color appears on at most d/8 edges and the coloring satisfies a relatively mild structural condition, or φ is proper and every color appears on at most d- 2 edges. We also show that φ is avoidable if d is divisible by 3 and every color class of φ is an induced matching. Moreover, for all 1 ≤ k≤ d, we characterize for which configurations consisting of a partial coloring φ of d- k edges and a partial coloring ψ of k edges, there is an extension of φ that avoids ψ.

Ort, förlag, år, upplaga, sidor
Springer, 2022. Vol. 38, nr 3, artikel-id 79
Nyckelord [en]
Avoiding edge coloring, Edge coloring, Hypercube, Precoloring extension
Nationell ämneskategori
Diskret matematik
Identifikatorer
URN: urn:nbn:se:umu:diva-193790DOI: 10.1007/s00373-022-02485-zISI: 000777995400001Scopus ID: 2-s2.0-85127515233OAI: oai:DiVA.org:umu-193790DiVA, id: diva2:1656640
Forskningsfinansiär
Vetenskapsrådet, 2017-05077Tillgänglig från: 2022-05-06 Skapad: 2022-05-06 Senast uppdaterad: 2023-03-23Bibliografiskt granskad

Open Access i DiVA

fulltext(329 kB)232 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 329 kBChecksumma SHA-512
447674445da5e3c8f1a1e115804c1bf375d846b58e12fc27e97dbdef576e0205285655395d95880e6ae1026e82871d486c0962ea76802cf3a326f67146bebbaf
Typ fulltextMimetyp application/pdf

Övriga länkar

Förlagets fulltextScopus

Person

Markström, Klas

Sök vidare i DiVA

Av författaren/redaktören
Markström, Klas
Av organisationen
Institutionen för matematik och matematisk statistik
I samma tidskrift
Graphs and Combinatorics
Diskret matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 232 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 265 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf