×

Factors with red-blue coloring of claw-free graphs and cubic graphs. (English) Zbl 1529.05129

A valid colouring of a graph \(G\) is any \(2\)-vertex colouring of \(G\) in, say, red and blue, such that the number of vertices coloured red is even (excluding zero). The authors prove that any valid colouring of a connected claw-free graph admits a system of vertex-disjoint paths whose end vertices coincide with the red vertices. If the graph is \(3\)-edge-connected, claw-free and cubic, then the authors prove that such a system of paths gives rise to a factor where each red vertex has degree one and every blue vertex has degree two, provided that the valid colouring has the added property of having any pair of red vertices being at a distance of at least three.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C75 Structural characterization of families of graphs
Full Text: DOI

References:

[1] Akiyama, J., Kano, M.: Factors and factorizations of graphs. In: LNM 2031. Springer, New York (2011) · Zbl 1229.05001
[2] Egawa, Y.; Kano, M., Sufficient conditions for graphs to have \((g, f)\)-factors, Discrete Math., 151, 87-90 (1996) · Zbl 0853.05061 · doi:10.1016/0012-365X(94)00085-W
[3] Kaiser, T., Disjoint T-paths in tough graphs, J. Graph Theory, 59, 1-10 (2008) · Zbl 1165.05015 · doi:10.1002/jgt.20316
[4] Lu, H.; Kano, M., Characterization of 1-tough graphs using factors, Discrete Math., 343, 111901 (2020) · Zbl 1441.05114 · doi:10.1016/j.disc.2020.111901
[5] Lovász, L., The factorization of graphs II, Acta Mat. Hungary, 23, 223-246 (1972) · Zbl 0247.05155 · doi:10.1007/BF01889919
[6] Petersen, J., Die Theorie der regulären graphs, Acta Math., 15, 193-220 (1891) · JFM 23.0115.03 · doi:10.1007/BF02392606
[7] Sumner, DP, Graphs with 1-factors, Proc. Am. Math., 42, 8-12 (1974) · Zbl 0293.05157 · doi:10.1090/S0002-9939-1974-0323648-6
[8] Thomassen, C., A remark on the factor theorems of Lovász and Tutte, J. Graph Theory, 5, 441-442 (1981) · Zbl 0465.05055 · doi:10.1002/jgt.3190050415
[9] Tutte, WT, The subgraph problem, Ann. Discrete Math., 3, 289-295 (1978) · Zbl 0377.05034 · doi:10.1016/S0167-5060(08)70514-4
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.