Vertex Partitions and Maximum \G-free Subgraphs

MaRDI QIDQ6404627zbMATH OpenFDO

Authors Yaser Rowshan

Publication date 11 July 2022

Abstract: For a given graph $H$ and the graphical properties $P_1,P_2,ldots,P_k$, we say the graph $H$ has a $(V_1,V_2,ldots,V_k)$-decomposition, if for each $iin[k]$, the subgraph induced on $V_i$ has a property $P_i$. Bollob'{a}s and Manvel, have shown that for a graph $H$ with maximum degree $Delta(H)geq3$ and clique number $omega(H)leqDelta(H)$, if $Delta(H)=p+q$, then there exists a $(V_1,V_2)$-decomposition of $V(H)$, such that $Delta(H[V_1])leqp$, $Delta(H[V_2])leqq$, $H[V_1]$ is $(p-1)$-degenerate, and $H[V_2]$ is $(q-1)$-degenerate. Matamala, has shown that if $Delta(H)=p+q$, then there exists a $(V_1,V_2)$-decomposition of $V(H)$, so that $H[V_1]$ is a maximum $(p-1)$-degenerate induced subgraph and $H[V_2]$ is $(q-1)$-degenerate. Catlin and Lai, have proven that $H$ has a $(V_1,V_2)$-decomposition so thst $H[V_1]$ is a maximum acyclic set and $omega(H[V_2]),Delta(H[V_2])leqDelta-2(Delta(H)geq5)$. For a graph $G$, when $P_i$ is the property of not containing a subgraph isomorphic to $G$. Now suppose that $H$ is a connected graph with maximum degree $Delta(H)geq5,(wherek=2)$, and $Delta(H)geq9,(wherekgeq3)$, $omega(H)leqDelta(H)-1$, and $H$ is a $K_{Delta(H)}setminuse$-free graph. Assume that $p_{1}geq{p}_{2}geqcdotsgeq{p}_{k}geq3$ are $k$ positive integers, such that $su{m}_{i=1}^k{p}_i=Delta(H)-1+k$. For each $iin[k-1]$, set $G_i$ as a collection of graphs with minimum degree at least $p_i-1$. Then there exists a $(V_1,V_2,ldots,V_k)$-decomposition of $V(H)$, such that $H[V_1]$ is $G_1$-free, $V_1$ has the maximum possible size, $H[V_i]$ is $G_i$-free for each $2leqileqk-1$ and $Delta(H[V_k])leq{p}_k$, and either $H[V_k]$ is $K_{p_k}$-free or its $p_k$-cliques are disjoint.

This page was built for publication: Vertex Partitions and Maximum $\G$-free Subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6404627)