排序方式: 共有11条查询结果,搜索用时 31 毫秒
1.
D. Gonçalves 《Discrete Mathematics》2007,307(16):2112-2121
We solve a conjecture of Roditty, Shoham and Yuster [P.J. Cameron (Ed.), Problems from the 17th British Combinatorial Conference, Discrete Math., 231 (2001) 469-478; Y. Roditty, B. Shoham, R. Yuster, Monotone paths in edge-ordered sparse graphs, Discrete Math. 226 (2001) 411-417] on the caterpillar arboricity of planar graphs. We prove that for every planar graph G=(V,E), the edge set E can be partitioned into four subsets (Ei)1?i?4 in such a way that G[Ei], for 1?i?4, is a forest of caterpillars. We also provide a linear-time algorithm which constructs for a given planar graph G, four forests of caterpillars covering the edges of G. 相似文献
2.
1.IntroductionAlinearforestisaforestwhosecomponentsarepaths.Akiyama,E-coo,andHararyprovedthefollowingTheoremAll]andTheoremBIZ].TheoremA.Every3-regUlargraphGhasapartition(FI,F2)ofE(G)suchthatboth(V(G),FI)and(V(G),F2)arelinearforests.TheoremB.Every4reg... 相似文献
3.
徐保根 《高校应用数学学报(A辑)》2000,15(4):383-388
设a(G)表示图G的点荫度,m为正整数,H为连通图,混合Ramsey数v(a;m;H)被定义的为最小的正整数P,使得对任意P阶图G则有a(G)≥m或者H包括于G^-。本文给出了v(a;m;H)的一种计算方法,并对图Cn和轮Wn确定了v(a;n;Cn)和v(a;m;Wn)的值。 相似文献
4.
5.
6.
7.
8.
David R. Wood 《Journal of Combinatorial Theory, Series B》2004,90(2):309
An acyclic decomposition of a digraph is a partition of the edges into acyclic subgraphs. Trivially every digraph has an acyclic decomposition into two subgraphs. It is proved that for every integer s2 every digraph has an acyclic decomposition into s subgraphs such that in each subgraph the outdegree of each vertex v is at most
. For all digraphs this degree bound is optimal. 相似文献
9.
10.