Decomposing S a -like Cubic G aphs
Oli e Bach le , S en O. K umke
RPTU Kaise slau e n-Landau
27. SEG Wo kshop, 2023
Ou line
Basics
3-decomposi ions
Exis ence o Hamil onian g aphs
Cons uc ing a Decomposi ion
F om he cen e
To he ips
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 1 / 18
3-Decomposi ions o G aphs
De ini ion (Cubic G aphs)
A g aph is cubic i e e y e ex has deg ee 3.
De ini ion (3-Decomposi ion)
A3-decomposi ion o a connec ed cubic g aph Gconsis s o
▶a spanning ee T,
▶a se o cycles C, and
▶a ma ching M
such ha E(G)is he disjoin union E(T)∪E(C)∪M.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 2 / 18
3-Decomposi ions o G aphs
De ini ion (Cubic G aphs)
A g aph is cubic i e e y e ex has deg ee 3.
De ini ion (3-Decomposi ion)
A3-decomposi ion o a connec ed cubic g aph Gconsis s o
▶a spanning ee T,
▶a se o cycles C, and
▶a ma ching M
such ha E(G)is he disjoin union E(T)∪E(C)∪M.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 2 / 18
3-Decomposi ions o G aphs
De ini ion (Cubic G aphs)
A g aph is cubic i e e y e ex has deg ee 3.
De ini ion (3-Decomposi ion)
A3-decomposi ion o a connec ed cubic g aph Gconsis s o
▶a spanning ee T,
▶a se o cycles C, and
▶a ma ching M
such ha E(G)is he disjoin union E(T)∪E(C)∪M.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 2 / 18
An Example G aph
▶Gi en: connec ed cubic g aph.
▶Take a spanning ee.
▶The emaining edges o m
cycles and pa hs.
▶Wan pa hs o leng h 1.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 3 / 18
An Example G aph
▶Gi en: connec ed cubic g aph.
▶Take a spanning ee.
▶The emaining edges o m
cycles and pa hs.
▶Wan pa hs o leng h 1.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 3 / 18
An Example G aph
▶Gi en: connec ed cubic g aph.
▶Take a spanning ee.
▶The emaining edges o m
cycles and pa hs.
▶Wan pa hs o leng h 1.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 3 / 18
An Example G aph
▶Gi en: connec ed cubic g aph.
▶Take a spanning ee.
▶The emaining edges o m
cycles and pa hs.
▶Wan pa hs o leng h 1.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 3 / 18
Ou Resul
De ini ion (S a -like G aphs)
Le Gbe a connec ed cubic g aph wi h a pe ec ma ching M.
▶G−Mconsis s o cycles.
▶Con ac ing hese yields he con ac ion g aph GM.
Gis s a -like i i has a pe ec ma ching Msuch ha GMis a s a .
De ini ion (3-Connec i i y)
A g aph Gis 3-connec ed i emo ing 2 e ices does no disconnec i .
Theo em (Main Resul , 2022)
E e y 3-connec ed s a -like g aph has a 3-decomposi ion.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 5 / 18
Ou Resul
De ini ion (S a -like G aphs)
Le Gbe a connec ed cubic g aph wi h a pe ec ma ching M.
▶G−Mconsis s o cycles.
▶Con ac ing hese yields he con ac ion g aph GM.
Gis s a -like i i has a pe ec ma ching Msuch ha GMis a s a .
De ini ion (3-Connec i i y)
A g aph Gis 3-connec ed i emo ing 2 e ices does no disconnec i .
Theo em (Main Resul , 2022)
E e y 3-connec ed s a -like g aph has a 3-decomposi ion.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 5 / 18
Ou Resul
De ini ion (S a -like G aphs)
Le Gbe a connec ed cubic g aph wi h a pe ec ma ching M.
▶G−Mconsis s o cycles.
▶Con ac ing hese yields he con ac ion g aph GM.
Gis s a -like i i has a pe ec ma ching Msuch ha GMis a s a .
De ini ion (3-Connec i i y)
A g aph Gis 3-connec ed i emo ing 2 e ices does no disconnec i .
Theo em (Main Resul , 2022)
E e y 3-connec ed s a -like g aph has a 3-decomposi ion.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 5 / 18
Ou Resul
De ini ion (S a -like G aphs)
Le Gbe a connec ed cubic g aph wi h a pe ec ma ching M.
▶G−Mconsis s o cycles.
▶Con ac ing hese yields he con ac ion g aph GM.
Gis s a -like i i has a pe ec ma ching Msuch ha GMis a s a .
De ini ion (3-Connec i i y)
A g aph Gis 3-connec ed i emo ing 2 e ices does no disconnec i .
Theo em (Main Resul , 2022)
E e y 3-connec ed s a -like g aph has a 3-decomposi ion.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 5 / 18
Ou Resul
De ini ion (S a -like G aphs)
Le Gbe a connec ed cubic g aph wi h a pe ec ma ching M.
▶G−Mconsis s o cycles.
▶Con ac ing hese yields he con ac ion g aph GM.
Gis s a -like i i has a pe ec ma ching Msuch ha GMis a s a .
De ini ion (3-Connec i i y)
A g aph Gis 3-connec ed i emo ing 2 e ices does no disconnec i .
Theo em (Main Resul , 2022)
E e y 3-connec ed s a -like g aph has a 3-decomposi ion.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 5 / 18
Ou Resul
De ini ion (S a -like G aphs)
Le Gbe a connec ed cubic g aph wi h a pe ec ma ching M.
▶G−Mconsis s o cycles.
▶Con ac ing hese yields he con ac ion g aph GM.
Gis s a -like i i has a pe ec ma ching Msuch ha GMis a s a .
De ini ion (3-Connec i i y)
A g aph Gis 3-connec ed i emo ing 2 e ices does no disconnec i .
Theo em (Main Resul , 2022)
E e y 3-connec ed s a -like g aph has a 3-decomposi ion.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 5 / 18
Ou Resul
De ini ion (S a -like G aphs)
Le Gbe a connec ed cubic g aph wi h a pe ec ma ching M.
▶G−Mconsis s o cycles.
▶Con ac ing hese yields he con ac ion g aph GM.
Gis s a -like i i has a pe ec ma ching Msuch ha GMis a s a .
De ini ion (3-Connec i i y)
A g aph Gis 3-connec ed i emo ing 2 e ices does no disconnec i .
Theo em (Main Resul , 2022)
E e y 3-connec ed s a -like g aph has a 3-decomposi ion.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 5 / 18
Ou Resul
De ini ion (S a -like G aphs)
Le Gbe a connec ed cubic g aph wi h a pe ec ma ching M.
▶G−Mconsis s o cycles.
▶Con ac ing hese yields he con ac ion g aph GM.
Gis s a -like i i has a pe ec ma ching Msuch ha GMis a s a .
De ini ion (3-Connec i i y)
A g aph Gis 3-connec ed i emo ing 2 e ices does no disconnec i .
Theo em (Xie, Zhou, Zhou, 2020)
E e y g aph wi h a con ac ion g aph on 3 e ices has a 3-decomposi ion.
Theo em (Main Resul , 2022)
E e y 3-connec ed s a -like g aph has a 3-decomposi ion.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 5 / 18
Ou Resul
De ini ion (S a -like G aphs)
Le Gbe a connec ed cubic g aph wi h a pe ec ma ching M.
▶G−Mconsis s o cycles.
▶Con ac ing hese yields he con ac ion g aph GM.
Gis s a -like i i has a pe ec ma ching Msuch ha GMis a s a .
De ini ion (3-Connec i i y)
A g aph Gis 3-connec ed i emo ing 2 e ices does no disconnec i .
Theo em (Main Resul , 2022)
E e y 3-connec ed s a -like g aph has a 3-decomposi ion.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 5 / 18
Hamil onian G aphs ha e 3-Decomposi ions
Theo em (Akba i, Jensen, Sigge s)
E e y connec ed cubic Hamil onian g aph has a 3-decomposi ion.
minimal cycle
Call his he decomposi ion gi en by he minimal cycle.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 6 / 18
Hamil onian G aphs ha e 3-Decomposi ions
Theo em (Akba i, Jensen, Sigge s)
E e y connec ed cubic Hamil onian g aph has a 3-decomposi ion.
minimal cycle
Call his he decomposi ion gi en by he minimal cycle.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 6 / 18
Hamil onian G aphs ha e 3-Decomposi ions
Theo em (Akba i, Jensen, Sigge s)
E e y connec ed cubic Hamil onian g aph has a 3-decomposi ion.
minimal cycle
Call his he decomposi ion gi en by he minimal cycle.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 6 / 18
Hamil onian G aphs ha e 3-Decomposi ions
Theo em (Akba i, Jensen, Sigge s)
E e y connec ed cubic Hamil onian g aph has a 3-decomposi ion.
minimal cycle
Call his he decomposi ion gi en by he minimal cycle.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 6 / 18
Hamil onian G aphs ha e 3-Decomposi ions
Theo em (Akba i, Jensen, Sigge s)
E e y connec ed cubic Hamil onian g aph has a 3-decomposi ion.
minimal cycle
Call his he decomposi ion gi en by he minimal cycle.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 6 / 18
Hamil onian G aphs ha e 3-Decomposi ions
Theo em (Akba i, Jensen, Sigge s)
E e y connec ed cubic Hamil onian g aph has a 3-decomposi ion.
minimal cycle
Call his he decomposi ion gi en by he minimal cycle.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 6 / 18
Fi s S eps
Theo em (Main Resul )
E e y 3-connec ed s a -like g aph has a 3-decomposi ion.
Assump ion
All cycles in G−Mha e cho ds in G.
Obse a ion
The e exis s a minimal cycle a oiding any ixed bounda y e ex.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 7 / 18
Fi s S eps
Theo em (Main Resul )
E e y 3-connec ed s a -like g aph has a 3-decomposi ion.
Assump ion
All cycles in G−Mha e cho ds in G.
Obse a ion
The e exis s a minimal cycle a oiding any ixed bounda y e ex.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 7 / 18
Fi s S eps
Theo em (Main Resul )
E e y 3-connec ed s a -like g aph has a 3-decomposi ion.
Assump ion
All cycles in G−Mha e cho ds in G.
Obse a ion
The e exis s a minimal cycle a oiding any ixed bounda y e ex.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 7 / 18
Fi s S eps
Theo em (Main Resul )
E e y 3-connec ed s a -like g aph has a 3-decomposi ion.
Assump ion
All cycles in G−Mha e cho ds in G.
Obse a ion
The e exis s a minimal cycle a oiding any ixed bounda y e ex.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 7 / 18
Fi s S eps
Theo em (Main Resul )
E e y 3-connec ed s a -like g aph has a 3-decomposi ion.
Assump ion
All cycles in G−Mha e cho ds in G.
Obse a ion
The e exis s a minimal cycle a oiding any ixed bounda y e ex.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 7 / 18
Decomposing he Cen e
▶Take any minimal cycle C.
▶Check edges o ips.
▶A mos 1 o each ip.
▶A leas 2 o some ip.
▶Use decomposi ion
▶gi en by C.
▶using a pa o C.
▶3 cases o he ips:
▶only black edges,
▶1 g een edge,
▶2 ed edges.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 8 / 18
Decomposing he Cen e
▶Take any minimal cycle C.
▶Check edges o ips.
▶A mos 1 o each ip.
▶A leas 2 o some ip.
▶Use decomposi ion
▶gi en by C.
▶using a pa o C.
▶3 cases o he ips:
▶only black edges,
▶1 g een edge,
▶2 ed edges.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 8 / 18
The Tips: Only Black Edges
Take he decomposi ion gi en by a minimal cycle:
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 9 / 18
The Tips: Only Black Edges
Take he decomposi ion gi en by a minimal cycle:
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 9 / 18
The Tips: Only Black Edges
Take he decomposi ion gi en by a minimal cycle:
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 9 / 18
The Tips: Only Black Edges
Take he decomposi ion gi en by a minimal cycle:
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 9 / 18
Decomposing he Cen e
▶Take any minimal cycle C.
▶Check edges o ips.
▶A mos 1 o each ip.
▶A leas 2 o some ip.
▶Use decomposi ion
▶gi en by C.
▶using a pa o C.
▶3 cases o he ips:
▶only black edges,
▶1 g een edge,
▶2 ed edges.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 10 / 18
Decomposing he Cen e
▶Take any minimal cycle C.
▶Check edges o ips.
▶A mos 1 o each ip.
▶A leas 2 o some ip.
▶Use decomposi ion
▶gi en by C.
▶using a pa o C.
▶3 cases o he ips:
▶only black edges,
▶1 g een edge,
▶2 ed edges.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 10 / 18
Decomposing he Cen e
▶Take any minimal cycle C.
▶Check edges o ips.
▶A mos 1 o each ip.
▶A leas 2 o some ip.
▶Use decomposi ion
▶gi en by C.
▶using a pa o C.
▶3 cases o he ips:
▶only black edges,
▶1 g een edge,
▶2 ed edges.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 10 / 18
The Tips: One G een Edge
▶Look o a use ul minimal cycle.
▶I none exis s ⇒All cho ds go om he le o he igh pa h.
▶Bo h pa hs ha e he same leng h ⇒Le els.
▶Call a cho d long i i s ends a e a leas 2 le els apa .
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 11 / 18
The Tips: One G een Edge
Case 1: No long cho d exis s
▶Two o m o cho ds:
▶di ec
▶c oss
▶Ob ain a Hamil onian pa h.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 12 / 18
The Tips: One G een Edge
Case 1: No long cho d exis s
▶Two o m o cho ds:
▶di ec
▶c oss
▶Ob ain a Hamil onian pa h.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 12 / 18
The Tips: One G een Edge
Case 1: No long cho d exis s
▶Two o m o cho ds:
▶di ec
▶c oss
▶Ob ain a Hamil onian pa h.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 12 / 18
The Tips: One G een Edge
Case 1: No long cho d exis s
▶Two o m o cho ds:
▶di ec
▶c oss
▶Ob ain a Hamil onian pa h.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 12 / 18
The Tips: One G een Edge
Case 1: No long cho d exis s
▶Two o m o cho ds:
▶di ec
▶c oss
▶Ob ain a Hamil onian pa h.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 12 / 18
The Tips: One G een Edge
Case 1: No long cho d exis s
▶Two o m o cho ds:
▶di ec
▶c oss
▶Ob ain a Hamil onian pa h.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 12 / 18
The Tips: One G een Edge
Case 1: No long cho d exis s
▶Two o m o cho ds:
▶di ec
▶c oss
▶Ob ain a Hamil onian pa h.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 12 / 18
The Tips: One G een Edge
Case 1: No long cho d exis s
▶Two o m o cho ds:
▶di ec
▶c oss
▶Ob ain a Hamil onian pa h.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 12 / 18
The Tips: One G een Edge
Case 1: No long cho d exis s
▶Two o m o cho ds:
▶di ec
▶c oss
▶Ob ain a Hamil onian pa h.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 12 / 18
The Tips: One G een Edge
Case 2: A long cho d exis s
▶Take he i s such cho d.
▶Ve ices be o e pai ed up.
▶Rega d he o he e ex on
his le el and i s successo .
▶Neighbou s below he cho d.
▶Use a wo-cho d cycle.
▶Lea es a ee.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 13 / 18
Decomposing he Cen e
▶Take any minimal cycle C.
▶Check edges o ips.
▶A mos 1 o each ip.
▶A leas 2 o some ip.
▶Use decomposi ion
▶gi en by C.
▶using a pa o C.
▶3 cases o he ips:
▶only black edges,
▶1 g een edge,
▶2 ed edges.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 14 / 18
Decomposing he Cen e
▶Take any minimal cycle C.
▶Check edges o ips.
▶A mos 1 o each ip.
▶A leas 2 o some ip.
▶Use decomposi ion
▶gi en by C.
▶using a pa o C.
▶3 cases o he ips:
▶only black edges,
▶1 g een edge,
▶2 ed edges.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 14 / 18
Decomposing he Cen e
▶Take any minimal cycle C.
▶Check edges o ips.
▶A mos 1 o each ip.
▶A leas 2 o some ip.
▶Use decomposi ion
▶gi en by C.
▶using a pa o C.
▶3 cases o he ips:
▶only black edges,
▶1 g een edge,
▶2 ed edges.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 14 / 18
Decomposing he Cen e
▶Take any minimal cycle C.
▶Check edges o ips.
▶A mos 1 o each ip.
▶A leas 2 o some ip.
▶Use decomposi ion
▶gi en by C.
▶using a pa o C.
▶3 cases o he ips:
▶only black edges,
▶1 g een edge,
▶2 ed edges.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 14 / 18
Decomposing he Cen e
▶Take any minimal cycle C.
▶Check edges o ips.
▶A mos 1 o each ip.
▶A leas 2 o some ip.
▶Use decomposi ion
▶gi en by C.
▶using a pa o C.
▶3 cases o he ips:
▶only black edges,
▶1 g een edge,
▶2 ed edges.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 14 / 18
Decomposing he Cen e
▶Take any minimal cycle C.
▶Check edges o ips.
▶A mos 1 o each ip.
▶A leas 2 o some ip.
▶Use decomposi ion
▶gi en by C.
▶using a pa o C.
▶3 cases o he ips:
▶only black edges,
▶1 g een edge,
▶2 ed edges.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 14 / 18
Decomposing he Cen e
▶Take any minimal cycle C.
▶Check edges o ips.
▶A mos 1 o each ip.
▶A leas 2 o some ip.
▶Use decomposi ion
▶gi en by C.
▶using a pa o C.
▶3 cases o he ips:
▶only black edges,
▶1 g een edge,
▶2 ed edges.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 14 / 18
The Tips: Two Red Edges
▶One pa h connec s o cen e.
▶Pu i in Tand es in C.
▶P oblem: “ ed” cho ds.
▶Idea: use o sho cu .
▶Mus connec new pa hs.
▶Take maximal sequence o
cho ds such ha
▶pa hs can be connec ed,
▶cho ds a e maximal.
▶Need: No mo e ed cho ds.
▶By maximali y: No cho ds
be ween di e en ed pa hs.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 15 / 18
The Tips: Two Red Edges
▶One pa h connec s o cen e.
▶Pu i in Tand es in C.
▶P oblem: “ ed” cho ds.
▶Idea: use o sho cu .
▶Mus connec new pa hs.
▶Take maximal sequence o
cho ds such ha
▶pa hs can be connec ed,
▶cho ds a e maximal.
▶Need: No mo e ed cho ds.
▶By maximali y: No cho ds
be ween di e en ed pa hs.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 15 / 18
The Tips: Two Red Edges
▶One pa h connec s o cen e.
▶Pu i in Tand es in C.
▶P oblem: “ ed” cho ds.
▶Idea: use o sho cu .
▶Mus connec new pa hs.
▶Take maximal sequence o
cho ds such ha
▶pa hs can be connec ed,
▶cho ds a e maximal.
▶Need: No mo e ed cho ds.
▶By maximali y: No cho ds
be ween di e en ed pa hs.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 15 / 18
The Tips: Two Red Edges
▶Call e ices wi h neighbou s in
g een pa hs o he cen e good.
▶Suppose no all e ices in a ed
pa h a e good.
▶Take wo good e ices
▶wi h a bad one in be ween,
▶o minimal dis ance.
▶The e exis s a “c ossing” cho d.
▶Ex ends he sequence. E
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 16 / 18
The Tips: Two Red Edges
▶Call e ices wi h neighbou s in
g een pa hs o he cen e good.
▶Suppose no all e ices in a ed
pa h a e good.
▶Take wo good e ices
▶wi h a bad one in be ween,
▶o minimal dis ance.
▶The e exis s a “c ossing” cho d.
▶Ex ends he sequence. E
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 16 / 18
The Tips: Two Red Edges
▶Call e ices wi h neighbou s in
g een pa hs o he cen e good.
▶Suppose no all e ices in a ed
pa h a e good.
▶Take wo good e ices
▶wi h a bad one in be ween,
▶o minimal dis ance.
▶The e exis s a “c ossing” cho d.
▶Ex ends he sequence. E
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 16 / 18
The Tips: Two Red Edges
▶Call e ices wi h neighbou s in
g een pa hs o he cen e good.
▶Suppose no all e ices in a ed
pa h a e good.
▶Take wo good e ices
▶wi h a bad one in be ween,
▶o minimal dis ance.
▶The e exis s a “c ossing” cho d.
▶Ex ends he sequence. E
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 16 / 18
The Tips: Two Red Edges
▶Call e ices wi h neighbou s in
g een pa hs o he cen e good.
▶Suppose no all e ices in a ed
pa h a e good.
▶Take wo good e ices
▶wi h a bad one in be ween,
▶o minimal dis ance.
▶The e exis s a “c ossing” cho d.
▶Ex ends he sequence. E
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 16 / 18
Decomposing he Cen e
▶Take any minimal cycle C.
▶Check edges o ips.
▶A mos 1 o each ip.
▶A leas 2 o some ip.
▶Use decomposi ion
▶gi en by C.
▶using a pa o C.
▶3 cases o he ips:
▶only black edges,
▶1 g een edge,
▶2 ed edges.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 17 / 18
Decomposing he Cen e
▶Take any minimal cycle C.
▶Check edges o ips.
▶A mos 1 o each ip.
▶A leas 2 o some ip.
▶Use decomposi ion
▶gi en by C.
▶using a pa o C.
▶3 cases o he ips:
▶only black edges,
▶1 g een edge,
▶2 ed edges.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 17 / 18
Summa y
▶Rega ded a na u al ex ension o Hamil onian g aphs.
▶Ob ained eusable decomposi ions allowing us o
▶connec a e ex o he ee,
▶comple e a cycle.
▶Showed why hese su ice o decompose s a -like g aphs.
Fo he scep ics.
Con ac : bach le @ma hema ik.uni-kl.de
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 18 / 18
Summa y
▶Rega ded a na u al ex ension o Hamil onian g aphs.
▶Ob ained eusable decomposi ions allowing us o
▶connec a e ex o he ee,
▶comple e a cycle.
▶Showed why hese su ice o decompose s a -like g aphs.
Fo he scep ics.
Con ac : bach le @ma hema ik.uni-kl.de
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 18 / 18
Fo Fu he Reading
S. Akba i, T. R. Jensen, M. Sigge s.
Decomposi ions o g aphs in o ees, o es s, and egula subg aphs.
Jou nal o Disc e e Ma hema ics, ol. 338, no. 8, pp. 1322-1327, 2015.
M. Xie, C. Zhou, S. Zhou.
Decomposi ion o cubic g aphs wi h a 2- ac o consis ing o h ee cycles.
Jou nal o Disc e e Ma hema ics, ol. 343, no. 8, pp. 1118-1139, 2020.
O. Bach le , S. K umke.
Towa ds ob aining a 3-Decomposi ion om a pe ec Ma ching.
The Elec onic Jou nal o Combina o ics, ol. 29, no. 4, 2022.
Oli e Bach le , S en O. K umke Decomposing S a -like Cubic G aphs SEG 27 1 / 1
