×

zbMATH — the first resource for mathematics

Odd decompositions and coverings of graphs. (English) Zbl 1458.05217
Summary: A (finite) graph is odd if all its vertices have odd degrees. The principal aim of this survey is to present the current state of research on covers and decompositions of graphs into fewest possible number of odd subgraphs. Given a graph \(G\), the parameters \(\chi_o^\prime(G)\) and \(\operatorname{cov}_o(G)\) denote, respectively, the minimum size of a decomposition and cover of \(G\) consisting of odd subgraphs. L. Pyber [in: Sets, graphs and numbers. A birthday salute to Vera T. Sós and András Hajnal. Amsterdam: North-Holland Publishing Company. 583–610 (1992; Zbl 0792.05110)] and T. Mátrai [J. Graph Theory 53, No. 1, 77–82 (2006; Zbl 1098.05067)], respectively, have shown that for every simple graph \(G\) it holds that \(\chi_o^\prime(G)\leq 4\) and \(\operatorname{cov}_o(G)\leq 3\), with both bounds being sharp. The multigraph analogues of the same inequalities, given by the present authors in [ J. Graph Theory 92, No. 3, 304–321 (2019; Zbl 1429.05169); Adv. Math., Sci. J. 8, No. 2, 63–68 (2019; Zbl 1431.05124)], respectively, are discussed in detail. The list versions of the graph parameters \(\chi_o^\prime(G)\) and \(\operatorname{cov}_o (G)\), along with other generalizations and possible new directions of related research, are considered in the latter part of the article. Throughout we also pose various structural and algorithmic questions and problems.
MSC:
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Atanasov, R.; Petruševski, M.; Škrekovski, R., Odd edge-colorability of subcubic graphs, Ars Math. Contemp., 10, 359-370 (2016) · Zbl 1347.05057
[2] Bondy, J. A.; Murty, U. S.R., (Graph Theory. Graph Theory, Graduate Texts in Mathematics, vol. 244 (2008), Springer: Springer New York) · Zbl 1134.05001
[3] Chartrand, G.; Zhang, P., Chromatic Graph Theory (2009), Chapman & Hall, CRC Press · Zbl 1169.05001
[4] Diestel, R., (Graph Theory. Graph Theory, Graduate Texts in Mathematics, vol. 173 (2010), Springer: Springer Berlin)
[5] Edmonds, J. R., Minimum partition of a matroid into independent sets, J. Res. Nat. Bur. Stand. B, 69B, 67-72 (1965) · Zbl 0192.09101
[6] F. Jaeger, On nowhere-zero flows in multigraphs, in: Proceedings of the Fifth British Combinatorial Conference, 1975, pp. 373-378.
[7] Jaeger, F., Flows and generalized coloring theorems in graphs, J. Combin. Theory Ser. B, 26, 205-216 (1979) · Zbl 0422.05028
[8] Kano, M.; Katona, G. Y.; Varga, K., Decomposition of a graph into two disjoint odd subgraphs, Graphs Combin., 34, 6, 1581-1588 (2018) · Zbl 1402.05175
[9] Lužar, B.; Petruševski, M.; Škrekovski, R., Odd edge coloring of graphs, Ars Math. Contemp., 9, 277-287 (2015) · Zbl 1329.05115
[10] Mátrai, T., Covering the edges of a graph by three odd subgraphs, J. Graph Theory, 53, 75-82 (2006) · Zbl 1098.05067
[11] Matthews, K. R., On the eulericity of a graph, J. Graph Theory, 2, 143-148 (1978) · Zbl 0407.05062
[12] M. Petruševski, Graph Colorings and Homomorphisms (Phd. Thesis), in macedonian, 2015.
[13] Petruševski, M., Odd \(4\)-edge-colorability of graphs, J. Graph Theory, 87, 4, 460-474 (2018) · Zbl 1386.05063
[14] Petruševski, M.; Škrekovski, R., Coverability of graph by three odd subgraphs, J. Graph Theory, 92, 3, 304-321 (2019) · Zbl 1429.05169
[15] Petruševski, M.; Škrekovski, R., Decomposing a graph into two subgraphs with prescribed parities of vertex degrees, Adv. Math. Sci. J., 8, 2, 63-68 (2019) · Zbl 1431.05124
[16] Pyber, L., Covering the edges of a graph by. sets, graphs and numbers, Colloquia Math. Soc. János Bolyai, 60, 583-610 (1991) · Zbl 0792.05110
[17] Tutte, W. T., A contribution to the theory of chromatic polynomials, Canad. J. Math., 6, 80-91 (1954) · Zbl 0055.17101
[18] Tutte, W. T., A class of Abelian groups, Canad. J. Math., 8, 13-28 (1956) · Zbl 0070.02302
[19] Zhang, C. Q., (Integer Flows and Cycle Covers of Graphs. Integer Flows and Cycle Covers of Graphs, Monographs and Textbooks in Pure and Applied Mathematics, vol. 205 (1997), Marcel Dekker Inc.) · Zbl 0866.05001
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.