umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Exact and Approximate Compression of Transfer Matrices for Graph Homomorphisms
KTH Physics, AlbaNova University Center, SE-106 91 Stockholm, Sweden.
Umeå University, Faculty of Science and Technology, Department of Mathematics and Mathematical Statistics.
2008 (English)In: LMS Journal of Computation and Mathematics, ISSN 1461-1570, E-ISSN 1461-1570, Vol. 11, 1-14 p.Article in journal (Refereed) Published
Abstract [en]

The aim of this paper is to extend the previous work on transfer matrix compression in the case of graph homomorphisms. For H-homomorphisms of lattice-like graphs we demonstrate how the automorphisms of H, as well as those of the underlying lattice, can be used to reduce the size of the relevant transfer matrices. As applications of this method we give currently best known bounds for the number of 4- and 5-colourings of the square grid, and the number of 3- and 4-colourings of the three-dimensional cubic lattice. Finally, we also discuss approximate compression of transfer matrices.

Place, publisher, year, edition, pages
Cambridge University Press, 2008. Vol. 11, 1-14 p.
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:umu:diva-52122DOI: 10.1112/S1461157000000498ISI: 000207626900001OAI: oai:DiVA.org:umu-52122DiVA: diva2:497231
Available from: 2012-02-10 Created: 2012-02-10 Last updated: 2017-12-07Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Lundow, Per-HåkanMarkström, Klas
By organisation
Department of Mathematics and Mathematical Statistics
In the same journal
LMS Journal of Computation and Mathematics
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 43 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf