Change search

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
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, p. 533-542Article in journal (Refereed) Published
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, p. 533-542
##### Keyword [en]
List coloring; Random list; Coloring from random lists; Complete graph; Complete bipartite graph
##### National Category
Discrete Mathematics
##### Identifiers
ISI: 000371081000007OAI: oai:DiVA.org:liu-126248DiVA, id: diva2:913454
Available from: 2016-03-21 Created: 2016-03-21 Last updated: 2017-11-30

#### Open Access in DiVA

##### File information
File name FULLTEXT01.pdfFile size 171 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Publisher's full text

#### 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
##### On the subject
Discrete Mathematics

#### Search outside of DiVA

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: 182 hits

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
v. 2.33.0
|