|
图的强均匀点荫度
|
Abstract:
图G的均匀k-划分是将图G的顶点划分,使得每个划分类导出的子图是一个森林且任意两个划分类中的顶点数最多相差1。图G的强均匀点荫度是最小整数k,使得对任意的
,图G都有一个均匀
-划分。本文证明每个无割点的外平面图G,它的强均匀点荫度至多为,继而证明了无割点的外平面图满足猜想:对任何平面图G,强均匀点荫度至多是。同时,得到平方图的强均匀点荫度的下界为
,证明圈
的平方图在
时,强均匀点荫度为3,当
时,强均匀点荫度为2,从而证明圈的平方图满足强均匀点荫的猜想。
An equitable k-partition of a graph G is a partition of the vertex set of G such that the subgraph induced by each partition class is a forest and the sizes of any two parts differ by at most one. The strong equitable vertex arboricity of G is the minimum integer k so that G has an equitably
- partitioned for an
. This paper proves that the strong equitable vertex arboricity of each outerplanar has no cut-vertices G is at most 2, and then proves that the outerplanar satisfies the conjecture that for any plan G, the strong equitable vertex arboricity is at most 3. Meanwhile, the lower bound of the strong equitable vertex arboricity of the square graph is
, which proved that the square graph of the circuits
[1] | Bondy, J.A. and Murty, U.S.R. (2008) Graph Theory. Springer. |
[2] | Wu, J.L., Zhang, X. and Li, H.L. (2013) Equitable Vertex Arboricity of Graphs. Discrete Mathematics, 313, 2696-2701. https://doi.org/10.1016/j.disc.2013.08.006 |
[3] | Fan, H., Kierstead, H.A., Liu, G., Molla, T., Wu, J. and Zhang, X. (2011) A Note on Relaxed Equitable Coloring of Graphs. Information Processing Letters, 111, 1062-1066. https://doi.org/10.1016/j.ipl.2011.08.001 |
[4] | Zhang, X. and Wu, J. (2014) A Conjecture on Equitable Vertex Arboricity of Graphs. Filomat, 28, 217-219. https://doi.org/10.2298/fil1401217z |
[5] | Zhang, X. (2016) Equitable Vertex Arboricity of Subcubic Graphs. Discrete Mathematics, 339, 1724-1726. https://doi.org/10.1016/j.disc.2016.02.003 |
[6] | Chen, G., Gao, Y., Shan, S., Wang, G. and Wu, J. (2016) Equitable Vertex Arboricity of 5-Degenerate Graphs. Journal of Combinatorial Optimization, 34, 426-432. https://doi.org/10.1007/s10878-016-9997-8 |
[7] | Zhang, X., Niu, B., Li, Y. and Li, B. (2021) Equitable Vertex Arboricity Conjecture Holds for Graphs with Low Degeneracy. Acta Mathematica Sinica, English Series, 37, 1293-1302. https://doi.org/10.1007/s10114-021-0663-4 |
[8] | Esperet, L., Lemoine, L. and Maffray, F. (2015) Equitable Partition of Graphs into Induced Forests. Discrete Mathematics, 338, 1481-1483. https://doi.org/10.1016/j.disc.2015.03.019 |
[9] | Borodin, O.V. (1979) On Acyclic Colorings of Planar Graphs. Discrete Mathematics, 25, 211-236. https://doi.org/10.1016/0012-365x(79)90077-3 |
[10] | Chartrand, G. and Kronk, H.V. (1969) The Point-Arboricity of Planar Graphs. Journal of the London Mathematical Society, 1, 612-616. https://doi.org/10.1112/jlms/s1-44.1.612 |
[11] | 刘维婵, 张欣. 外1-平面图的均匀点荫度[J]. 计算机工程与应用, 2018, 54(10): 51-53+80. |
[12] | Zhang, X. (2015) Equitable Vertex Arboricity of Planar Graphs. Taiwanese Journal of Mathematics, 19, 123-131. https://doi.org/10.11650/tjm.19.2015.4422 |
[13] | 吴建良. 外平面图的完备染色[J]. 山东矿业学院学报, 1996(2): 219-222. |