Independence numbers and chromatic numbers of random subgraphs in some sequences of graphs (Q483670)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Independence numbers and chromatic numbers of random subgraphs in some sequences of graphs |
scientific article |
Statements
Independence numbers and chromatic numbers of random subgraphs in some sequences of graphs (English)
0 references
17 December 2014
0 references
Let \(G(n,r,s)\) be a graph having the vertex set \(V(n,r)=\{x=(x_1,\dots,x_n)\mid x_i\in\{0,1\}, x_1+\dots+x_n=r\}\) and the edge set \(E(n,r,s)=\{\{x,y\}\mid d(x,y)=s\}\). Now let the random graph \(\mathcal{G}(G(n,r,s),p)\) be defined as a random element of the set of all the spanning subgraphs \(H=(V_n,E)\) of \(G(n,r,s)=(V_n,E_n)\) having binomial distribution: \(\operatorname P(\mathcal{G}(G(n,r,s),p)=H)=p^{|E|}(1-p)^{|E_n|-|E|}\). The authors study the independence number \(s\) and the chromatic numbers of the random graphs \(\mathcal{G}(G(n,r,s),1/2)\).
0 references
random graph
0 references
independence number
0 references
chromatic number
0 references
0 references