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 avoiding some families of arrays
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för matematik och matematisk statistik.
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.

Ort, förlag, år, upplaga, sidor
2012. Vol. 312, nr 5, s. 963-972
Nyckelord [en]
Latin square, avoiding arrays, list coloring
Nationell ämneskategori
Diskret matematik
Identifikatorer
URN: urn:nbn:se:umu:diva-43325DOI: 10.1016/j.disc.2011.10.028OAI: oai:DiVA.org:umu-43325DiVA, id: diva2:413024
Tillgänglig från: 2011-04-28 Skapad: 2011-04-27 Senast uppdaterad: 2018-06-08Bibliografiskt granskad
Ingår i avhandling
1. On some graph coloring problems
Öppna denna publikation i ny flik eller fönster >>On some graph coloring problems
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
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:nbn:se:umu:diva-43389 (URN)978-91-7459-198-9 (ISBN)
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

Open Access i DiVA

On avoiding some families of arrays(214 kB)170 nedladdningar
Filinformation
Filnamn FULLTEXT02.pdfFilstorlek 214 kBChecksumma SHA-512
170d24a9ab080546b51893db2edab67e08f36dc72d4a4b597f679d2ab7491d61a175c35054185f9c4cb63f227a8a33fa1d6ff237d350b0845adfa7653993dd62
Typ fulltextMimetyp application/pdf

Övriga länkar

Förlagets fulltext

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
I samma tidskrift
Discrete Mathematics
Diskret matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 170 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.

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 238 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