umu.sePublications
Change search
Link to record
Permanent link

Direct link
BETA
Casselgren, Carl Johan
Publications (10 of 14) Show all publications
Andren, L. J., Casselgren, C. J. & Öhman, L.-D. (2013). Avoiding Arrays of Odd Order by Latin Squares. Combinatorics, probability & computing, 22(2), 184-212
Open this publication in new window or tab >>Avoiding Arrays of Odd Order by Latin Squares
2013 (English)In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 22, no 2, p. 184-212Article in journal (Refereed) Published
Abstract [en]

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 <= 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 -> infinity.

National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-66768 (URN)10.1017/S0963548312000570 (DOI)000314296400002 ()
Available from: 2013-03-15 Created: 2013-03-05 Last updated: 2018-06-08Bibliographically approved
Casselgren, C. J. (2012). Coloring graphs from random lists of size 2. European journal of combinatorics (Print), 33(2), 168-181
Open this publication in new window or tab >>Coloring graphs from random lists of size 2
2012 (English)In: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 33, no 2, p. 168-181Article in journal (Refereed) Published
Abstract [en]

Let G = G(n) be a graph on n vertices with girth at least g and maximum degree bounded by some absolute constant Delta. Assign to each vertex v of G a list L(v) of colors by choosing each list independently and uniformly at random from all 2-subsets of a color set e of size sigma (n). In this paper we determine, for each fixed g and growing n, the asymptotic probability of the existence of a proper coloring phi such that phi(v) is an element of L(v) for all v is an element of V(G). In particular, we show that if g is odd and sigma (n) = omega(n(1/(2g-2))), then the probability that G has a proper coloring from such a random list assignment tends to 1 as n --> infinity. Furthermore, we show that this is best possible in the sense that for each fixed odd g and each n >= g, there is a graph H = H(n, g) with bounded maximum degree and girth g, such that if sigma (n) = 0(n(1/(2g-2))), then the probability that H has a proper coloring from such a random list assignment tends to 0 as n --> infinity. A corresponding result for graphs with bounded maximum degree and even girth is also given. Finally, by contrast, we show that for a complete graph on n vertices, the property of being colorable from random lists of size 2, where the lists are chosen uniformly at random from a color set of size sigma (n), exhibits a sharp threshold at sigma (n) = 2n. (C) 2011 Elsevier Ltd. All rights reserved.

Place, publisher, year, edition, pages
London: Academic Press, 2012
National Category
Mathematics
Identifiers
urn:nbn:se:umu:diva-50912 (URN)10.1016/j.ejc.2011.09.040 (DOI)000297890300005 ()
Available from: 2012-01-02 Created: 2012-01-02 Last updated: 2018-06-08Bibliographically approved
Casselgren, C. J. (2012). On avoiding some families of arrays. Discrete Mathematics, 312(5), 963-972
Open this publication in new window or tab >>On avoiding some families of arrays
2012 (English)In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 312, no 5, p. 963-972Article in journal (Refereed) Published
Abstract [en]

An n×n array A with entries from {1,…,n} is avoidable if there is an n×n Latin square L such that no cell in L contains a symbol that occurs in the corresponding cell in A. We show that the problem of determining whether an array that contains at most two entries per cell is avoidable is NP-complete, even in the case when the array has entries from only two distinct symbols. Assuming that PNP, this disproves a conjecture by Öhman. Furthermore, we present several new families of avoidable arrays. In particular, every single entry array (arrays where each cell contains at most one symbol) of order n≥2k with entries from at most k distinct symbols and where each symbol occurs in at most n−2 cells is avoidable, and every single entry array of order n, where each of the symbols 1,…,n occurs in at most cells, is avoidable. Additionally, if k≥2, then every single entry array of order at least n≥4, where at most k rows contain non-empty cells and where each symbol occurs in at most nk+1 cells, is avoidable.

Keywords
Latin square, avoiding arrays, list coloring
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-43325 (URN)10.1016/j.disc.2011.10.028 (DOI)
Available from: 2011-04-28 Created: 2011-04-27 Last updated: 2018-06-08Bibliographically approved
Casselgren, C. J. (2011). A note on path factors of (3,4)-biregular bipartite graphs. The Electronic Journal of Combinatorics, 18(1), P218
Open this publication in new window or tab >>A note on path factors of (3,4)-biregular bipartite graphs
2011 (English)In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 18, no 1, p. P218-Article in journal (Refereed) Published
Abstract [en]

A proper edge coloring of a graph G with colors 1,2,3, ... is called an interval coloring if the colors on the edges incident with any vertex are consecutive. A bipartite graphis (3,4)-biregular if all vertices in one part have degree 3 and all vertices in the other part have degree 4. Recently it was proved [J. Graph Theory 61 (2009), 88-97] that if such a graph G has a spanning subgraph whose components are paths with end points at 3-valent vertices and lengths in {2,4,6,8}, then G has an interval coloring. It was also conjectured that every simple (3,4)-biregular bipartite graph has such a subgraph. We provide some evidence for this conjecture by proving that a simple (3,4)-biregular bipartite graph has a spanning subgraph whose components are nontrivial paths with endpoints at 3-valent vertices and lengths not exceeding 22.

