Change search
ReferencesLink to record
Permanent link

Direct link
On avoiding some families of arrays
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
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.

Place, publisher, year, edition, pages
2012. Vol. 312, no 5, 963-972 p.
Keyword [en]
Latin square, avoiding arrays, list coloring
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-43325DOI: 10.1016/j.disc.2011.10.028OAI: oai:DiVA.org:umu-43325DiVA: diva2:413024
Available from: 2011-04-28 Created: 2011-04-27 Last updated: 2012-05-23Bibliographically approved
In thesis
1. On some graph coloring problems
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. 22 p.
Series
Doctoral thesis / Umeå University, Department of Mathematics, ISSN 1102-8300 ; 48
Keyword
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: 2011-05-20Bibliographically approved

Open Access in DiVA

On avoiding some families of arrays(214 kB)100 downloads
File information
File name FULLTEXT02.pdfFile size 214 kBChecksum SHA-512
170d24a9ab080546b51893db2edab67e08f36dc72d4a4b597f679d2ab7491d61a175c35054185f9c4cb63f227a8a33fa1d6ff237d350b0845adfa7653993dd62
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

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

Search outside of DiVA

GoogleGoogle Scholar
Total: 100 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

Altmetric score

Total: 73 hits
ReferencesLink to record
Permanent link

Direct link