Reductions for the 3-Decomposition Conjecture

Reductions for the 3-Decomposition Conjecture Oliver Bachtler and Irene Heinrich Department of Mathematics TU Kaiserslautern and Department of Mathematics TU Darmstadt XII Latin-American Algorithms, Graphs and Optimization Symposium, 2023 Motivation Four Colour Theorem Every planar graph is 4-colourable. O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 1 / 16 Motivation Four Colour Theorem Every planar graph is 4-colourable. O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 1 / 16 Motivation Four Colour Theorem Every planar graph is 4-colourable. O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 1 / 16 Motivation Four Colour Theorem Every planar graph is 4-colourable. O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 1 / 16 Motivation Four Colour Theorem Every planar graph is 4-colourable. O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 1 / 16 Proving the Four Colour Theorem Find a set of configurations that is ▶reducible and ▶checked by a computer ▶unavoidable. ▶by hand, 400 pages O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 2 / 16 Proving the Four Colour Theorem Find a set of configurations that is ▶reducible and ▶checked by a computer ▶unavoidable. ▶by hand, 400 pages O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 2 / 16 Proving the Four Colour Theorem Find a set of configurations that is ▶reducible and ▶checked by a computer ▶unavoidable. ▶by hand, 400 pages O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 2 / 16 Proving the Four Colour Theorem Find a set of configurations that is ▶reducible and ▶checked by a computer ▶unavoidable. ▶by hand, 400 pages O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 2 / 16 Proving the Four Colour Theorem Find a set of configurations that is ▶reducible and ▶checked by a computer ▶unavoidable. ▶by hand, 400 pages O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 2 / 16 Outline The 3-Decomposition Conjecture Reducible Configurations Unavoidable Structures O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 3 / 16 The 3-Decomposition Conjecture O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 4 / 16 3-Decompositions of Graphs Definition A graph is cubic if every vertex has degree 3. Definition A3-decomposition of a connected cubic graph Gconsists of ▶aspanning tree T, ▶aunion of cycles C, and ▶amatching M such that E(G)is the disjoint union E(T)∪E(C)∪M. O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 5 / 16 3-Decompositions of Graphs Definition A graph is cubic if every vertex has degree 3. Definition A3-decomposition of a connected cubic graph Gconsists of ▶aspanning tree T, ▶aunion of cycles C, and ▶amatching M such that E(G)is the disjoint union E(T)∪E(C)∪M. O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 5 / 16 3-Decompositions of Graphs Definition A graph is cubic if every vertex has degree 3. Definition A3-decomposition of a connected cubic graph Gconsists of ▶aspanning tree T, ▶aunion of cycles C, and ▶amatching M such that E(G)is the disjoint union E(T)∪E(C)∪M. O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 5 / 16 An Example Graph ▶Given: connected cubic graph. ▶Take a spanning tree. ▶The remaining edges form cycles and paths. ▶Want paths of length 1. O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 6 / 16 An Example Graph ▶Given: connected cubic graph. ▶Take a spanning tree. ▶The remaining edges form cycles and paths. ▶Want paths of length 1. O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 6 / 16 An Example Graph ▶Given: connected cubic graph. ▶Take a spanning tree. ▶The remaining edges form cycles and paths. ▶Want paths of length 1. O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 6 / 16 Reducible Configurations O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 8 / 16 Reducible Configurations Definition Areducible configuration is a graph that is not part of a 3-connected minimum counterexample to the 3-decomposition conjecture. Example The triangle is reducible. O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 9 / 16 Reducible Configurations Definition Areducible configuration is a graph that is not part of a 3-connected minimum counterexample to the 3-decomposition conjecture. Example The triangle is reducible. O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 9 / 16 Reducible Configurations Definition Areducible configuration is a graph that is not part of a 3-connected minimum counterexample to the 3-decomposition conjecture. Example The triangle is reducible. O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 9 / 16 Reducible Configurations Definition Areducible configuration is a graph that is not part of a 3-connected minimum counterexample to the 3-decomposition conjecture. Example The triangle is reducible. O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 9 / 16 Reducible Configurations Definition Areducible configuration is a graph that is not part of a 3-connected minimum counterexample to the 3-decomposition conjecture. Example The triangle is reducible. O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 9 / 16 Reducible Configurations Definition Areducible configuration is a graph that is not part of a 3-connected minimum counterexample to the 3-decomposition conjecture. Example The triangle is reducible. O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 9 / 16 Reducible Configurations Definition Areducible configuration is a graph that is not part of a 3-connected minimum counterexample to the 3-decomposition conjecture. Example The triangle is reducible. O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 9 / 16 Non-Reducibility of the square Example The square is not reducible. O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 10 / 16 Non-Reducibility of the square Example The square is not reducible. O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 10 / 16 A Bigger Example Example The claw-square is reducible. O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 11 / 16 A Bigger Example Example The claw-square is reducible. O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 11 / 16 A List of Reducible Configurations Theorem The graphs below are reducible configurations. O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 12 / 16 A List of Reducible Configurations Theorem The graphs below are reducible configurations. O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 12 / 16 A List of Reducible Configurations Theorem The graphs below are reducible configurations. O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 12 / 16 A List of Reducible Configurations Theorem The graphs below are reducible configurations. O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 12 / 16 A List of Reducible Configurations Theorem The graphs below are reducible configurations. O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 12 / 16 A List of Reducible Configurations Theorem The graphs below are reducible configurations. O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 12 / 16 Unavoidable Structures O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 13 / 16 Unavoidable Structures Question: Are these reducible configurations unavoidable? Answer: No (sadly). Solution: Restrict the class of cubic graphs to make them unavoidable. ⇒Bound the path-width. O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 14 / 16 Bounding the Path-Width Theorem Cubic graphs of path-width at most 4contain a reducible configuration. Corollary Every 3-connected cubic graph of path-width at most 4satisfies the 3-decomposition conjecture. O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 15 / 16 Summary ▶We have seen six reducible configurations, ▶noted that they are unavoidable for path-width 4, and ▶deduced that the 3-decomposition conjecture holds for 3-connected cubic graphs of path-width 4. Contact: [email protected] O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 16 / 16 Summary ▶We have seen six reducible configurations, ▶noted that they are unavoidable for path-width 4, and ▶deduced that the 3-decomposition conjecture holds for 3-connected cubic graphs of path-width 4. Contact: [email protected] O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 16 / 16 Interesting Extensions O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 1 / 3 Reducibility of the Domino C1 C2 H2 H4 O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 2 / 3 What Is Path-Width? Lengthy to define. O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 3 / 3 What Is Path-Width? Definition (Path-Decompositions) ▶Let Gbe a graph, ▶P=p1. . . pna path, ▶V={V1,...,Vn}be bags (⊆V(G)). (P,V)is a path-decomposition of Gif: ▶Every v∈V(G)is contained in some bag. ▶Every uv ∈E(G)is covered by some bag. ▶The set {pi:v∈Vi}is connected for all v∈V(G). Definition (Path-Width) Let Gbe a graph and (P,V)be a path-decomposition of G. ▶The width of (P,V)is max{|V1|,...,|Vn|} − 1. ▶The path-width of Gis the minimal width of its path-decompositions. Lengthy to define. O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 3 / 3 What Is Path-Width? Lengthy to define. O. Bachtler and I. Heinrich (RPTU) Reductions for the 3-Dec. Conjecture LAGOS 2023 3 / 3