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
Latin cubes with forbidden entries
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.
2019 (English)In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 26, no 1, article id P1.2Article in journal (Refereed) Published
Abstract [en]

We consider the problem of constructing Latin cubes subject to the condition that some symbols may not appear in certain cells. We prove that there is a constant y>0 such that if n=2k and A is a 3-dimensional n×n×n array where every cell contains at most γn symbols, and every symbol occurs at most γn times in every line of A, then A is avoidable; that is, there is a Latin cube L of order n such that for every 1 ≤ i,j,k ≤ n, the symbol in position (i,j,k) of L does not appear in the corresponding cell of A. 

Place, publisher, year, edition, pages
Newark: Department of Mathematical Science, University of Delaware , 2019. Vol. 26, no 1, article id P1.2
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-147511ISI: 000456790800002OAI: oai:DiVA.org:umu-147511DiVA, id: diva2:1203765
Funder
Swedish Research Council, 2014-4897
Note

Originally included in thesis in manuscript form.

Available from: 2018-05-04 Created: 2018-05-04 Last updated: 2019-04-24Bibliographically approved
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
2. On avoiding and completing colorings
Open this publication in new window or tab >>On avoiding and completing colorings
2019 (English)Doctoral thesis, comprehensive summary (Other academic)
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.

Place, publisher, year, edition, pages
Umeå: Umeå University, 2019. p. 11
Series
Research report in mathematics, ISSN 1653-0810 ; 66/19
Keywords
Graph coloring, precoloring, list assignment
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-158343 (URN)978-91-7855-055-5 (ISBN)
Public defence
2019-05-24, MA121, MIT-huset, Umeå, 10:15 (English)
Opponent
Supervisors
Available from: 2019-05-03 Created: 2019-04-24 Last updated: 2019-04-29Bibliographically approved

Open Access in DiVA

fulltext(716 kB)14 downloads
File information
File name FULLTEXT01.pdfFile size 716 kBChecksum SHA-512
883356d6a6e60bee4a3570f239ea7bc4b58c6d682d2d91a0a37b7f95741b0b2f60e125f84f08e1da8096704c0b2bd0dc85898651ec73faf0a506c16b25f32865
Type fulltextMimetype application/pdf

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
In the same journal
The Electronic Journal of Combinatorics
Discrete Mathematics

Search outside of DiVA

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