Change search
ReferencesLink to record
Permanent link

Direct link
On some graph coloring problems
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
2011 (English)Doctoral thesis, comprehensive summary (Other academic)
Place, publisher, year, edition, pages
Umeå: Umeå universitet, Institutionen för matematik och matematisk statistik , 2011. , 22 p.
Series
Doctoral thesis / Umeå University, Department of Mathematics, ISSN 1102-8300 ; 48
Keyword [en]
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: urn:nbn:se:umu:diva-43389ISBN: 978-91-7459-198-9OAI: oai:DiVA.org:umu-43389DiVA: diva2:413324
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: 2011-05-20Bibliographically approved
List of papers
1. Coloring graphs from random lists of fixed size
Open this publication in new window or tab >>Coloring graphs from random lists of fixed size
(English)Manuscript (preprint) (Other academic)
Identifiers
urn:nbn:se:umu:diva-43318 (URN)
Available from: 2011-04-28 Created: 2011-04-27 Last updated: 2011-04-28Bibliographically approved
2. Coloring graphs from random lists of size 2
Open this publication in new window or tab >>Coloring graphs from random lists of size 2
(English)Manuscript (preprint) (Other academic)
Identifiers
urn:nbn:se:umu:diva-43319 (URN)
Available from: 2011-04-28 Created: 2011-04-27 Last updated: 2011-04-28Bibliographically approved
3. Vertex coloring complete multipartite graphs from random lists of size 2
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, 1150-1157 p.Article 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.

Keyword
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: 2011-09-28Bibliographically approved
4. Avoiding arrays of odd order by Latin squares
Open this publication in new window or tab >>Avoiding arrays of odd order by Latin squares
(English)Manuscript (preprint) (Other academic)
Abstract [en]

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.

Keyword
Latin square, avoidability, avoidable array
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:umu:diva-36026 (URN)
Available from: 2010-09-15 Created: 2010-09-14 Last updated: 2011-05-20Bibliographically approved
5. On avoiding some families of arrays
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, 963-972 p.Article 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.

Keyword
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: 2012-05-23Bibliographically approved
6. On interval edge colorings of (a,b)-biregular bipartitie graphs
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, 1951-1956 p.Article 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: 2011-04-28Bibliographically approved
7. Proper path-factors and interval edge-coloring of (3,4)-biregular bigraphs
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, 88-97 p.Article 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
Keyword
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: 2011-04-28Bibliographically approved
8. On Path Factors of (3,4)-Biregular Bigraphs
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, 405-411 p.Article 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
Keyword
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: 2011-04-28Bibliographically approved
9. 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: 2011-04-28Bibliographically approved

Open Access in DiVA

fulltext(258 kB)1867 downloads
File information
File name FULLTEXT01.pdfFile size 258 kBChecksum SHA-512
6e1fbe602614a457cac4a214ea420cbc9558ce4e6c604685c20403d2f9a392a5018fc846d96fbc5e796b4e0b4bf19bca6bd9fde80ae86ceb73c1f2bb2e2dad61
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Casselgren, Carl Johan
By organisation
Department of Mathematics and Mathematical Statistics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 1867 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 217 hits
ReferencesLink to record
Permanent link

Direct link