| 1. |
- Andrén, Lina, et al.
(författare)
-
Restricted completion of sparse partial Latin squares
- 2019
-
Ingår i: Combinatorics, probability & computing. - : Cambridge University Press. - 0963-5483 .- 1469-2163. ; 28:5, s. 675-695
-
Tidskriftsartikel (refereegranskat)abstract
- An n × n partial Latin square P is called α-dense if each row and column has at most αn non-empty cells and each symbol occurs at most αn times in P. An n × n array A where each cell contains a subset of {1,.., n} is a (βn, βn, βn)-array if each symbol occurs at most βn times in each row and column and each cell contains a set of size at most βn. Combining the notions of completing partial Latin squares and avoiding arrays, we prove that there are constants α, β > 0 such that, for every positive integer n, if P is an α-dense n × n partial Latin square, A is an n × n (βn, βn, βn)-array, and no cell of P contains a symbol that appears in the corresponding cell of A, then there is a completion of P that avoids A; that is, there is a Latin square L that agrees with P on every non-empty cell of P, and, for each i, j satisfying 1 ≤ i, j ≤ n, the symbol in position (i, j) in L does not appear in the corresponding cell of A.
|
|
| 2. |
- 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.
|
|
| 3. |
- 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.
|
|
| 4. |
- Andren, Lina J., et al.
(författare)
-
Avoiding Arrays of Odd Order by Latin Squares
- 2013
-
Ingår i: Combinatorics, probability & computing. - : Cambridge University Press (CUP). - 0963-5483 .- 1469-2163. ; 22:2, s. 184-212
-
Tidskriftsartikel (refereegranskat)abstract
- We prove that there is a constant c such that, for each positive integer k, every (2k + 1) x (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) x (2k + 1) Latin square S on the symbols 1, ... , 2k + 1 such that, for each i, j is an element of {1, ... , 2k + 1}, the symbol in position (i, j) of S does not appear in the corresponding cell in Lambda. This settles the last open case of a conjecture by Haggkvist. Using this result, we also show that there is a constant rho, such that, for any positive integer n, if each cell in an n x n array B is assigned a set of m andlt;= rho n symbols, where each set is chosen independently and uniformly at random from {1, ... , n}, then the probability that B is avoidable tends to 1 as n -andgt; infinity.
|
|
| 5. |
- 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.
|
|
| 6. |
- Asratian, Armen, et al.
(författare)
-
Cyclic deficiency of graphs
- 2019
-
Ingår i: Discrete Applied Mathematics. - : ELSEVIER. - 0166-218X .- 1872-6771. ; 266, s. 171-185
-
Tidskriftsartikel (refereegranskat)abstract
- A proper edge coloring of a graph G with colors 1, 2, . . . , t is called a cyclic interval t-coloring if for each vertex v of G the edges incident to v are colored by consecutive colors, under the condition that color 1 is considered as consecutive to color t. In this paper we introduce and investigate a new notion, the cyclic deficiency of a graph G, defined as the minimum number of pendant edges whose attachment to G yields a graph admitting a cyclic interval coloring; this number can be considered as a measure of closeness of G of being cyclically interval colorable. We determine or bound the cyclic deficiency of several families of graphs. In particular, we present examples of graphs of bounded maximum degree with arbitrarily large cyclic deficiency, and graphs whose cyclic deficiency approaches the number of vertices. Finally, we conjecture that the cyclic deficiency of any graph does not exceed the number of vertices, and we present several results supporting this conjecture. (C) 2018 Elsevier B.V. All rights reserved.
|
|
| 7. |
- Asratian, Armen, Professor, 1951-, et al.
(författare)
-
Decomposing graphs into interval colorable subgraphs and no-wait multi-stage schedules
- 2023
-
Ingår i: Discrete Applied Mathematics. - : ELSEVIER. - 0166-218X .- 1872-6771. ; 335, s. 25-35
-
Tidskriftsartikel (refereegranskat)abstract
- A graph G is called interval colorable if it has a proper edge coloring with colors 1, 2, 3, ... such that the colors of the edges incident to every vertex of G form an interval of integers. Not all graphs are interval colorable; in fact, quite few families have been proved to admit interval colorings. In this paper we introduce and investigate a new notion, the interval coloring thickness of a graph G, denoted theta int(G), which is the minimum number of interval colorable edge-disjoint subgraphs of G whose union is G. Our investigation is motivated by scheduling problems with compactness require-ments, in particular, problems whose solution may consist of several schedules, but where each schedule must not contain any waiting periods or idle times for all involved parties. We first prove that every connected properly 3-edge colorable graph with maximum degree 3 is interval colorable, and using this result, we deduce an upper bound on theta int(G) for general graphs G. We demonstrate that this upper bound can be improved in the case when G is bipartite, planar or complete multipartite and consider some applications in timetabling.
|
|
| 8. |
- Asratian, Armen, et al.
(författare)
-
Solution of Vizings Problem on Interchanges for the case of Graphs with Maximum Degree 4 and Related Results
- 2016
-
Ingår i: Journal of Graph Theory. - : WILEY-BLACKWELL. - 0364-9024 .- 1097-0118. ; 82:4, s. 350-373
-
Tidskriftsartikel (refereegranskat)abstract
- Let G be a Class 1 graph with maximum degree 4 and let t amp;gt;= 5 be an integer. We show that any proper t-edge coloring of G can be transformed to any proper 4-edge coloring of G using only transformations on 2-colored subgraphs (so-called interchanges). This settles the smallest previously unsolved case of a well-known problem of Vizing on interchanges, posed in 1965. Using our result we give an affirmative answer to a question of Mohar for two classes of graphs: we show that all proper 5-edge colorings of a Class 1 graph with maximum degree 4 are Kempe equivalent, that is, can be transformed to each other by interchanges, and that all proper 7-edge colorings of a Class 2 graph with maximum degree 5 are Kempe equivalent. (C) 2015 Wiley Periodicals, Inc.
|
|
| 9. |
- Asratian, Armen, et al.
(författare)
-
Some results on cyclic interval edge colorings of graphs
- 2018
-
Ingår i: Journal of Graph Theory. - : WILEY. - 0364-9024 .- 1097-0118. ; 87:2, s. 239-252
-
Tidskriftsartikel (refereegranskat)abstract
- A proper edge coloring of a graph G with colors 1,2,,t is called a cyclic interval t-coloring if for each vertex v of G the edges incident to v are colored by consecutive colors, under the condition that color 1 is considered as consecutive to color t. We prove that a bipartite graph G of even maximum degree (G)4 admits a cyclic interval (G)-coloring if for every vertex v the degree dG(v) satisfies either dG(v)(G)-2 or dG(v)2. We also prove that every Eulerian bipartite graph G with maximum degree at most eight has a cyclic interval coloring. Some results are obtained for (a,b)-biregular graphs, that is, bipartite graphs with the vertices in one part all having degree a and the vertices in the other part all having degree b; it has been conjectured that all these have cyclic interval colorings. We show that all (4, 7)-biregular graphs as well as all (2r-2,2r)-biregular (r2) graphs have cyclic interval colorings. Finally, we prove that all complete multipartite graphs admit cyclic interval colorings; this proves a conjecture of Petrosyan and Mkhitaryan.
|
|
| 10. |
- Casselgren, Carl Johan
(författare)
-
Anote on one-sided interval edge colorings of bipartite graphs
- 2022
-
Ingår i: Discrete Mathematics. - : Elsevier. - 0012-365X .- 1872-681X. ; 345:2
-
Tidskriftsartikel (refereegranskat)abstract
- For a bipartite graph G with parts X and Y, an X-interval coloring is a proper edge coloring of G by integers such that the colors on the edges incident to any vertex in X form an interval. Denote by chi(int) (G, X) the minimum k such that G has an X-interval coloring with k colors. Casselgren and Toft (2016) [12] asked whether there is a polynomial P(Delta) such that if G has maximum degree at most A, then chi(int)(G, X) <= P(A). In this short note, we answer this question in the affirmative; in fact, we prove that a cubic polynomial suffices. We also deduce some improved upper bounds on chi(int)(G, X) for bipartite graphs with small maximum degree. (C) 2021 The Author(s). Published by Elsevier B.V.
|
|
