The 3-Decomposition Conjecture for Star-Like Graphs

Decomposing Star-like Cubic Graphs Oliver Bachtler, Sven O. Krumke RPTU Kaiserslautern-Landau 27. SEG Workshop, 2023 Outline Basics 3-decompositions Existence for Hamiltonian graphs Constructing a Decomposition From the centre To the tips Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 1 / 18 3-Decompositions of Graphs Definition (Cubic Graphs) A graph is cubic if every vertex has degree 3. Definition (3-Decomposition) A3-decomposition of a connected cubic graph Gconsists of ▶a spanning tree T, ▶a set of cycles C, and ▶a matching M such that E(G)is the disjoint union E(T)∪E(C)∪M. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 2 / 18 3-Decompositions of Graphs Definition (Cubic Graphs) A graph is cubic if every vertex has degree 3. Definition (3-Decomposition) A3-decomposition of a connected cubic graph Gconsists of ▶a spanning tree T, ▶a set of cycles C, and ▶a matching M such that E(G)is the disjoint union E(T)∪E(C)∪M. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 2 / 18 3-Decompositions of Graphs Definition (Cubic Graphs) A graph is cubic if every vertex has degree 3. Definition (3-Decomposition) A3-decomposition of a connected cubic graph Gconsists of ▶a spanning tree T, ▶a set of cycles C, and ▶a matching M such that E(G)is the disjoint union E(T)∪E(C)∪M. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 2 / 18 An Example Graph ▶Given: connected cubic graph. ▶Take a spanning tree. ▶The remaining edges form cycles and paths. ▶Want paths of length 1. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 3 / 18 An Example Graph ▶Given: connected cubic graph. ▶Take a spanning tree. ▶The remaining edges form cycles and paths. ▶Want paths of length 1. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 3 / 18 An Example Graph ▶Given: connected cubic graph. ▶Take a spanning tree. ▶The remaining edges form cycles and paths. ▶Want paths of length 1. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 3 / 18 An Example Graph ▶Given: connected cubic graph. ▶Take a spanning tree. ▶The remaining edges form cycles and paths. ▶Want paths of length 1. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 3 / 18 Our Result Definition (Star-like Graphs) Let Gbe a connected cubic graph with a perfect matching M. ▶G−Mconsists of cycles. ▶Contracting these yields the contraction graph GM. Gis star-like if it has a perfect matching Msuch that GMis a star. Definition (3-Connectivity) A graph Gis 3-connected if removing 2 vertices does not disconnect it. Theorem (Main Result, 2022) Every 3-connected star-like graph has a 3-decomposition. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 5 / 18 Our Result Definition (Star-like Graphs) Let Gbe a connected cubic graph with a perfect matching M. ▶G−Mconsists of cycles. ▶Contracting these yields the contraction graph GM. Gis star-like if it has a perfect matching Msuch that GMis a star. Definition (3-Connectivity) A graph Gis 3-connected if removing 2 vertices does not disconnect it. Theorem (Main Result, 2022) Every 3-connected star-like graph has a 3-decomposition. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 5 / 18 Our Result Definition (Star-like Graphs) Let Gbe a connected cubic graph with a perfect matching M. ▶G−Mconsists of cycles. ▶Contracting these yields the contraction graph GM. Gis star-like if it has a perfect matching Msuch that GMis a star. Definition (3-Connectivity) A graph Gis 3-connected if removing 2 vertices does not disconnect it. Theorem (Main Result, 2022) Every 3-connected star-like graph has a 3-decomposition. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 5 / 18 Our Result Definition (Star-like Graphs) Let Gbe a connected cubic graph with a perfect matching M. ▶G−Mconsists of cycles. ▶Contracting these yields the contraction graph GM. Gis star-like if it has a perfect matching Msuch that GMis a star. Definition (3-Connectivity) A graph Gis 3-connected if removing 2 vertices does not disconnect it. Theorem (Main Result, 2022) Every 3-connected star-like graph has a 3-decomposition. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 5 / 18 Our Result Definition (Star-like Graphs) Let Gbe a connected cubic graph with a perfect matching M. ▶G−Mconsists of cycles. ▶Contracting these yields the contraction graph GM. Gis star-like if it has a perfect matching Msuch that GMis a star. Definition (3-Connectivity) A graph Gis 3-connected if removing 2 vertices does not disconnect it. Theorem (Main Result, 2022) Every 3-connected star-like graph has a 3-decomposition. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 5 / 18 Our Result Definition (Star-like Graphs) Let Gbe a connected cubic graph with a perfect matching M. ▶G−Mconsists of cycles. ▶Contracting these yields the contraction graph GM. Gis star-like if it has a perfect matching Msuch that GMis a star. Definition (3-Connectivity) A graph Gis 3-connected if removing 2 vertices does not disconnect it. Theorem (Main Result, 2022) Every 3-connected star-like graph has a 3-decomposition. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 5 / 18 Our Result Definition (Star-like Graphs) Let Gbe a connected cubic graph with a perfect matching M. ▶G−Mconsists of cycles. ▶Contracting these yields the contraction graph GM. Gis star-like if it has a perfect matching Msuch that GMis a star. Definition (3-Connectivity) A graph Gis 3-connected if removing 2 vertices does not disconnect it. Theorem (Main Result, 2022) Every 3-connected star-like graph has a 3-decomposition. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 5 / 18 Our Result Definition (Star-like Graphs) Let Gbe a connected cubic graph with a perfect matching M. ▶G−Mconsists of cycles. ▶Contracting these yields the contraction graph GM. Gis star-like if it has a perfect matching Msuch that GMis a star. Definition (3-Connectivity) A graph Gis 3-connected if removing 2 vertices does not disconnect it. Theorem (Xie, Zhou, Zhou, 2020) Every graph with a contraction graph on 3 vertices has a 3-decomposition. Theorem (Main Result, 2022) Every 3-connected star-like graph has a 3-decomposition. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 5 / 18 Our Result Definition (Star-like Graphs) Let Gbe a connected cubic graph with a perfect matching M. ▶G−Mconsists of cycles. ▶Contracting these yields the contraction graph GM. Gis star-like if it has a perfect matching Msuch that GMis a star. Definition (3-Connectivity) A graph Gis 3-connected if removing 2 vertices does not disconnect it. Theorem (Main Result, 2022) Every 3-connected star-like graph has a 3-decomposition. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 5 / 18 Hamiltonian Graphs have 3-Decompositions Theorem (Akbari, Jensen, Siggers) Every connected cubic Hamiltonian graph has a 3-decomposition. minimal cycle Call this the decomposition given by the minimal cycle. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 6 / 18 Hamiltonian Graphs have 3-Decompositions Theorem (Akbari, Jensen, Siggers) Every connected cubic Hamiltonian graph has a 3-decomposition. minimal cycle Call this the decomposition given by the minimal cycle. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 6 / 18 Hamiltonian Graphs have 3-Decompositions Theorem (Akbari, Jensen, Siggers) Every connected cubic Hamiltonian graph has a 3-decomposition. minimal cycle Call this the decomposition given by the minimal cycle. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 6 / 18 Hamiltonian Graphs have 3-Decompositions Theorem (Akbari, Jensen, Siggers) Every connected cubic Hamiltonian graph has a 3-decomposition. minimal cycle Call this the decomposition given by the minimal cycle. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 6 / 18 Hamiltonian Graphs have 3-Decompositions Theorem (Akbari, Jensen, Siggers) Every connected cubic Hamiltonian graph has a 3-decomposition. minimal cycle Call this the decomposition given by the minimal cycle. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 6 / 18 Hamiltonian Graphs have 3-Decompositions Theorem (Akbari, Jensen, Siggers) Every connected cubic Hamiltonian graph has a 3-decomposition. minimal cycle Call this the decomposition given by the minimal cycle. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 6 / 18 First Steps Theorem (Main Result) Every 3-connected star-like graph has a 3-decomposition. Assumption All cycles in G−Mhave chords in G. Observation There exists a minimal cycle avoiding any fixed boundary vertex. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 7 / 18 First Steps Theorem (Main Result) Every 3-connected star-like graph has a 3-decomposition. Assumption All cycles in G−Mhave chords in G. Observation There exists a minimal cycle avoiding any fixed boundary vertex. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 7 / 18 First Steps Theorem (Main Result) Every 3-connected star-like graph has a 3-decomposition. Assumption All cycles in G−Mhave chords in G. Observation There exists a minimal cycle avoiding any fixed boundary vertex. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 7 / 18 First Steps Theorem (Main Result) Every 3-connected star-like graph has a 3-decomposition. Assumption All cycles in G−Mhave chords in G. Observation There exists a minimal cycle avoiding any fixed boundary vertex. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 7 / 18 First Steps Theorem (Main Result) Every 3-connected star-like graph has a 3-decomposition. Assumption All cycles in G−Mhave chords in G. Observation There exists a minimal cycle avoiding any fixed boundary vertex. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 7 / 18 Decomposing the Centre ▶Take any minimal cycle C. ▶Check edges to tips. ▶At most 1 to each tip. ▶At least 2 to some tip. ▶Use decomposition ▶given by C. ▶using a part of C. ▶3 cases for the tips: ▶only black edges, ▶1 green edge, ▶2 red edges. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 8 / 18 Decomposing the Centre ▶Take any minimal cycle C. ▶Check edges to tips. ▶At most 1 to each tip. ▶At least 2 to some tip. ▶Use decomposition ▶given by C. ▶using a part of C. ▶3 cases for the tips: ▶only black edges, ▶1 green edge, ▶2 red edges. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 8 / 18 The Tips: Only Black Edges Take the decomposition given by a minimal cycle: Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 9 / 18 The Tips: Only Black Edges Take the decomposition given by a minimal cycle: Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 9 / 18 The Tips: Only Black Edges Take the decomposition given by a minimal cycle: Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 9 / 18 The Tips: Only Black Edges Take the decomposition given by a minimal cycle: Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 9 / 18 Decomposing the Centre ▶Take any minimal cycle C. ▶Check edges to tips. ▶At most 1 to each tip. ▶At least 2 to some tip. ▶Use decomposition ▶given by C. ▶using a part of C. ▶3 cases for the tips: ▶only black edges, ▶1 green edge, ▶2 red edges. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 10 / 18 Decomposing the Centre ▶Take any minimal cycle C. ▶Check edges to tips. ▶At most 1 to each tip. ▶At least 2 to some tip. ▶Use decomposition ▶given by C. ▶using a part of C. ▶3 cases for the tips: ▶only black edges, ▶1 green edge, ▶2 red edges. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 10 / 18 Decomposing the Centre ▶Take any minimal cycle C. ▶Check edges to tips. ▶At most 1 to each tip. ▶At least 2 to some tip. ▶Use decomposition ▶given by C. ▶using a part of C. ▶3 cases for the tips: ▶only black edges, ▶1 green edge, ▶2 red edges. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 10 / 18 The Tips: One Green Edge ▶Look for a useful minimal cycle. ▶If none exists ⇒All chords go from the left to the right path. ▶Both paths have the same length ⇒Levels. ▶Call a chord long if its ends are at least 2 levels apart. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 11 / 18 The Tips: One Green Edge Case 1: No long chord exists ▶Two form of chords: ▶direct ▶cross ▶Obtain a Hamiltonian path. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 12 / 18 The Tips: One Green Edge Case 1: No long chord exists ▶Two form of chords: ▶direct ▶cross ▶Obtain a Hamiltonian path. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 12 / 18 The Tips: One Green Edge Case 1: No long chord exists ▶Two form of chords: ▶direct ▶cross ▶Obtain a Hamiltonian path. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 12 / 18 The Tips: One Green Edge Case 1: No long chord exists ▶Two form of chords: ▶direct ▶cross ▶Obtain a Hamiltonian path. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 12 / 18 The Tips: One Green Edge Case 1: No long chord exists ▶Two form of chords: ▶direct ▶cross ▶Obtain a Hamiltonian path. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 12 / 18 The Tips: One Green Edge Case 1: No long chord exists ▶Two form of chords: ▶direct ▶cross ▶Obtain a Hamiltonian path. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 12 / 18 The Tips: One Green Edge Case 1: No long chord exists ▶Two form of chords: ▶direct ▶cross ▶Obtain a Hamiltonian path. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 12 / 18 The Tips: One Green Edge Case 1: No long chord exists ▶Two form of chords: ▶direct ▶cross ▶Obtain a Hamiltonian path. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 12 / 18 The Tips: One Green Edge Case 1: No long chord exists ▶Two form of chords: ▶direct ▶cross ▶Obtain a Hamiltonian path. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 12 / 18 The Tips: One Green Edge Case 2: A long chord exists ▶Take the first such chord. ▶Vertices before paired up. ▶Regard the other vertex on this level and its successor. ▶Neighbours below the chord. ▶Use a two-chord cycle. ▶Leaves a tree. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 13 / 18 Decomposing the Centre ▶Take any minimal cycle C. ▶Check edges to tips. ▶At most 1 to each tip. ▶At least 2 to some tip. ▶Use decomposition ▶given by C. ▶using a part of C. ▶3 cases for the tips: ▶only black edges, ▶1 green edge, ▶2 red edges. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 14 / 18 Decomposing the Centre ▶Take any minimal cycle C. ▶Check edges to tips. ▶At most 1 to each tip. ▶At least 2 to some tip. ▶Use decomposition ▶given by C. ▶using a part of C. ▶3 cases for the tips: ▶only black edges, ▶1 green edge, ▶2 red edges. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 14 / 18 Decomposing the Centre ▶Take any minimal cycle C. ▶Check edges to tips. ▶At most 1 to each tip. ▶At least 2 to some tip. ▶Use decomposition ▶given by C. ▶using a part of C. ▶3 cases for the tips: ▶only black edges, ▶1 green edge, ▶2 red edges. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 14 / 18 Decomposing the Centre ▶Take any minimal cycle C. ▶Check edges to tips. ▶At most 1 to each tip. ▶At least 2 to some tip. ▶Use decomposition ▶given by C. ▶using a part of C. ▶3 cases for the tips: ▶only black edges, ▶1 green edge, ▶2 red edges. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 14 / 18 Decomposing the Centre ▶Take any minimal cycle C. ▶Check edges to tips. ▶At most 1 to each tip. ▶At least 2 to some tip. ▶Use decomposition ▶given by C. ▶using a part of C. ▶3 cases for the tips: ▶only black edges, ▶1 green edge, ▶2 red edges. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 14 / 18 Decomposing the Centre ▶Take any minimal cycle C. ▶Check edges to tips. ▶At most 1 to each tip. ▶At least 2 to some tip. ▶Use decomposition ▶given by C. ▶using a part of C. ▶3 cases for the tips: ▶only black edges, ▶1 green edge, ▶2 red edges. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 14 / 18 Decomposing the Centre ▶Take any minimal cycle C. ▶Check edges to tips. ▶At most 1 to each tip. ▶At least 2 to some tip. ▶Use decomposition ▶given by C. ▶using a part of C. ▶3 cases for the tips: ▶only black edges, ▶1 green edge, ▶2 red edges. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 14 / 18 The Tips: Two Red Edges ▶One path connects to centre. ▶Put it in Tand rest in C. ▶Problem: “red” chords. ▶Idea: use to shortcut. ▶Must connect new paths. ▶Take maximal sequence of chords such that ▶paths can be connected, ▶chords are maximal. ▶Need: No more red chords. ▶By maximality: No chords between different red paths. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 15 / 18 The Tips: Two Red Edges ▶One path connects to centre. ▶Put it in Tand rest in C. ▶Problem: “red” chords. ▶Idea: use to shortcut. ▶Must connect new paths. ▶Take maximal sequence of chords such that ▶paths can be connected, ▶chords are maximal. ▶Need: No more red chords. ▶By maximality: No chords between different red paths. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 15 / 18 The Tips: Two Red Edges ▶One path connects to centre. ▶Put it in Tand rest in C. ▶Problem: “red” chords. ▶Idea: use to shortcut. ▶Must connect new paths. ▶Take maximal sequence of chords such that ▶paths can be connected, ▶chords are maximal. ▶Need: No more red chords. ▶By maximality: No chords between different red paths. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 15 / 18 The Tips: Two Red Edges ▶Call vertices with neighbours in green paths or the centre good. ▶Suppose not all vertices in a red path are good. ▶Take two good vertices ▶with a bad one in between, ▶of minimal distance. ▶There exists a “crossing” chord. ▶Extends the sequence. E Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 16 / 18 The Tips: Two Red Edges ▶Call vertices with neighbours in green paths or the centre good. ▶Suppose not all vertices in a red path are good. ▶Take two good vertices ▶with a bad one in between, ▶of minimal distance. ▶There exists a “crossing” chord. ▶Extends the sequence. E Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 16 / 18 The Tips: Two Red Edges ▶Call vertices with neighbours in green paths or the centre good. ▶Suppose not all vertices in a red path are good. ▶Take two good vertices ▶with a bad one in between, ▶of minimal distance. ▶There exists a “crossing” chord. ▶Extends the sequence. E Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 16 / 18 The Tips: Two Red Edges ▶Call vertices with neighbours in green paths or the centre good. ▶Suppose not all vertices in a red path are good. ▶Take two good vertices ▶with a bad one in between, ▶of minimal distance. ▶There exists a “crossing” chord. ▶Extends the sequence. E Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 16 / 18 The Tips: Two Red Edges ▶Call vertices with neighbours in green paths or the centre good. ▶Suppose not all vertices in a red path are good. ▶Take two good vertices ▶with a bad one in between, ▶of minimal distance. ▶There exists a “crossing” chord. ▶Extends the sequence. E Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 16 / 18 Decomposing the Centre ▶Take any minimal cycle C. ▶Check edges to tips. ▶At most 1 to each tip. ▶At least 2 to some tip. ▶Use decomposition ▶given by C. ▶using a part of C. ▶3 cases for the tips: ▶only black edges, ▶1 green edge, ▶2 red edges. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 17 / 18 Decomposing the Centre ▶Take any minimal cycle C. ▶Check edges to tips. ▶At most 1 to each tip. ▶At least 2 to some tip. ▶Use decomposition ▶given by C. ▶using a part of C. ▶3 cases for the tips: ▶only black edges, ▶1 green edge, ▶2 red edges. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 17 / 18 Summary ▶Regarded a natural extension of Hamiltonian graphs. ▶Obtained reusable decompositions allowing us to ▶connect a vertex to the tree, ▶complete a cycle. ▶Showed why these suffice to decompose star-like graphs. For the sceptics. Contact: [email protected] Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 18 / 18 Summary ▶Regarded a natural extension of Hamiltonian graphs. ▶Obtained reusable decompositions allowing us to ▶connect a vertex to the tree, ▶complete a cycle. ▶Showed why these suffice to decompose star-like graphs. For the sceptics. Contact: [email protected] Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 18 / 18 For Further Reading S. Akbari, T. R. Jensen, M. Siggers. Decompositions of graphs into trees, forests, and regular subgraphs. Journal of Discrete Mathematics, vol. 338, no. 8, pp. 1322-1327, 2015. M. Xie, C. Zhou, S. Zhou. Decomposition of cubic graphs with a 2-factor consisting of three cycles. Journal of Discrete Mathematics, vol. 343, no. 8, pp. 1118-1139, 2020. O. Bachtler, S. Krumke. Towards obtaining a 3-Decomposition from a perfect Matching. The Electronic Journal of Combinatorics, vol. 29, no. 4, 2022. Oliver Bachtler, Sven O. Krumke Decomposing Star-like Cubic Graphs SEG 27 1 / 1