liu.seSearch for publications in DiVA

CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_upper_j_idt146",{id:"formSmash:upper:j_idt146",widgetVar:"widget_formSmash_upper_j_idt146",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:upper:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_upper_j_idt147_j_idt149",{id:"formSmash:upper:j_idt147:j_idt149",widgetVar:"widget_formSmash_upper_j_idt147_j_idt149",target:"formSmash:upper:j_idt147:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});

Coloring graphs of various maximum degree from random listsPrimeFaces.cw("AccordionPanel","widget_formSmash_some",{id:"formSmash:some",widgetVar:"widget_formSmash_some",multiple:true}); PrimeFaces.cw("AccordionPanel","widget_formSmash_all",{id:"formSmash:all",widgetVar:"widget_formSmash_all",multiple:true});
function selectAll()
{
var panelSome = $(PrimeFaces.escapeClientId("formSmash:some"));
var panelAll = $(PrimeFaces.escapeClientId("formSmash:all"));
panelAll.toggle();
toggleList(panelSome.get(0).childNodes, panelAll);
toggleList(panelAll.get(0).childNodes, panelAll);
}
/*Toggling the list of authorPanel nodes according to the toggling of the closeable second panel */
function toggleList(childList, panel)
{
var panelWasOpen = (panel.get(0).style.display == 'none');
// console.log('panel was open ' + panelWasOpen);
for (var c = 0; c < childList.length; c++) {
if (childList[c].classList.contains('authorPanel')) {
clickNode(panelWasOpen, childList[c]);
}
}
}
/*nodes have styleClass ui-corner-top if they are expanded and ui-corner-all if they are collapsed */
function clickNode(collapse, child)
{
if (collapse && child.classList.contains('ui-corner-top')) {
// console.log('collapse');
child.click();
}
if (!collapse && child.classList.contains('ui-corner-all')) {
// console.log('expand');
child.click();
}
}
PrimeFaces.cw("AccordionPanel","widget_formSmash_responsibleOrgs",{id:"formSmash:responsibleOrgs",widgetVar:"widget_formSmash_responsibleOrgs",multiple:true}); 2018 (English)In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 52, no 1, p. 54-73Article in journal (Refereed) Published
##### Abstract [en]

##### Place, publisher, year, edition, pages

WILEY , 2018. Vol. 52, no 1, p. 54-73
##### Keyword [en]

coloring from random lists; list coloring; random list
##### National Category

Probability Theory and Statistics
##### Identifiers

URN: urn:nbn:se:liu:diva-143607DOI: 10.1002/rsa.20725ISI: 000415879600003OAI: oai:DiVA.org:liu-143607DiVA: diva2:1165638
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt434",{id:"formSmash:j_idt434",widgetVar:"widget_formSmash_j_idt434",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt440",{id:"formSmash:j_idt440",widgetVar:"widget_formSmash_j_idt440",multiple:true});
#####

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt446",{id:"formSmash:j_idt446",widgetVar:"widget_formSmash_j_idt446",multiple:true});
##### Note

Let G=G(n) be a graph on n vertices with maximum degree = (n). Assign to each vertex v of G a list L(v) of colors by choosing each list independently and uniformly at random from all k-subsets of a color set C of size C sigma=sigma(n). Such a list assignment is called a random(k,C)-list assignment. In this paper, we are interested in determining the asymptotic probability (as n ) of the existence of a proper coloring phi of G, such that phi(v)L(v) for every vertex v of G, a so-called L-coloring. We give various lower bounds on sigma, in terms of n, k, and , which ensures that with probability tending to 1 as n there is an L-coloring of G. In particular, we show, for all fixed k and growing n, that if sigma(n)=(n1/k21/k) and =O(n), then the probability that G has an L-coloring tends to 1 as n. If k2 and =(n1/2), then the same conclusion holds provided that sigma=(). We also give related results for other bounds on , when k is constant or a strictly increasing function of n.

Funding Agencies|SVeFUM; Mittag-Leffler Institute

Available from: 2017-12-13 Created: 2017-12-13 Last updated: 2018-01-03
doi
urn-nbn$(function(){PrimeFaces.cw("Tooltip","widget_formSmash_j_idt1143",{id:"formSmash:j_idt1143",widgetVar:"widget_formSmash_j_idt1143",showEffect:"fade",hideEffect:"fade",showDelay:500,hideDelay:300,target:"formSmash:altmetricDiv"});});

CiteExport$(function(){PrimeFaces.cw("TieredMenu","widget_formSmash_lower_j_idt1196",{id:"formSmash:lower:j_idt1196",widgetVar:"widget_formSmash_lower_j_idt1196",autoDisplay:true,overlay:true,my:"left top",at:"left bottom",trigger:"formSmash:lower:exportLink",triggerEvent:"click"});}); $(function(){PrimeFaces.cw("OverlayPanel","widget_formSmash_lower_j_idt1197_j_idt1199",{id:"formSmash:lower:j_idt1197:j_idt1199",widgetVar:"widget_formSmash_lower_j_idt1197_j_idt1199",target:"formSmash:lower:j_idt1197:permLink",showEffect:"blind",hideEffect:"fade",my:"right top",at:"right bottom",showCloseIcon:true});});