Exists a bound for threewidth in $Delta(G)leq 3$ graphs?












1












$begingroup$


Is it true that $Delta(G)leq3$ implies $TW(G)leq6$? (where $TW$ is the "treewidth"). I know that for $Delta(G)leq4$ there is no bound for treewidth because the $ntimes n$ grid has $TW=n$. For $Deltaleq2$ it is easy to see that $TWleq 2$, and the case $Deltaleq1$ is trivial. I think this is the right bound only because I cannot find bigger counterexamples; but I dont have any idea to prove this.










share|cite|improve this question









$endgroup$

















    1












    $begingroup$


    Is it true that $Delta(G)leq3$ implies $TW(G)leq6$? (where $TW$ is the "treewidth"). I know that for $Delta(G)leq4$ there is no bound for treewidth because the $ntimes n$ grid has $TW=n$. For $Deltaleq2$ it is easy to see that $TWleq 2$, and the case $Deltaleq1$ is trivial. I think this is the right bound only because I cannot find bigger counterexamples; but I dont have any idea to prove this.










    share|cite|improve this question









    $endgroup$















      1












      1








      1





      $begingroup$


      Is it true that $Delta(G)leq3$ implies $TW(G)leq6$? (where $TW$ is the "treewidth"). I know that for $Delta(G)leq4$ there is no bound for treewidth because the $ntimes n$ grid has $TW=n$. For $Deltaleq2$ it is easy to see that $TWleq 2$, and the case $Deltaleq1$ is trivial. I think this is the right bound only because I cannot find bigger counterexamples; but I dont have any idea to prove this.










      share|cite|improve this question









      $endgroup$




      Is it true that $Delta(G)leq3$ implies $TW(G)leq6$? (where $TW$ is the "treewidth"). I know that for $Delta(G)leq4$ there is no bound for treewidth because the $ntimes n$ grid has $TW=n$. For $Deltaleq2$ it is easy to see that $TWleq 2$, and the case $Deltaleq1$ is trivial. I think this is the right bound only because I cannot find bigger counterexamples; but I dont have any idea to prove this.







      graph-theory






      share|cite|improve this question













      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked Dec 20 '18 at 2:22









      Veridian DynamicsVeridian Dynamics

      1,909312




      1,909312






















          2 Answers
          2






          active

          oldest

          votes


















          0












          $begingroup$


          As part of their work on graph minors leading to the Robertson–Seymour theorem and the graph structure theorem, Neil Robertson and Paul Seymour proved that a family $F$ of finite graphs has unbounded treewidth if and only if the minors of graphs in $F$ include arbitrarily large square grid graphs, or equivalently subgraphs of the hexagonal tiling formed by intersecting it with arbitrarily large disks. (Wikipedia)







          share|cite|improve this answer









          $endgroup$





















            1












            $begingroup$

            A simple proof goes this way:



            Take $K_n$ the complete graph in $n$ vertices. Take $vin G$, replace it with a cycle of length $d(v)=n-1$ and connect the $d(v)$ vertices in a 1-to-1 fashion to a vertex of the cycle. The result is that every vertex in the cycle has degree $3$. Repeat this until no vertex of degree $>3$ left. The graph $G$ obtained is $3$-regular and (clearly) $K_nleq G$. Then, $text{TW}(G)geqtext{TW}(K_n)=n-1$. So, the treewidth is unbounded even in the class of $3$-regular graphs.






            share|cite|improve this answer









            $endgroup$













              Your Answer





              StackExchange.ifUsing("editor", function () {
              return StackExchange.using("mathjaxEditing", function () {
              StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
              StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
              });
              });
              }, "mathjax-editing");

              StackExchange.ready(function() {
              var channelOptions = {
              tags: "".split(" "),
              id: "69"
              };
              initTagRenderer("".split(" "), "".split(" "), channelOptions);

              StackExchange.using("externalEditor", function() {
              // Have to fire editor after snippets, if snippets enabled
              if (StackExchange.settings.snippets.snippetsEnabled) {
              StackExchange.using("snippets", function() {
              createEditor();
              });
              }
              else {
              createEditor();
              }
              });

              function createEditor() {
              StackExchange.prepareEditor({
              heartbeatType: 'answer',
              autoActivateHeartbeat: false,
              convertImagesToLinks: true,
              noModals: true,
              showLowRepImageUploadWarning: true,
              reputationToPostImages: 10,
              bindNavPrevention: true,
              postfix: "",
              imageUploader: {
              brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
              contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
              allowUrls: true
              },
              noCode: true, onDemand: true,
              discardSelector: ".discard-answer"
              ,immediatelyShowMarkdownHelp:true
              });


              }
              });














              draft saved

              draft discarded


















              StackExchange.ready(
              function () {
              StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3047080%2fexists-a-bound-for-threewidth-in-deltag-leq-3-graphs%23new-answer', 'question_page');
              }
              );

              Post as a guest















              Required, but never shown

























              2 Answers
              2






              active

              oldest

              votes








              2 Answers
              2






              active

              oldest

              votes









              active

              oldest

              votes






              active

              oldest

              votes









              0












              $begingroup$


              As part of their work on graph minors leading to the Robertson–Seymour theorem and the graph structure theorem, Neil Robertson and Paul Seymour proved that a family $F$ of finite graphs has unbounded treewidth if and only if the minors of graphs in $F$ include arbitrarily large square grid graphs, or equivalently subgraphs of the hexagonal tiling formed by intersecting it with arbitrarily large disks. (Wikipedia)







              share|cite|improve this answer









              $endgroup$


















                0












                $begingroup$


                As part of their work on graph minors leading to the Robertson–Seymour theorem and the graph structure theorem, Neil Robertson and Paul Seymour proved that a family $F$ of finite graphs has unbounded treewidth if and only if the minors of graphs in $F$ include arbitrarily large square grid graphs, or equivalently subgraphs of the hexagonal tiling formed by intersecting it with arbitrarily large disks. (Wikipedia)







                share|cite|improve this answer









                $endgroup$
















                  0












                  0








                  0





                  $begingroup$


                  As part of their work on graph minors leading to the Robertson–Seymour theorem and the graph structure theorem, Neil Robertson and Paul Seymour proved that a family $F$ of finite graphs has unbounded treewidth if and only if the minors of graphs in $F$ include arbitrarily large square grid graphs, or equivalently subgraphs of the hexagonal tiling formed by intersecting it with arbitrarily large disks. (Wikipedia)







                  share|cite|improve this answer









                  $endgroup$




                  As part of their work on graph minors leading to the Robertson–Seymour theorem and the graph structure theorem, Neil Robertson and Paul Seymour proved that a family $F$ of finite graphs has unbounded treewidth if and only if the minors of graphs in $F$ include arbitrarily large square grid graphs, or equivalently subgraphs of the hexagonal tiling formed by intersecting it with arbitrarily large disks. (Wikipedia)








                  share|cite|improve this answer












                  share|cite|improve this answer



                  share|cite|improve this answer










                  answered Dec 20 '18 at 7:54









                  Alex RavskyAlex Ravsky

                  40.4k32282




                  40.4k32282























                      1












                      $begingroup$

                      A simple proof goes this way:



                      Take $K_n$ the complete graph in $n$ vertices. Take $vin G$, replace it with a cycle of length $d(v)=n-1$ and connect the $d(v)$ vertices in a 1-to-1 fashion to a vertex of the cycle. The result is that every vertex in the cycle has degree $3$. Repeat this until no vertex of degree $>3$ left. The graph $G$ obtained is $3$-regular and (clearly) $K_nleq G$. Then, $text{TW}(G)geqtext{TW}(K_n)=n-1$. So, the treewidth is unbounded even in the class of $3$-regular graphs.






                      share|cite|improve this answer









                      $endgroup$


















                        1












                        $begingroup$

                        A simple proof goes this way:



                        Take $K_n$ the complete graph in $n$ vertices. Take $vin G$, replace it with a cycle of length $d(v)=n-1$ and connect the $d(v)$ vertices in a 1-to-1 fashion to a vertex of the cycle. The result is that every vertex in the cycle has degree $3$. Repeat this until no vertex of degree $>3$ left. The graph $G$ obtained is $3$-regular and (clearly) $K_nleq G$. Then, $text{TW}(G)geqtext{TW}(K_n)=n-1$. So, the treewidth is unbounded even in the class of $3$-regular graphs.






                        share|cite|improve this answer









                        $endgroup$
















                          1












                          1








                          1





                          $begingroup$

                          A simple proof goes this way:



                          Take $K_n$ the complete graph in $n$ vertices. Take $vin G$, replace it with a cycle of length $d(v)=n-1$ and connect the $d(v)$ vertices in a 1-to-1 fashion to a vertex of the cycle. The result is that every vertex in the cycle has degree $3$. Repeat this until no vertex of degree $>3$ left. The graph $G$ obtained is $3$-regular and (clearly) $K_nleq G$. Then, $text{TW}(G)geqtext{TW}(K_n)=n-1$. So, the treewidth is unbounded even in the class of $3$-regular graphs.






                          share|cite|improve this answer









                          $endgroup$



                          A simple proof goes this way:



                          Take $K_n$ the complete graph in $n$ vertices. Take $vin G$, replace it with a cycle of length $d(v)=n-1$ and connect the $d(v)$ vertices in a 1-to-1 fashion to a vertex of the cycle. The result is that every vertex in the cycle has degree $3$. Repeat this until no vertex of degree $>3$ left. The graph $G$ obtained is $3$-regular and (clearly) $K_nleq G$. Then, $text{TW}(G)geqtext{TW}(K_n)=n-1$. So, the treewidth is unbounded even in the class of $3$-regular graphs.







                          share|cite|improve this answer












                          share|cite|improve this answer



                          share|cite|improve this answer










                          answered Dec 22 '18 at 17:14









                          Veridian DynamicsVeridian Dynamics

                          1,909312




                          1,909312






























                              draft saved

                              draft discarded




















































                              Thanks for contributing an answer to Mathematics Stack Exchange!


                              • Please be sure to answer the question. Provide details and share your research!

                              But avoid



                              • Asking for help, clarification, or responding to other answers.

                              • Making statements based on opinion; back them up with references or personal experience.


                              Use MathJax to format equations. MathJax reference.


                              To learn more, see our tips on writing great answers.




                              draft saved


                              draft discarded














                              StackExchange.ready(
                              function () {
                              StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3047080%2fexists-a-bound-for-threewidth-in-deltag-leq-3-graphs%23new-answer', 'question_page');
                              }
                              );

                              Post as a guest















                              Required, but never shown





















































                              Required, but never shown














                              Required, but never shown












                              Required, but never shown







                              Required, but never shown

































                              Required, but never shown














                              Required, but never shown












                              Required, but never shown







                              Required, but never shown







                              Popular posts from this blog

                              Bressuire

                              Cabo Verde

                              Gyllenstierna