2026-07-24T06:45:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16088 2024-03-06T10:56:55Z ddc:004 open_access

On the Independence Number of Random Trees via Tricolourations Bellin, Etienne Independence number simply generated tree Galton-Watson tree tricolouration We are interested in the independence number of large random simply generated trees and related parameters, such as their matching number or the kernel dimension of their adjacency matrix. We express these quantities using a canonical tricolouration, which is a way to colour the vertices of a tree with three colours. As an application we obtain limit theorems in L^p for the renormalised independence number in large simply generated trees (including large size-conditioned Bienaymé-Galton-Watson trees). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Etienne Bellin 2022 Is Part Of LIPIcs, Volume 225, 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AofA.2022.2 urn:nbn:de:0030-drops-160886 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2022.2 eng https://creativecommons.org/licenses/by/4.0/legalcode