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
On avoiding and completing colorings
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
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 [en]
Graph coloring, precoloring, list assignment
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-158343ISBN: 978-91-7855-055-5 (print)OAI: oai:DiVA.org:umu-158343DiVA, id: diva2:1306676
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
List of papers
1. Restricted extension of sparse partial edge colorings of hypercubes
Open this publication in new window or tab >>Restricted extension of sparse partial edge colorings of hypercubes
(English)Manuscript (preprint) (Other academic)
Abstract [en]

We consider the following type of question: Given a partial proper d-edge coloring of the d-dimensional hypercube Qd, and lists of allowed colors for the non-colored edges of Qd, can we extend the partial coloring to a proper d-edge coloring using only colors from the lists? We prove that this question has a positive answer in the case when both the partial coloring and the color lists satisfy certain sparsity conditions.

National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:umu:diva-146922 (URN)
Available from: 2018-05-04 Created: 2018-05-04 Last updated: 2019-04-29
2. Edge precoloring extension of hypercubes
Open this publication in new window or tab >>Edge precoloring extension of hypercubes
(English)Manuscript (preprint) (Other academic)
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:nbn:se:umu:diva-147508 (URN)
Available from: 2018-05-04 Created: 2018-05-04 Last updated: 2019-04-29
3. On restricted colorings of (d,s)-edge colorable graphs
Open this publication in new window or tab >>On restricted colorings of (d,s)-edge colorable graphs
(English)Manuscript (preprint) (Other academic)
Abstract [en]

A cycle is 2-colored if its edges are properly colored by two distinct colors. A (d,s)-edge colorable graph G is a d-regular graph that admits a proper d-edge coloring in which every edge of G is in at least s−1 2-colored 4-cycles. Given a (d,s)-edge colorable graph G and a list assigment L of forbidden colors for the edges of G satisfying certain sparsity conditions, we prove that there is a proper d-edge coloring of Gthat avoids L, that is, a proper edge coloring φ of G such that φ(e)∉L(e) for every edge e of G.

Keywords
list assigment, restricted colorings
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-158320 (URN)
Available from: 2019-04-23 Created: 2019-04-23 Last updated: 2019-04-29
4. Latin cubes with forbidden entries
Open this publication in new window or tab >>Latin cubes with forbidden entries
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
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:umu:diva-147511 (URN)000456790800002 ()
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
5. Latin cubes of even order with forbidden entries
Open this publication in new window or tab >>Latin cubes of even order with forbidden entries
(English)Manuscript (preprint) (Other academic)
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 γ>0 such that if n=2t 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.

Keywords
Latin cubes, forbidden entries
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-158322 (URN)
Available from: 2019-04-23 Created: 2019-04-23 Last updated: 2019-04-29

Open Access in DiVA

fulltext(253 kB)14 downloads
File information
File name FULLTEXT01.pdfFile size 253 kBChecksum SHA-512
8ca5c7b79301e6ab87330f0c19b282d52ceceda19be8f9ebfd3502781cb705da8d5b2a016c3a420cea1fbb1fb8abe3c3f66421550f7eda76151b1e986e8e3fb3
Type fulltextMimetype application/pdf
spikblad(180 kB)6 downloads
File information
File name SPIKBLAD01.pdfFile size 180 kBChecksum SHA-512
ce1f4a0d937700b44ea40fcd721916b681c0a40c1abcee662c80d63f30cd6dbd7c6f717d5ba7690e74566d8b8a9d6d900fde45dd02d470ac1c86f0476cf698d3
Type spikbladMimetype application/pdf

Authority records BETA

Pham, Lan Anh

Search in DiVA

By author/editor
Pham, Lan Anh
By organisation
Department of Mathematics and Mathematical Statistics
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

isbn
urn-nbn

Altmetric score

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