Article in volume
Authors:
Title:
Vertex partitioning of graphs into odd induced subgraphs
PDFSource:
Discussiones Mathematicae Graph Theory 43(2) (2023) 385-399
Received: 2020-01-06 , Revised: 2020-10-12 , Accepted: 2020-10-12 , Available online: 2020-11-03 , https://doi.org/10.7151/dmgt.2371
Abstract:
A graph $G$ is called an odd (even) graph if for every vertex $v\in 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)\le 4$. Moreover, we show that for every tree $T$
of even order $od_F(T)\le 2$ and for every unicyclic graph $G$ of even order
$od_F(G)\le 3$. Also, we prove that if $G$ is claw-free, then $V(G)$ can be
partitioned into at most $\Delta(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
References:
- J. Akiyama, G. Exoo and F. Harary, Covering and packing in graphs. III. Cyclic and acyclic invariants, Math. Slovaca 30 (1980) 405–417.
- N. Alon, The linear arboricity of graphs, Israel J. Math. 62 (1988) 311–325.
https://doi.org/10.1007/BF02783300 - 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 - 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:3<205::AID-JGT2>3.0.CO;2-T - G. Gutin, Note on perfect forests, J. Graph Theory 82 (2016) 233–235.
https://doi.org/10.1002/jgt.21897 - 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 - L. Lovász, Combinatorial Problems and Exercises (North-Holland, Amsterdam, 1979).
- L. Lovász, On decomposition of graphs, Studia Sci. Math. Hungar. 1 (1966) 237–238.
- J. Petersen, Die Theorie der regulären graphs, Acta Math. 15 (1891) 193–220.
https://doi.org/10.1007/BF02392606 - A.D. Scott, Large induced subgraphs with all degrees odd, Combin. Probab. Comput. 1 (1992) 335–349.
https://doi.org/10.1017/S0963548300000389 - A.D. Scott, On induced subgraphs with all degrees odd, Graphs Combin. 17 (2001) 539–553.
https://doi.org/10.1007/s003730170028 - C. Thomassen, Kuratowski's theorem, J. Graph Theory 5 (1981) 225–241.
https://doi.org/10.1002/jgt.3190050304 - D. West, Introduction to Graph Theory, Second Edition, 197–199, 208–209 (Prentice Hall, 2001).
Close