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

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • 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
Edge precoloring extension of hypercubes
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
(Engelska)Manuskript (preprint) (Övrigt vetenskapligt)
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.

Nationell ämneskategori
Diskret matematik
Forskningsämne
matematik
Identifikatorer
URN: urn:nbn:se:umu:diva-147508OAI: oai:DiVA.org:umu-147508DiVA, id: diva2:1203756
Tillgänglig från: 2018-05-04 Skapad: 2018-05-04 Senast uppdaterad: 2019-04-29
Ingår i avhandling
1. On avoiding and completing edge colorings
Öppna denna publikation i ny flik eller fönster >>On avoiding and completing edge colorings
2018 (Engelska)Licentiatavhandling, sammanläggning (Övrigt vetenskapligt)
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. 

Ort, förlag, år, upplaga, sidor
Umeå: Umeå University, 2018. s. 8
Serie
Research report in mathematics, ISSN 1653-0810
Nationell ämneskategori
Diskret matematik
Forskningsämne
matematik
Identifikatorer
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 (Engelska)
Opponent
Handledare
Tillgänglig från: 2018-05-25 Skapad: 2018-05-04 Senast uppdaterad: 2018-06-09Bibliografiskt granskad
2. On avoiding and completing colorings
Öppna denna publikation i ny flik eller fönster >>On avoiding and completing colorings
2019 (Engelska)Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
Abstract [en]

All of my papers are 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 φ to a proper edge coloring of G which avoids L? 

In Paper I, G is the d-dimensional hypercube graph Qd, a partial proper edge precoloring φ and a list assignment L must satisfy certain sparsity conditions. Paper II still deals with the 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. In Paper III, G is a (d,s)-edge colorable graph; that is G has a proper d-edge coloring, where every edge is contained in at least s-1 2-colored 4-cycles, L must satisfy certain sparsity conditions and we do not have a partial proper edge precoloring φ on edges of G. The problem in Paper III is also considered in Paper IV and Paper V, but here G can be seen as the complete 3-uniform 3-partite hypergraph K3n,n,n, where n is a power of two in paper IV and n is an even number in paper V.

Ort, förlag, år, upplaga, sidor
Umeå: Umeå University, 2019. s. 11
Serie
Research report in mathematics, ISSN 1653-0810 ; 66/19
Nyckelord
Graph coloring, precoloring, list assignment
Nationell ämneskategori
Diskret matematik
Identifikatorer
urn:nbn:se:umu:diva-158343 (URN)978-91-7855-055-5 (ISBN)
Disputation
2019-05-24, MA121, MIT-huset, Umeå, 10:15 (Engelska)
Opponent
Handledare
Tillgänglig från: 2019-05-03 Skapad: 2019-04-24 Senast uppdaterad: 2019-04-29Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

URL

Personposter BETA

Markström, KlasPham, Lan Anh

Sök vidare i DiVA

Av författaren/redaktören
Markström, KlasPham, Lan Anh
Av organisationen
Institutionen för matematik och matematisk statistik
Diskret matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar

urn-nbn

Altmetricpoäng

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

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • 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