| 1. |
- Asratian, Armen S., 1951-, et al.
(author)
-
Stable properties of graphs
- 1991
-
In: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 90:2, s. 143-152
-
Journal article (peer-reviewed)abstract
- Abstract For many properties P Bondy and Chvátal (1976) have found sufficient conditions such that if a graph G + uv has property P then G itself has property P. In this paper we will give a generalization that will improve ten of these conditions.
|
|
| 2. |
- Linusson, Svante
(author)
-
Extended pattern avoidance
- 2002
-
In: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 246:1-3, s. 219-230
-
Journal article (peer-reviewed)abstract
- A 0-1 matrix is said to be extendably tau-avoiding if it can be the upper left corner of a tau-avoiding permutation matrix. This concept arose in Eriksson and Linusson (Electron. J. Combin. 2 (1995) R6) where the surprising result that the number of extendably 321-avoiding rectangles are enumerated by the ballot numbers was proved, Here we study the other five patterns of length three. The main result is that the six patterns of length three divide into only two cases, no easy symmetry can explain this. Another result is that the Simion-Schmidt-West bijection for permutations avoiding patterns 12tau and 21tau works also for extended pattern avoidance. As an application, we use the results on extended pattern avoidance to prove a sequence of refinements on the enumeration of permutations avoiding patterns of length 3. The results and proofs use many properties and refinements of the Catalan numbers. (C) 2002 Elsevier Science B.V. All rights reserved.
|
|
| 3. |
- Asratian, Armen, et al.
(author)
-
On interval edge colorings of (a, ß)-biregular bipartite graphs
- 2007
-
In: Discrete Mathematics. - : Elsevier BV. - 0012-365X .- 1872-681X. ; 307:15, s. 1951-1956
-
Journal article (peer-reviewed)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.
|
|
| 4. |
- Casselgren, Carl Johan
(author)
-
Anote on one-sided interval edge colorings of bipartite graphs
- 2022
-
In: Discrete Mathematics. - : Elsevier. - 0012-365X .- 1872-681X. ; 345:2
-
Journal article (peer-reviewed)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.
|
|
| 5. |
- Casselgren, Carl Johan, et al.
(author)
-
Completing partial Latin squares with one filled row, column and symbol
- 2013
-
In: Discrete Mathematics. - : Elsevier. - 0012-365X .- 1872-681X. ; 313:9, s. 1011-1017
-
Journal article (peer-reviewed)abstract
- Let P be an n×n partial Latin square every non-empty cell of which lies in a fixed row r, a fixed column c or contains a fixed symbol s. Assume further that s is the symbol of cell (r,c) in P. We prove that P is completable to a Latin square if n≥8 and n is divisible by 4, or n≤7 and n∉{3,4,5}. Moreover, we present a polynomial algorithm for the completion of such a partial Latin square.
|
|
| 6. |
- Casselgren, Carl Johan, et al.
(author)
-
On interval and cyclic interval edge colorings of (3,5)-biregular graphs
- 2017
-
In: Discrete Mathematics. - : ELSEVIER SCIENCE BV. - 0012-365X .- 1872-681X. ; 340:11, s. 2678-2687
-
Journal article (peer-reviewed)abstract
- A proper edge coloring f of a graph G with colors 1, 2, 3, . . . , t is called an interval coloring if the colors on the edges incident to every vertex of G form an interval of integers. The coloring f is cyclic interval if for every vertex v of G, the colors on the edges incident to v either form an interval or the set {1, . . . t} \ {f (e) : e is incident to v} is an interval. A bipartite graph G is (a, b)-biregular if every vertex in one part has degree a and every vertex in the other part has degree b; it has been conjectured that all such graphs have interval colorings. We prove that every (3, 5)-biregular graph has a cyclic interval coloring and we give several sufficient conditions for a (3, 5)-biregular graph to admit an interval coloring. (C) 2016 Elsevier B.V. All rights reserved.
|
|
| 7. |
- Casselgren, Carl Johan, et al.
(author)
-
One-sided interval edge-colorings of bipartite graphs
- 2016
-
In: Discrete Mathematics. - : ELSEVIER SCIENCE BV. - 0012-365X .- 1872-681X. ; 339:11, s. 2628-2639
-
Journal article (peer-reviewed)abstract
- Let G be a bipartite graph with bipartition (X, Y). An X-interval coloring of G 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. In this paper we give various upper and lower bounds on chi(int)(G, X) in terms of the vertex degrees of G. We also determine chi(int) (G, X) exactly for some classes of bipartite graphs G. Furthermore, we present upper bounds on chi(int) (G, X) for classes of bipartite graphs G with maximum degree Delta(G) at most 9: in particular, if Delta(G) = 4, then chi(int) (G, X) amp;lt;= 6; if Delta(G) = 5, then chi(int) (G, X) amp;lt;= 15; if Delta(G) = 6, then chi(int) (G, X) amp;lt;= 33. (C) 2016 Elsevier B.V. All rights reserved.
|
|
| 8. |
- Casselgren, Carl Johan, et al.
(author)
-
Restricted extension of sparse partial edge colorings of hypercubes
- 2020
-
In: Discrete Mathematics. - : ELSEVIER. - 0012-365X .- 1872-681X. ; 343:11
-
Journal article (peer-reviewed)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.
|
|
| 9. |
- Casselgren, Carl Johan, et al.
(author)
-
Some bounds on the number of colors in interval and cyclic interval edge colorings of graphs
- 2018
-
In: Discrete Mathematics. - : ELSEVIER SCIENCE BV. - 0012-365X .- 1872-681X. ; 341:3, s. 627-637
-
Journal article (peer-reviewed)abstract
- An interval t-coloring of a multigraph G is a proper edge coloring with colors 1, ... , t such that the colors of the edges incident with every vertex of G are colored by consecutive colors. A cyclic interval t-coloring of a multigraph G is a proper edge coloring with colors 1, ... , t such that the colors of the edges incident with every vertex of G are colored by consecutive colors, under the condition that color 1 is considered as consecutive to color t. Denote by w(G) (w(c)(G)) and W(G) (W-c(G)) the minimum and maximum number of colors in a (cyclic) interval coloring of a multigraph G, respectively. We present some new sharp bounds on w(G) and W(G) for multigraphs G satisfying various conditions. In particular, we show that if G is a 2-connected multigraph with an interval coloring, then W(G) amp;lt;= 1 + left perpendicular vertical bar V(G)vertical bar/2 right perpendicular (Delta(G) - 1). We also give several results towards the general conjecture that W-c(G) amp;lt;= I vertical bar V(G)vertical bar for any triangle-free graph G with a cyclic interval coloring; we establish that approximate versions of this conjecture hold for several families of graphs, and we prove that the conjecture is true for graphs with maximum degree at most 4. (C) 2017 Elsevier B.V. All rights reserved.
|
|
| 10. |
- Eriksson, Henrik, et al.
(author)
-
Sorting a bridge hand.
- 2001
-
In: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 241:1-3, s. 289-300
-
Journal article (peer-reviewed)
|
|
