错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On partitions of theta-free multigraphs under degree constraints

  • Zijian Deng,
  • Caibing Chang,
  • Yan Liu

摘要

Let G be a graph which may have multiple edges but no loops, \(\mu _{G}(v)\) μ G ( v ) be the multiplicity of G (which is the maximum among the numbers of edges between v and the other vertex on G), and a and b be any two functions, s.t. \(a,b: V(G)\rightarrow \mathbb {N} \backslash \{0,1\}\) a , b : V ( G ) N \ { 0 , 1 } . A theta is a graph made of three internally vertex-disjoint chordless paths \(P_{1}=x- \cdots -y\) P 1 = x - - y , \(P_{2}=x-\cdots -y\) P 2 = x - - y , \(P_{3}=x-\cdots -y\) P 3 = x - - y of length at least two and no edges exist between \(P_i\) P i and \(P_j\) P j ( \(i\ne j,i,j\in \{1,2,3\}\) i j , i , j { 1 , 2 , 3 } ) except the three edges incident to x and the three edges incident to y. For a partition (XY) of V(G), and any \(x\in X\) x X , \(y\in Y\) y Y , let \(d_X(x)\) d X ( x ) denote by the degree of x in G[X], and \(d_Y(y)\) d Y ( y ) be defined similarly. In this paper, we show that a graph G admits a partition (AB) such that \(d_{A}(x)\ge a(x)\) d A ( x ) a ( x ) for any \(x\in A\) x A and \(d_{B}(y) \ge b(y)\) d B ( y ) b ( y ) for any \(y\in B\) y B if G is \(\mathcal {H}\) H -free and \(d_{G}(v)\ge a + b + 2\mu _{G}(v)-3\) d G ( v ) a + b + 2 μ G ( v ) - 3 for any vertex \(v\in V(G)\) v V ( G ) , where for each member \(H \in \mathcal {H}\) H H , the underlying of H belongs to {triangle, wheel, theta}.