论文标题
具有规定程度或连接性能的低色素跨度子（DI）图
Low chromatic spanning sub(di)graphs with prescribed degree or connectivity properties
论文作者
论文摘要
概括了Erdős和Lovász的概括，我们表明每个图$ g $都包含一个$ k $ -partite $ h $，带有$λ（h）\ geq \ lceil {} \ frac {} \ frac {k-1} {k-1} {k} {k}λ（g）\ rceil $，$ ucceil $，$ us $λ（$λ$）$ cy是$ g的gon。特别是，由于纳什·威廉姆斯（Nash-Williams）和塔特（Tutte），这意味着每一个$ 7 $ - 边缘连接的图都包含一个跨越的二分组图，其边缘集将其分解为两个边缘 - 界定跨越树。我们表明，这是最好的，因为它不适合许多$ 6 $连接的图形。 对于有向图，[6]中显示没有$ k $，因此每个$ k $ arc-arc连接的Digraph具有一个跨越强的二分子子数字。我们证明，每个强大的挖掘物都有一个跨越强的三方子区域，并且在至少6个顶点上的每个强烈半完整的挖掘物都包含一个跨越强的二分子子数字。 \ jbj {我们通过证明每个正整数$ k $，每个$ k $ - arc-arcnectectigraph都包含一个跨度$（2k+1 $） - partite subdiite subdipe of $ k $ - $ -K $ -2.ARC连接，这是与之相关的，这是最好的，\ jbj {我们将此结果推广到更高的连接率。 [18]中的一个猜想意味着，最低级别$ 2K-1 $的每个挖掘都包含一个跨度$ 3 $ - 分段子插图，最低级别至少$ k $。我们证明，通过提供最低限度的$ 2K-2 $的无限类别的挖掘$ 2K-2 $，这将是最好的2k-1 $。 我们还证明，最低半学位的每个挖掘都至少$ 3R $包含一个跨度$ 6 $ - 分段子数字，每个顶点每个顶点都具有至少$ r $ $ $。
Generalizing well-known results of Erdős and Lovász, we show that every graph $G$ contains a spanning $k$-partite subgraph $H$ with $λ(H)\geq \lceil{}\frac{k-1}{k}λ(G)\rceil$, where $λ(G)$ is the edge-connectivity of $G$. In particular, together with a well-known result due to Nash-Williams and Tutte, this implies that every $7$-edge-connected graphs contains a spanning bipartite graph whose edge set decomposes into two edge-disjoint spanning trees. We show that this is best possible as it does not hold for infintely many $6$-edge-connected graphs. For directed graphs, it was shown in [6] that there is no $k$ such that every $k$-arc-connected digraph has a spanning strong bipartite subdigraph. We prove that every strong digraph has a spanning strong 3-partite subdigraph and that every strong semicomplete digraph on at least 6 vertices contains a spanning strong bipartite subdigraph. \jbj{We generalize this result to higher connectivities by proving} that, for every positive integer $k$, every $k$-arc-connected digraph contains a spanning $(2k+1$)-partite subdigraph which is $k$-arc-connected and this is best possible. A conjecture in [18] implies that every digraph of minimum out-degree $2k-1$ contains a spanning $3$-partite subdigraph with minimum out-degree at least $k$. We prove that the bound $2k-1$ would be best possible by providing an infinite class of digraphs with minimum out-degree $2k-2$ which do not contain any spanning $3$-partite subdigraph in which all out-degrees are at least $k$. We also prove that every digraph of minimum semi-degree at least $3r$ contains a spanning $6$-partite subdigraph in which every vertex has in- and out-degree at least $r$.
