The fractional chromatic number of generalized cones over graphs (Q2138562): Difference between revisions

Let \(G\) be a connected graph with \(V(G)=\{u_1,\dots,u_n\}\). A \(1\)-cone \(\Delta_1(G)\) over \(G\) is simply the join of \(G\) and one vertex graph \(K_1=\{v\}\), that is \(\Delta_1(G)=G\vee \{v\}\). From vertices of \(1\)-cone we construct a \(2\)-cone \(\Delta_2(G)\) by \(V(\Delta_2(G))=V(G)\cup\{u_1^1,\dots,u_n^1\}\cup\{v\}\) and \(E(\Delta_2(G))=E(G)\cup\{u_i^1u_j:u_iu_j\in E(G)\}\cup\{vu_i^1:i\in\{1,\dots,n\}\}\). Clearly, \(\Delta_2(G)\) is a famous Mycielski construction over \(G\). Inductively we define the \(k\)-cone \(\Delta_k(G)\) over \(G\) from the \((k-1)\)-cone \(\Delta_{k-1}(G)\) over \(G\) for every integer \(k\geq 3\). From \(\Delta_{k-1}(G)\) first delete all edges \(\{vu_i^{k-2}:i\in\{1,\dots,n\}\}\) and then add vertices \(\{u_1^{k-1},\dots,u_n^{k-1}\}\) and edges \(\{u_i^{k-1}u_j^{k-2}:u_iu_j\in E(G)\}\cup\{vu_i^{k-1}:i\in\{1,\dots,n\}\}\). Let \(G\) and \(H\) be connected graphs and let \(h:V(H)\rightarrow \mathbb{N}\) be a mapping. The \((H,h)\)-cone over \(G\), denoted by \(\Delta_{H,h}(G)\) is obtained from disjoint copies of \(\Delta_{h(w)}(G)\) for every vertex \(w\in V(H)\) where the copies of \(G\) on vertices \(\{u_1,\dots,u_n\}\) in \(\Delta_{h(w)}(G)\) is contracted into a single vertex for every \(w\in V(H)\). Further, edges between the same vertices in a different copies \(\Delta_{h(w)}(G)\) and \(\Delta_{h(w')}(G)\) are added whenever \(ww'\in E(H)\). Let \(\mathcal{I}(G)\) denote the family of independent sets of a graph \(G\). A mapping \(f:\mathcal{I}(G)\rightarrow [0,1]\) is called a fractional coloring if \(\sum_{v\in I, I\in \mathcal{I}(G)}f(I)\geq 1\) for every \(v\in V(G)\). The fractional chromatic number \(\chi_f(G)\) of \(G\) is the minimum weight \(w(f)=\sum_{I\in \mathcal{I}(G)}f(I)\) over all fractional colorings \(f\). The main result of this contribution is the exact value for the fractional chromatic number of the \((H,h)\)-cone over \(G\) under additional condition that \(\chi_f(H)\leq\chi_f(G)\).