umu.sePublications
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
Edge precoloring extension of hypercubes
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
(English)In: Article in journal (Refereed) Submitted
Abstract [en]

We consider the problem of extending partial edge colorings of hypercubes. In particular, we obtain an analogue of the positive solution to the famous Evans' conjecture on completing partial Latin squares by proving that every proper partial edge coloring of at most (d-1) edges of the d-dimensional hypercube Qd can be extended to a proper d-edge coloring of  Qd. Additionally, we characterize which partial edge colorings of  Qd with precisely d precolored edges are extendable to proper d-edge colorings of  Qd.

National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-147508OAI: oai:DiVA.org:umu-147508DiVA, id: diva2:1203756
Available from: 2018-05-04 Created: 2018-05-04 Last updated: 2018-06-09
In thesis
1. On avoiding and completing edge colorings
Open this publication in new window or tab >>On avoiding and completing edge colorings
2018 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

These papers are all related to the problem of avoiding and completing an edge precoloring of a graph. In more detail, given a graph G and a partial proper edge precoloring φ of G and a list assignment L for every non-colored edge of G, can we extend the precoloring to a proper edge coloring avoiding any list assignment? In the first paper, G is a d-dimensional hypercube graph Qd, a partial proper edge precoloring φ and every list assignment L must satisfy certain sparsity conditions. The second paper still deals with d-dimensional hypercube graph Qd, but the list assignment L for every edge of Qd is an empty set and φ must be a partial proper edge precoloring of at most (d - 1) edges. For the third paper, G can be seen as a complete 3-uniform 3-partite hypergraph, every list assignment L must satisfy certain sparsity conditions but we do not have a partial proper edge precoloring φ on edges of G. 

Place, publisher, year, edition, pages
Umeå: Umeå University, 2018. p. 8
Series
Research report in mathematics, ISSN 1653-0810
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:umu:diva-146915 (URN)978-91-7601-876-7 (ISBN)
Presentation
2018-05-17, MA346, MIT Building, Umea University, Umea, 13:00 (English)
Opponent
Supervisors
Available from: 2018-05-25 Created: 2018-05-04 Last updated: 2018-06-09Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

URL

Authority records BETA

Markström, KlasPham, Lan Anh

Search in DiVA

By author/editor
Markström, KlasPham, Lan Anh
By organisation
Department of Mathematics and Mathematical Statistics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

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