Geodesic
Vertex partitioning of graphs into odd induced subgraphs
Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 2, pp. 385-399 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

A graph G is called an odd (even) graph if for every vertex v∈ V(G), d_G(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 od_F(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 od_F(G)≤ 4. Moreover, we show that for every tree T of even order od_F(T)≤ 2 and for every unicyclic graph G of even order od_F(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.
Keywords: odd induced subgraph, subcubic graphs, claw-free graphs, line graphs, independent set 
@article{DMGT_2023_43_2_a4,
     author = {Aashtab, Arman and Akbari, Saieed and Ghanbari, Maryam and Shidani, Amitis},
     title = {Vertex partitioning of graphs into odd induced subgraphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {385--399},
     year = {2023},
     volume = {43},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a4/}
}
TY  - JOUR
AU  - Aashtab, Arman
AU  - Akbari, Saieed
AU  - Ghanbari, Maryam
AU  - Shidani, Amitis
TI  - Vertex partitioning of graphs into odd induced subgraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2023
SP  - 385
EP  - 399
VL  - 43
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a4/
LA  - en
ID  - DMGT_2023_43_2_a4
ER  - 
%0 Journal Article
%A Aashtab, Arman
%A Akbari, Saieed
%A Ghanbari, Maryam
%A Shidani, Amitis
%T Vertex partitioning of graphs into odd induced subgraphs
%J Discussiones Mathematicae. Graph Theory
%D 2023
%P 385-399
%V 43
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a4/
%G en
%F DMGT_2023_43_2_a4
Aashtab, Arman; Akbari, Saieed; Ghanbari, Maryam; Shidani, Amitis. Vertex partitioning of graphs into odd induced subgraphs. Discussiones Mathematicae. Graph Theory, Tome 43 (2023) no. 2, pp. 385-399. http://geodesic.mathdoc.fr/item/DMGT_2023_43_2_a4/

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

[2] N. Alon, The linear arboricity of graphs, Israel J. Math. 62 (1988) 311–325. https://doi.org/10.1007/BF02783300

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

[4] L. Cowen, W. Goddard and C.E. Jesurum, Defective coloring revisited, J. Graph Theory 24 (1997) 205–219. https://doi.org/10.1002/(SICI)1097-0118(199703)24:33.0.CO;2-T

[5] G. Gutin, Note on perfect forests, J. Graph Theory 82 (2016) 233–235. https://doi.org/10.1002/jgt.21897

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

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

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

[9] J. Petersen, Die Theorie der regulären graphs, Acta Math. 15 (1891) 193–220. https://doi.org/10.1007/BF02392606

[10] A.D. Scott, Large induced subgraphs with all degrees odd, Combin. Probab. Comput. 1 (1992) 335–349. https://doi.org/10.1017/S0963548300000389

[11] A.D. Scott, On induced subgraphs with all degrees odd, Graphs Combin. 17 (2001) 539–553. https://doi.org/10.1007/s003730170028

[12] C. Thomassen, Kuratowski's theorem, J. Graph Theory 5 (1981) 225–241. https://doi.org/10.1002/jgt.3190050304

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