liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • 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
Coloring Complete and Complete Bipartite Graphs from Random Lists
Linköping University, Department of Mathematics, Mathematics and Applied Mathematics. Linköping University, Faculty of Science & Engineering.
Umeå University, Sweden.
2016 (English)In: Graphs and Combinatorics, ISSN 0911-0119, E-ISSN 1435-5914, Vol. 32, no 2, 533-542 p.Article in journal (Refereed) Published
Resource type
Text
Abstract [en]

Assign to each vertex v of the complete graph on n vertices a list L(v) of colors by choosing each list independently and uniformly at random from all f(n)-subsets of a color set , where f(n) is some integer-valued function of n. Such a list assignment L is called a random (f(n), [n])-list assignment. In this paper, we determine the asymptotic probability (as ) of the existence of a proper coloring of , such that for every vertex v of . We show that this property exhibits a sharp threshold at . Additionally, we consider the corresponding problem for the line graph of a complete bipartite graph with parts of size m and n, respectively. We show that if , , and L is a random (f(n), [n])-list assignment for the line graph of , then with probability tending to 1, as , there is a proper coloring of the line graph of with colors from the lists.

Place, publisher, year, edition, pages
SPRINGER JAPAN KK , 2016. Vol. 32, no 2, 533-542 p.
Keyword [en]
List coloring; Random list; Coloring from random lists; Complete graph; Complete bipartite graph
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:liu:diva-126248DOI: 10.1007/s00373-015-1587-5ISI: 000371081000007OAI: oai:DiVA.org:liu-126248DiVA: diva2:913454
Available from: 2016-03-21 Created: 2016-03-21 Last updated: 2017-11-30

Open Access in DiVA

fulltext(171 kB)64 downloads
File information
File name FULLTEXT01.pdfFile size 171 kBChecksum SHA-512
86319828db1686b48dba59aa3ee38997eef8fe28253a0fc5fb078898a8edad5259707eeaa4b200b8aa9bac7236a365dc6ee94a2d17d04644880f57a87de3c03d
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Authority records BETA

Casselgren, Carl Johan

Search in DiVA

By author/editor
Casselgren, Carl Johan
By organisation
Mathematics and Applied MathematicsFaculty of Science & Engineering
In the same journal
Graphs and Combinatorics
Discrete Mathematics

Search outside of DiVA

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

doi
urn-nbn

Altmetric score

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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • 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