| 1. |
- Andrén, Lina J., 1980-, et al.
(författare)
-
Avoiding arrays of odd order by Latin squares
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- We prove that there exists a constant c such that for each pos- itive integer k every (2k+1)×(2k+1) array A on the symbols 1,...,2k+1 with at most c(2k + 1) symbols in every cell, and each symbol repeated at most c(2k+1) times in every row and column is avoidable; that is, there is a (2k+1)×(2k+1) Latin square S on the symbols 1,...,2k+1 such that for each cell (i, j) in S the symbol in (i, j) does not appear in the corresponding cell in A. This settles the last open case of a conjecture by Häggkvist.
|
|
| 2. |
- Asratian, Armen, et al.
(författare)
-
On interval edge colorings of (a, ß)-biregular bipartite graphs
- 2007
-
Ingår i: Discrete Mathematics. - : Elsevier BV. - 0012-365X .- 1872-681X. ; 307:15, s. 1951-1956
-
Tidskriftsartikel (refereegranskat)abstract
- A bipartite graph G is called (a, ß)-biregular if all vertices in one part of G have degree a and all vertices in the other part have degree ß. An edge coloring of a graph G with colors 1, 2, 3, ..., t is called an interval t-coloring if the colors received by the edges incident with each vertex of G are distinct and form an interval of integers and at least one edge of G is colored i, for i = 1, ..., t. We show that the problem to determine whether an (a, ß)-biregular bipartite graph G has an interval t-coloring is NP-complete in the case when a = 6, ß = 3 and t = 6. It is known that if an (a, ß)-biregular bipartite graph G on m vertices has an interval t-coloring then a + ß - gcd (a, ß) = t = m - 1, where gcd (a, ß) is the greatest common divisor of a and ß. We prove that if an (a, ß)-biregular bipartite graph has m = 2 (a + ß) vertices then the upper bound can be improved to m - 3. © 2006 Elsevier B.V. All rights reserved.
|
|
| 3. |
- Asratian, Armen, et al.
(författare)
-
On Path Factors of (3,4)-Biregular Bigraphs
- 2008
-
Ingår i: Graphs and Combinatorics. - : Springer Science and Business Media LLC. - 0911-0119 .- 1435-5914. ; 24:5, s. 405-411
-
Tidskriftsartikel (refereegranskat)abstract
- A (3, 4)-biregular bigraph G is a bipartite graph where all vertices in one part have degree 3 and all vertices in the other part have degree 4. A path factor of G is a spanning subgraph whose components are nontrivial paths. We prove that a simple (3,4)-biregular bigraph always has a path factor such that the endpoints of each path have degree three. Moreover we suggest a polynomial algorithm for the construction of such a path factor.
|
|
| 4. |
- Asratian, Armen, et al.
(författare)
-
Proper path-factors and interval edge-coloring of (3,4)-biregular bigraphs
- 2009
-
Ingår i: Journal of Graph Theory. - : Wiley Periodicals Inc.. - 0364-9024 .- 1097-0118. ; 61:2, s. 88-97
-
Tidskriftsartikel (refereegranskat)abstract
- An interval coloring of a graph G is a proper coloring of E(G) by positive integers such that the colors on the edges incident to any vertex are consecutive. A (3,4)-biregular bigraph is a bipartite graph in which each vertex of one part has degree 3 and each vertex of the other has degree 4; it is unknown whether these all have interval colorings. We prove that G has an interval coloring using 6 colors when G is a (3,4)-biregular bigraph having a spanning subgraph whose components are paths with endpoints at 3-valent vertices and lengths in {2, 4, 6, 8}. We provide several sufficient conditions for the existence of such a subgraph.
|
|
| 5. |
- Casselgren, Carl Johan, 1982-, et al.
(författare)
-
A note on adaptable choosability and choosability with separation of planar graphs
- 2021
-
Ingår i: Journal of Combinatorial Mathematics and Combinatorial Computing. - : Charles Babbage Research Centre. - 0835-3026. ; 116, s. 101-109
-
Tidskriftsartikel (refereegranskat)abstract
- Let F be a (possibly improper) edge-coloring of a graph G; a vertex coloring of G is adapted to F if no color appears at the same time on an edge and on its two endpoints. If for some integer k, a graph G is such that given any list assignment L to the vertices of G, with |L(v)| ≥ k for all v, and any edge-coloring F of G, G admits a coloring c adapted to F where c(v) ∈ L(v) for all v, then G is said to be adaptably k-choosable. A (k, d)-list assignment for a graph G is a map that assigns to each vertex v a list L(v) of at least k colors such that |L(x) ∩ L(y)\ ≤ d whenever x and y are adjacent. A graph is (k, d)-choosable if for every (k, d)-list assignment L there is an L-coloring of G. It has been conjectured that planar graphs are (3, l)-choosable. We give some progress on this conjecture by giving sufficient conditions for a planar graph to be adaptably 3-choosable. Since (k, l)-choosability is a special case of adaptable k-choosablity, this implies that a planar graph satisfying these conditions is (3,1)-choosable.
|
|
| 6. |
|
|
| 7. |
|
|
| 8. |
|
|
| 9. |
- Casselgren, Carl Johan, 1982-, et al.
(författare)
-
Completing partial Latin squares with two filled rows and three filled columns
- 2023
-
Ingår i: Journal of Combinatorics. - : INT PRESS BOSTON, INC. - 2156-3527 .- 2150-959X. ; 14:1, s. 139-153
-
Tidskriftsartikel (refereegranskat)abstract
- Consider a partial Latin square P where the first two rows and first three columns are completely filled, and every other cell of P is empty. It has been conjectured that all such partial Latin squares of order at least 8 are completable. Based on a technique by Kuhl and McGinn we describe a framework for completing partial Latin squares in this class. Moreover, we use our method for proving that all partial Latin squares from this family, where the intersection of the nonempty rows and columns form a Latin rectangle with three distinct symbols, are completable.
|
|
| 10. |
- 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.
|
|
