Journal Details
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Open Access

Vertex Partitioning of Graphs Into Odd Induced Subgraphs

Accepted: 12 Oct 2020
Journal Details
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English

A graph G is called an odd (even) graph if for every vertex vV (G), dG(v) is odd (even). Let G be a graph of even order. Scott in 1992 proved that the vertices of every connected graph of even order can be partitioned into some odd induced forests. We denote the minimum number of odd induced subgraphs which partition V (G) by od(G). If all of the subgraphs are forests, then we denote it by odF (G). In this paper, we show that if G is a connected subcubic graph of even order or G is a connected planar graph of even order, then odF (G) ≤ 4. Moreover, we show that for every tree T of even order odF (T) ≤ 2 and for every unicyclic graph G of even order odF (G) ≤ 3. Also, we prove that if G is claw-free, then V (G) can be partitioned into at most Δ (G) − 1 induced forests and possibly one independent set. Furthermore, we demonstrate that the vertex set of the line graph of a tree can be partitioned into at most two odd induced subgraphs and possibly one independent set.

MSC 2010

[1] J. Akiyama, G. Exoo and F. Harary, Covering and packing in graphs. III. Cyclic and acyclic invariants, Math. Slovaca 30 (1980) 405–417.Search in Google Scholar

[2] N. Alon, The linear arboricity of graphs, Israel J. Math. 62 (1988) 311–325. doi:10.1007/BF0278330010.1007/BF02783300Search in Google Scholar

[3] K. Appel and W. Haken, Every planar map is four colorable. Part I: Discharging, Illinois J. Math. 21 (1977) 429–490. doi:10.1215/ijm/125604901110.1215/ijm/1256049011Search in Google Scholar

[4] L. Cowen, W. Goddard and C.E. Jesurum, Defective coloring revisited, J. Graph Theory 24 (1997) 205–219. doi:10.1002/(SICI)1097-0118(199703)24:3〈205::AID-JGT2〉 3.0.CO;2-TSearch in Google Scholar

[5] G. Gutin, Note on perfect forests, J. Graph Theory 82 (2016) 233–235. doi:10.1002/jgt.2189710.1002/jgt.21897Search in Google Scholar

[6] M.A. Henning, F. Joos, C. Löwenstein and T. Sasse, Induced cycles in graphs, Graphs Combin. 32 (2016) 2425–2441. doi:10.1007/s00373-016-1713-z10.1007/s00373-016-1713-zSearch in Google Scholar

[7] L. Lovász, Combinatorial Problems and Exercises (North-Holland, Amsterdam, 1979).Search in Google Scholar

[8] L. Lovász, On decomposition of graphs, Studia Sci. Math. Hungar. 1 (1966) 237–238.Search in Google Scholar

[9] J. Petersen, Die Theorie der regulären graphs, Acta Math. 15 (1891) 193–220. doi:10.1007/BF0239260610.1007/BF02392606Search in Google Scholar

[10] A.D. Scott, Large induced subgraphs with all degrees odd, Combin. Probab. Comput. 1 (1992) 335–349. doi:10.1017/S096354830000038910.1017/S0963548300000389Search in Google Scholar

[11] A.D. Scott, On induced subgraphs with all degrees odd, Graphs Combin. 17 (2001) 539–553. doi:10.1007/s00373017002810.1007/s003730170028Search in Google Scholar

[12] C. Thomassen, Kuratowski’s theorem, J. Graph Theory 5 (1981) 225–241. doi:10.1002/jgt.319005030410.1002/jgt.3190050304Search in Google Scholar

[13] D. West, Introduction to Graph Theory, Second Edition (Prentice Hall, 2001) 197–199, 208–209.Search in Google Scholar

• A Note About Monochromatic Components in Graphs of Large Minimum Degree

Recommended articles from Trend MD