Keywords
path factor, biregular bipartite graph, interval edge coloring
National Category
Mathematics
Identifiers
urn:nbn:se:umu:diva-50410 (URN)000296974200001 ()
Available from: 2011-12-13 Created: 2011-12-08 Last updated: 2018-06-08Bibliographically approved
Casselgren, C. J. (2011). On some graph coloring problems. (Doctoral dissertation). Umeå: Umeå universitet, Institutionen för matematik och matematisk statistik
Open this publication in new window or tab >>On some graph coloring problems
2011 (English)Doctoral thesis, comprehensive summary (Other academic)
Place, publisher, year, edition, pages
Umeå: Umeå universitet, Institutionen för matematik och matematisk statistik, 2011. p. 22
Series
Doctoral thesis / Umeå University, Department of Mathematics, ISSN 1102-8300 ; 48
Keywords
List coloring, interval edge coloring, coloring graphs from random lists, biregular graph, avoiding arrays, Latin square, scheduling
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:umu:diva-43389 (URN)978-91-7459-198-9 (ISBN)
Public defence
2011-05-20, MIT-huset, MA121, Umeå universitet, Umeå, 13:15
Opponent
Supervisors
Available from: 2011-04-29 Created: 2011-04-28 Last updated: 2018-06-08Bibliographically approved
Casselgren, C. J. (2011). Vertex coloring complete multipartite graphs from random lists of size 2. Discrete Mathematics, 311(13), 1150-1157
Open this publication in new window or tab >>Vertex coloring complete multipartite graphs from random lists of size 2
2011 (English)In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 311, no 13, p. 1150-1157Article in journal (Refereed) Published
Abstract [en]

Let Ks×m be the complete multipartite graph with s parts and m vertices in each part. Assign to each vertex v of Ks×m a list L(v) of colors, by choosing each list uniformly at random from all 2-subsets of a color set C of size σ(m). In this paper we determine, for all fixed s and growing m, the asymptotic probability of the existence of a proper coloring φ, such that φ(v)∈L(v) for all vV(Ks×m). We show that this property exhibits a sharp threshold at σ(m)=2(s−1)m.

Keywords
List coloring; Complete multipartite graph; Random list
National Category
Mathematics
Identifiers
urn:nbn:se:umu:diva-43323 (URN)10.1016/j.disc.2010.07.013 (DOI)
Available from: 2011-04-27 Created: 2011-04-27 Last updated: 2018-06-08Bibliographically approved
Asratian, A. S., Casselgren, C. J., Vandenbussche, J. & West, D. B. (2009). Proper path-factors and interval edge-coloring of (3,4)-biregular bigraphs. Journal of Graph Theory, 61(2), 88-97
Open this publication in new window or tab >>Proper path-factors and interval edge-coloring of (3,4)-biregular bigraphs
2009 (English)In: Journal of Graph Theory, ISSN 0364-9024, E-ISSN 1097-0118, Vol. 61, no 2, p. 88-97Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
Wiley Periodicals Inc., 2009
Keywords
path factor, interval edge-coloring, biregular bipartite graph
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:umu:diva-25912 (URN)10.1002/jgt.20370 (DOI)
Available from: 2009-09-10 Created: 2009-09-10 Last updated: 2018-06-08Bibliographically approved
Asratian, A. S. & Casselgren, C. J. (2008). On Path Factors of (3,4)-Biregular Bigraphs. Graphs and Combinatorics, 24(5), 405-411
Open this publication in new window or tab >>On Path Factors of (3,4)-Biregular Bigraphs
2008 (English)In: Graphs and Combinatorics, ISSN 0911-0119, E-ISSN 1435-5914, Vol. 24, no 5, p. 405-411Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
SpringerLink, 2008
Keywords
Path factor, Biregular bigraph, Interval edge coloring
Identifiers
urn:nbn:se:umu:diva-11276 (URN)10.1007/s00373-008-0803-y (DOI)
Available from: 2008-12-05 Created: 2008-12-05 Last updated: 2018-06-09Bibliographically approved
Asratian, A. S. & Casselgren, C. J. (2006). On interval edge colorings of (a,b)-biregular bipartitie graphs. Discrete Mathematics, 307(15), 1951-1956
Open this publication in new window or tab >>On interval edge colorings of (a,b)-biregular bipartitie graphs
2006 (English)In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 307, no 15, p. 1951-1956Article in journal (Refereed) Published
Place, publisher, year, edition, pages
Elsevier B.V., 2006
Identifiers
urn:nbn:se:umu:diva-7867 (URN)10.1016/j.disc.2006.11.001 (DOI)
Available from: 2008-01-13 Created: 2008-01-13 Last updated: 2018-06-09Bibliographically approved
Casselgren, C. J.A note on path factors of (3,4)-biregular bipartite graphs.
Open this publication in new window or tab >>A note on path factors of (3,4)-biregular bipartite graphs
(English)Manuscript (preprint) (Other academic)
Identifiers
urn:nbn:se:umu:diva-43326 (URN)
Available from: 2011-04-28 Created: 2011-04-27 Last updated: 2018-06-08Bibliographically approved

Search in DiVA

Show all publications