umu.sePublications

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

Coloring graphs from random lists of size 2PrimeFaces.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}); 2012 (English)In: European journal of combinatorics (Print), ISSN 0195-6698, E-ISSN 1095-9971, Vol. 33, no 2, 168-181 p.Article in journal (Refereed) Published
##### Abstract [en]

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

London: Academic Press, 2012. Vol. 33, no 2, 168-181 p.
##### National Category

Mathematics
##### Identifiers

URN: urn:nbn:se:umu:diva-50912DOI: 10.1016/j.ejc.2011.09.040ISI: 000297890300005OAI: oai:DiVA.org:umu-50912DiVA: diva2:471492
#####

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

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

PrimeFaces.cw("AccordionPanel","widget_formSmash_j_idt462",{id:"formSmash:j_idt462",widgetVar:"widget_formSmash_j_idt462",multiple:true});
Available from: 2012-01-02 Created: 2012-01-02 Last updated: 2017-12-08Bibliographically approved

Let G = G(n) be a graph on n vertices with girth at least g and maximum degree bounded by some absolute constant Delta. Assign to each vertex v of G a list L(v) of colors by choosing each list independently and uniformly at random from all 2-subsets of a color set e of size sigma (n). In this paper we determine, for each fixed g and growing n, the asymptotic probability of the existence of a proper coloring phi such that phi(v) is an element of L(v) for all v is an element of V(G). In particular, we show that if g is odd and sigma (n) = omega(n(1/(2g-2))), then the probability that G has a proper coloring from such a random list assignment tends to 1 as n --> infinity. Furthermore, we show that this is best possible in the sense that for each fixed odd g and each n >= g, there is a graph H = H(n, g) with bounded maximum degree and girth g, such that if sigma (n) = 0(n(1/(2g-2))), then the probability that H has a proper coloring from such a random list assignment tends to 0 as n --> infinity. A corresponding result for graphs with bounded maximum degree and even girth is also given. Finally, by contrast, we show that for a complete graph on n vertices, the property of being colorable from random lists of size 2, where the lists are chosen uniformly at random from a color set of size sigma (n), exhibits a sharp threshold at sigma (n) = 2n. (C) 2011 Elsevier Ltd. All rights reserved.

doi
urn-nbn$(function(){PrimeFaces.cw("Tooltip","widget_formSmash_j_idt1166",{id:"formSmash:j_idt1166",widgetVar:"widget_formSmash_j_idt1166",showEffect:"fade",hideEffect:"fade",showDelay:500,hideDelay:300,target:"formSmash:altmetricDiv"});});

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