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 Q_{d} can be extended to a proper d-edge coloring of Q_{d}. Additionally, we characterize which partial edge colorings of Q_{d} with precisely d precolored edges are extendable to proper d-edge colorings of Q_{d}.

2. Casselgren, Carl Johan

et al.

Markström, Klas

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.

Pham, Lan Anh

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.

Latin cubes with forbidden entries2019In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 26, no 1, article id P1.2Article in journal (Refereed)

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=2^{k} 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.

We consider the following type of question: Given a partial proper d-edge coloring of the d-dimensional hypercube Q_{d}, and lists of allowed colors for the non-colored edges of Q_{d}, 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. Casselgren, Carl Johan

et al.

Pham, Lan Anh

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.

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.

5.

Pham, Lan Anh

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.

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 Q_{d}, a partial proper edge precoloring φ and a list assignment L must satisfy certain sparsity conditions. Paper II still deals with the hypercube graph Q_{d}, but the list assignment L for every edge of Q_{d} 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 K^{3}_{n,n,n}, where n is a power of two in paper IV and n is an even number in paper V.

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 Q_{d}, 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 Q_{d}, but the list assignment L for every edge of Q_{d} 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.

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.

8. Trotignon, Nicolas

et al.

Pham, Lan Anh

Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.

chi-bounds, operations, and chords2018In: Journal of Graph Theory, ISSN 0364-9024, E-ISSN 1097-0118, Vol. 88, no 2, p. 312-336Article in journal (Refereed)

Abstract [en]

A long unichord in a graph is an edge that is the unique chord of some cycle of length at least 5. A graph is long unichord free if it does not contain any long unichord. We prove a structure theorem for long unichord free graph. We give an O(n4m) time algorithm to recognize them. We show that any long unichord free graph G can be colored with at most O(3) colors, where is the maximum number of pairwise adjacent vertices in G.