Search

In this paper, we consider the decomposition of multigraphs under minimum degree constraints and give a unified generalization of several results by various researchers. Let $G$ be a multigraph in which no quadrilaterals share edges with triangles and other quadrilaterals and let $\mu_G(v)=\max\{\mu_G(u,v):u\in V(G)\setminus\{v\}\}$, where $\mu_G(u,v)$ is the number of edges joining $u$ and $v$ in $G$. We show that for any two functions $a,b:V(G)\rightarrow\mathbb{N}\setminus\{0,1\}$, if $d_G(v)\ge a(v)+b(v)+2\mu_G(v)-3$ for each $v\in V(G)$, then there is a partition $(X,Y)$ of $V(G)$ such that $d_X(x)\geq a(x)$ for each $x\in X$ and $d_Y(y)\geq b(y)$ for each $y\in Y$. This extends the related results due to Diwan [3], Liu and Xu [7] and Ma and Yang [10] on simple graphs to the multigraph setting.

For a graph $G$, let $f(G)$ denote the maximum number of edges in a bipartite subgraph of $G$. Given a fixed graph $H$ and a positive integer $m$, let $f(m,H)$ denote the minimum possible cardinality of $f(G)$, as $G$ ranges over all graphs on $m$ edges that contain no copy of $H$. Alon et al. [‘Maximum cuts and judicious partitions in graphs without short cycles’, J. Combin. Theory Ser. B 88 (2003), 329–346] conjectured that, for any fixed graph $H$, there exists an $\unicode[STIX]{x1D716}(H)>0$ such that $f(m,H)\geq m/2+\unicode[STIX]{x1D6FA}(m^{3/4+\unicode[STIX]{x1D716}})$. We show that, for any wheel graph $W_{2k}$ of $2k$ spokes, there exists $c(k)>0$ such that $f(m,W_{2k})\geq m/2+c(k)m^{(2k-1)/(3k-1)}\log m$. In particular, we confirm the conjecture asymptotically for $W_{4}$ and give general lower bounds for $W_{2k+1}$.

Let $r\ge 3$ and $k\ge 2$ be fixed integers. Bollobas and Scott conjectured that every $r$-uniform hypergraph with $m$ edges has a vertex partition into $k$ sets with at most $m/k^r+o(m)$ edges in ...

Let G be a weighted hypergraph with edges of size at most 2. Bollobas and Scott conjectured that G admits a bipartition such that each vertex class meets edges of total weight at least (w1−Δ1)/2+2w2/3, where wi is the total weight of edges of size i and Δ1 is the maximum weight of an edge of size 1. In this paper, for positive integer weighted hypergraph G (i.e., multi-hypergraph), we show that there exists a bipartition of G such that each vertex class meets edges of total weight at least (w0−1)/6+(w1−Δ1)/3+2w2/3, where w0 is the number of edges of size 1. This generalizes a result of Haslegrave. Based on this result, we show that every graph with m edges, except for K2 and K1,3, admits a tripartition such that each vertex class meets at least [2m/5] edges, which establishes a special case of a more general conjecture of Bollobas and Scott.

For a graph $G$, let $f(G)$ denote the maximum number of edges in a bipartite subgraph of $G$. For an integer $m$ and for a fixed graph $H$, let $f(m,H)$ denote the minimum possible cardinality of $f(G)$ as $G$ ranges over all graphs on $m$ edges that contain no copy of $H$. We give a general lower bound for $f(m,H)$ which extends a result of Erdős and Lovász and we study this function for any bipartite graph $H$ with maximum degree at most $t\geq 2$ on one side.

For positive integers k≥2 and m, let gk(m) be the smallest integer such that for each graph G with m edges there exists a k-partition V(G)=V1∪…∪Vk in which each Vi contains at most gk(m) edges. Bollobas and Scott showed that gk(m)≤mk2+k−12k22m+1/4−1/2. Ma and Yu posed the following problem: is it true that the limsup of mk2+k−12k22m−gk(m) tends to infinity as m tends to infinity? They showed it holds when k is even, establishing a conjecture of Bollobas and Scott. In this article, we solve the problem completely. We also present a result by showing that every graph with a large k-cut has a k-partition in which each vertex class contains relatively few edges, which partly improves a result given by Bollobas and Scott.

Judicious partitioning problems on graphs and hypergraphs ask for partitions that optimize several quantities simultaneously. Let k ≥ 2 be an integer and let G be a hypergraph with mi edges of size i for i=1,2. Bollobás and Scott conjectured that G has a partition into k classes, each of which contains at most $m_1/k+m_2/k^2+O(\sqrt{m_1+m_2})$ edges. In this paper, we confirm the conjecture affirmatively by showing that G has a partition into k classes, each of which contains at most $$m_1/k+m_2/k^2+\ffrac{k-1}{2k^2}\sqrt{2(km_1+m_2)}+O(1)$$. edges. This bound is tight up to O(1).

Za graf ?$G$?, naj ?$f(G)$? označuje maksimalno število povezav v dvodelnem podgrafu grafa ?$G$?. Za celo število ?$m \ge 1$? in za množico ?$\mathcal{H}$? grafov, naj ?$f(m, \mathcal{H})$? označuje minimalno možno kardinalnost ?$f(G)$?, ko ?$G$? preteče vse grafe z ?$m$? povezavami, ki ne vsebujejo nobenega člana množice ?$\mathcal{H}$? kot podgrafa. Še posebej, za dani graf ?$H$?, enostavno pišemo ?$f(m, H)$?, za ?$f(m, \mathcal{H})$?, ko je ?$\mathcal{H} = \{H\}$?. Naj bo ?$r > 4$? fiksno sodo celo število. Alon in drugi (2003) so postavili domnevo, da obstaja pozitivna konstanta ?$c(r)$?, za katero je ?$f(m, C_{r-1}) \ge m/2 + c(r)m^{r/(r+1)}$? za vse ?$m$?. V tem članku pokažemo, da je ?$f(m, C_{r-1}) \ge m/2 + c(r)(m^r \log^4 m)^{1/(r+2)}$? za neko pozitivno konstanto ?$c(r)$? in za vse ?$m$?. Za poljubno določeno celo število ?$s \ge 2$? študiramo tudi funkcijo ?$f(m, \mathcal{H})$? za ?$\mathcal{H} = \{K_{2,s}, C_5\}$? in ?$\mathcal{H} = \{C_4, C_5,\dots , C_{r-1}\}$?, kar oboje izboljšuje rezultat Alona in drugih.

Judicious Partition Problem is to partition the vertex set of a graph such that certain quantities are optimized simultaneously. Let k be a positive integer and G a graph with m edges. It is proved in this paper that the vertex set of G can be partitioned into k parts V 1 , ? , V k such that e ( V i ) ? m k 2 + k - 1 2 k 2 ( 2 m + 1 4 - 1 2 ) + 2 3 for each i ? { 1 , 2 , ? , k } and e ( V 1 , ? , V k ) ? k - 1 k m + k - 1 2 k ( 2 m + 1 4 - 1 2 ) - ( k - 2 ) 2 8 k , where e ( V i ) is the number of edges with both ends in V i and e ( V 1 , ? , V k ) = m - ? i = 1 k e ( V i ) . This partially solves a problem proposed by Bollobas and Scott, and, for some values of m , solves the problem affirmatively.