| 1. |
- Casselgren, Carl Johan, et al.
(författare)
-
Edge precoloring extension of hypercubes
- 2020
-
Ingår i: Journal of Graph Theory. - : John Wiley & Sons. - 0364-9024 .- 1097-0118. ; 95:3, s. 410-444
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 2. |
- Casselgren, Carl Johan, et al.
(författare)
-
Latin cubes with forbidden entries
- 2019
-
Ingår i: The Electronic Journal of Combinatorics. - Newark : Department of Mathematical Science, University of Delaware. - 1097-1440 .- 1077-8926. ; 26:1
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 3. |
- Casselgren, Carl Johan, et al.
(författare)
-
Restricted extension of sparse partial edge colorings of hypercubes
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- 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.
|
|
| 4. |
- Pham, Lan Anh
(författare)
-
On avoiding and completing edge colorings
- 2018
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- 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.
|
|
| 5. |
- Casselgren, Carl Johan, et al.
(författare)
-
Latin cubes of even order with forbidden entries
- 2020
-
Ingår i: European journal of combinatorics (Print). - : ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD. - 0195-6698 .- 1095-9971. ; 85
-
Tidskriftsartikel (refereegranskat)abstract
- 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 gamma amp;gt; 0 such that if n is even and A is a 3-dimensional n x n x n array where every cell contains at most gamma n symbols, and every symbol occurs at most gamma 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 i, j, k is an element of {1, ..., n}, the symbol in position (i, j, k) of L does not appear in the corresponding cell of A. (C) 2019 Elsevier Ltd. All rights reserved.
|
|
| 6. |
- Casselgren, Carl Johan, 1982-, et al.
(författare)
-
Latin cubes of even order with forbidden entries
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- 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.
|
|
| 7. |
- Casselgren, Carl Johan, 1982-, et al.
(författare)
-
Latin cubes with forbidden entries
- 2019
-
Ingår i: The Electronic Journal of Combinatorics. - Clemson, SC, United States : Electronic Journal of Combinatorics. - 1097-1440 .- 1077-8926. ; 26:1
-
Tidskriftsartikel (refereegranskat)abstract
- 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 gamma amp;gt; 0 such that if n = 2(t) and A is a 3-dimensional n x n x n array where every cell contains at most gamma n symbols, and every symbol occurs at most gamma 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 amp;lt;= i, j, k amp;lt;= n, the symbol in position (i, j, k) of L does not appear in the corresponding cell of A.
|
|
| 8. |
- Casselgren, Carl Johan, et al.
(författare)
-
Restricted extension of sparse partial edge colorings of complete graphs
- 2021
-
Ingår i: The Electronic Journal of Combinatorics. - Boston : International Press. - 1097-1440 .- 1077-8926. ; 28:2
-
Tidskriftsartikel (refereegranskat)abstract
- Given a partial edge coloring of a complete graph K-n and lists of allowed colors for the non-colored edges of K-n, can we extend the partial edge coloring to a proper edge coloring of K-n using only colors from the lists? We prove that this question has a positive answer in the case when both the partial edge coloring and the color lists satisfy certain sparsity conditions.
|
|
| 9. |
- Casselgren, Carl Johan, et al.
(författare)
-
Restricted extension of sparse partial edge colorings of hypercubes
- 2020
-
Ingår i: Discrete Mathematics. - : ELSEVIER. - 0012-365X .- 1872-681X. ; 343:11
-
Tidskriftsartikel (refereegranskat)abstract
- 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. (C) 2020 Elsevier B.V. All rights reserved.
|
|
| 10. |
- Pham, Lan Anh, 1991-
(författare)
-
On avoiding and completing colorings
- 2019
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- 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.
|
|
