umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
On some graph coloring problems
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
2011 (Engelska)Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
Ort, förlag, år, upplaga, sidor
Umeå: Umeå universitet, Institutionen för matematik och matematisk statistik , 2011. , s. 22
Serie
Doctoral thesis / Umeå University, Department of Mathematics, ISSN 1102-8300 ; 48
Nyckelord [en]
List coloring, interval edge coloring, coloring graphs from random lists, biregular graph, avoiding arrays, Latin square, scheduling
Nationell ämneskategori
Diskret matematik
Forskningsämne
matematik
Identifikatorer
URN: urn:nbn:se:umu:diva-43389ISBN: 978-91-7459-198-9 (tryckt)OAI: oai:DiVA.org:umu-43389DiVA, id: diva2:413324
Disputation
2011-05-20, MIT-huset, MA121, Umeå universitet, Umeå, 13:15
Opponent
Handledare
Tillgänglig från: 2011-04-29 Skapad: 2011-04-28 Senast uppdaterad: 2018-06-08Bibliografiskt granskad
Delarbeten
1. Coloring graphs from random lists of fixed size
Öppna denna publikation i ny flik eller fönster >>Coloring graphs from random lists of fixed size
(Engelska)Manuskript (preprint) (Övrigt vetenskapligt)
Identifikatorer
urn:nbn:se:umu:diva-43318 (URN)
Tillgänglig från: 2011-04-28 Skapad: 2011-04-27 Senast uppdaterad: 2018-06-08Bibliografiskt granskad
2. Coloring graphs from random lists of size 2
Öppna denna publikation i ny flik eller fönster >>Coloring graphs from random lists of size 2
(Engelska)Manuskript (preprint) (Övrigt vetenskapligt)
Identifikatorer
urn:nbn:se:umu:diva-43319 (URN)
Tillgänglig från: 2011-04-28 Skapad: 2011-04-27 Senast uppdaterad: 2018-06-08Bibliografiskt granskad
3. Vertex coloring complete multipartite graphs from random lists of size 2
Öppna denna publikation i ny flik eller fönster >>Vertex coloring complete multipartite graphs from random lists of size 2
2011 (Engelska)Ingår i: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 311, nr 13, s. 1150-1157Artikel i tidskrift (Refereegranskat) 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.

Nyckelord
List coloring; Complete multipartite graph; Random list
Nationell ämneskategori
Matematik
Identifikatorer
urn:nbn:se:umu:diva-43323 (URN)10.1016/j.disc.2010.07.013 (DOI)
Tillgänglig från: 2011-04-27 Skapad: 2011-04-27 Senast uppdaterad: 2018-06-08Bibliografiskt granskad
4. Avoiding arrays of odd order by Latin squares
Öppna denna publikation i ny flik eller fönster >>Avoiding arrays of odd order by Latin squares
(Engelska)Manuskript (preprint) (Övrigt vetenskapligt)
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.

Nyckelord
Latin square, avoidability, avoidable array
Nationell ämneskategori
Diskret matematik
Forskningsämne
matematik
Identifikatorer
urn:nbn:se:umu:diva-36026 (URN)
Tillgänglig från: 2010-09-15 Skapad: 2010-09-14 Senast uppdaterad: 2018-06-08Bibliografiskt granskad
5. On avoiding some families of arrays
Öppna denna publikation i ny flik eller fönster >>On avoiding some families of arrays
2012 (Engelska)Ingår i: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 312, nr 5, s. 963-972Artikel i tidskrift (Refereegranskat) 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.

Nyckelord
Latin square, avoiding arrays, list coloring
Nationell ämneskategori
Diskret matematik
Identifikatorer
urn:nbn:se:umu:diva-43325 (URN)10.1016/j.disc.2011.10.028 (DOI)
Tillgänglig från: 2011-04-28 Skapad: 2011-04-27 Senast uppdaterad: 2018-06-08Bibliografiskt granskad
6. On interval edge colorings of (a,b)-biregular bipartitie graphs
Öppna denna publikation i ny flik eller fönster >>On interval edge colorings of (a,b)-biregular bipartitie graphs
2006 (Engelska)Ingår i: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 307, nr 15, s. 1951-1956Artikel i tidskrift (Refereegranskat) Published
Ort, förlag, år, upplaga, sidor
Elsevier B.V., 2006
Identifikatorer
urn:nbn:se:umu:diva-7867 (URN)10.1016/j.disc.2006.11.001 (DOI)
Tillgänglig från: 2008-01-13 Skapad: 2008-01-13 Senast uppdaterad: 2018-06-09Bibliografiskt granskad
7. Proper path-factors and interval edge-coloring of (3,4)-biregular bigraphs
Öppna denna publikation i ny flik eller fönster >>Proper path-factors and interval edge-coloring of (3,4)-biregular bigraphs
2009 (Engelska)Ingår i: Journal of Graph Theory, ISSN 0364-9024, E-ISSN 1097-0118, Vol. 61, nr 2, s. 88-97Artikel i tidskrift (Refereegranskat) 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.

Ort, förlag, år, upplaga, sidor
Wiley Periodicals Inc., 2009
Nyckelord
path factor, interval edge-coloring, biregular bipartite graph
Nationell ämneskategori
Diskret matematik
Forskningsämne
matematik
Identifikatorer
urn:nbn:se:umu:diva-25912 (URN)10.1002/jgt.20370 (DOI)
Tillgänglig från: 2009-09-10 Skapad: 2009-09-10 Senast uppdaterad: 2018-06-08Bibliografiskt granskad
8. On Path Factors of (3,4)-Biregular Bigraphs
Öppna denna publikation i ny flik eller fönster >>On Path Factors of (3,4)-Biregular Bigraphs
2008 (Engelska)Ingår i: Graphs and Combinatorics, ISSN 0911-0119, E-ISSN 1435-5914, Vol. 24, nr 5, s. 405-411Artikel i tidskrift (Refereegranskat) 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.

Ort, förlag, år, upplaga, sidor
SpringerLink, 2008
Nyckelord
Path factor, Biregular bigraph, Interval edge coloring
Identifikatorer
urn:nbn:se:umu:diva-11276 (URN)10.1007/s00373-008-0803-y (DOI)
Tillgänglig från: 2008-12-05 Skapad: 2008-12-05 Senast uppdaterad: 2018-06-09Bibliografiskt granskad
9. A note on path factors of (3,4)-biregular bipartite graphs
Öppna denna publikation i ny flik eller fönster >>A note on path factors of (3,4)-biregular bipartite graphs
(Engelska)Manuskript (preprint) (Övrigt vetenskapligt)
Identifikatorer
urn:nbn:se:umu:diva-43326 (URN)
Tillgänglig från: 2011-04-28 Skapad: 2011-04-27 Senast uppdaterad: 2018-06-08Bibliografiskt granskad

Open Access i DiVA

fulltext(258 kB)2789 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 258 kBChecksumma SHA-512
6e1fbe602614a457cac4a214ea420cbc9558ce4e6c604685c20403d2f9a392a5018fc846d96fbc5e796b4e0b4bf19bca6bd9fde80ae86ceb73c1f2bb2e2dad61
Typ fulltextMimetyp application/pdf

Personposter BETA

Casselgren, Carl Johan

Sök vidare i DiVA

Av författaren/redaktören
Casselgren, Carl Johan
Av organisationen
Institutionen för matematik och matematisk statistik
Diskret matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 2789 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

isbn
urn-nbn

Altmetricpoäng

isbn
urn-nbn
Totalt: 426 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf