×

A note on partitions of graphs under degree constraints. (English) Zbl 1442.05181

Summary: In this paper, we consider the partitions of graphs under minimum degree constraints and answer the following question of M. Liu and B. Xu [ibid. 226, 87–93 (2017; Zbl 1365.05232)] in negative: Let \(G\) be a triangle-free graph without \(K_{2 , 3}\), and let \(a , b : V ( G ) \to \mathbb{N} \setminus \{ 0 , 1 \}\) be two functions such that \(d_G ( x ) \geq a ( x ) + b ( x ) - 1\) for each \(x \in V ( G )\), does \(G\) admit 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\)?

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C07 Vertex degrees

Citations:

Zbl 1365.05232
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ban, A., Decomposing weighted graphs, J. Graph Theory, 86, 250-254 (2017) · Zbl 1370.05164
[2] Ban, A.; Linial, N., Internal partitions of regular graphs, J. Graph Theory, 83, 5-18 (2016) · Zbl 1346.05223
[3] Bazgan, C.; Tuza, Zs.; Vanderpooten, D., Efficient algorithms for decomposing graphs under degree constraints, Discrete Appl. Math., 155, 979-988 (2007) · Zbl 1131.05068
[4] Diwan, A., Decomposing graphs with girth at least five under degree constraints, J. Graph Theory, 33, 237-239 (2000) · Zbl 0942.05055
[5] Fujita, S.; Li, R.; Wang, G., Decomposing edge-coloured graphs under colour degree constraints, Combin. Probab. Comput., 28, 755-767 (2019) · Zbl 1436.05037
[6] Hou, J.; Ma, H.; Yu, J.; Zhang, X., On partitions of \(K_{2 , 3}\)-free graphs under degree constraints, Discrete Math., 341, 3288-3295 (2018) · Zbl 1397.05140
[7] Kaneko, A., On decomposition of triangle-free graphs under degree constraints, J. Graph Theory, 27, 7-9 (1998) · Zbl 0892.05040
[8] Liu, M.; Xu, B., On partitions of graphs under degree constraints, Discrete Appl. Math., 226, 87-93 (2017) · Zbl 1365.05232
[9] Lovász, L., On decomposition of graphs, Studia Sci. Math. Hungar., 1, 237-238 (1966) · Zbl 0151.33401
[10] Ma, J.; Yang, T., Decomposing \(C_4\)-free graphs under degree constraints, J. Graph Theory, 90, 13-23 (2019) · Zbl 1414.05239
[11] Schweser, T.; Stiebitz, M., Partitions of multigraphs under minimum degree constraints, Discrete Appl. Math., 257, 269-275 (2019) · Zbl 1406.05082
[12] Sheehan, J., Graph decomposition with constraints on the minimum degree, Discrete Math., 68, 299-307 (1988) · Zbl 0644.05030
[13] Song, J.; Xu, B., Partitions of graphs and multigraphs under degree constraints, Discrete Appl. Math. (2019)
[14] Stiebitz, M., Decomposing graphs under degree constraints, J. Graph Theory, 23, 321-324 (1996) · Zbl 0865.05058
[15] Thomassen, C., Graph decomposition with constraints on the connectivity and minimum degree, J. Graph Theory, 7, 165-167 (1983) · Zbl 0515.05045
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.