论文标题
自动化测试和交互式构造不可避免的小路径宽度的图形类别
Automated Testing and Interactive Construction of Unavoidable Sets for Graph Classes of Small Path-width
论文作者
论文摘要
我们提出了一个交互式框架，该框架给定了Graph类$ \ MATHCAL {G} $和数字$ K $的会员测试，并在最多$ k $的$ \ Mathcal {g} $中找到了$ \ Mathcal {g} $的图表的不可避免的集合。我们特别强调了$ \ Mathcal {g} $是一类立方图，并根据此情况量身定制算法。特别是，我们介绍了高度领先的路径分解的新概念，该概念产生了高效的修剪技术。 使用此框架，我们确定所有$ k \ in \ {3，\ dots，10 \} $的路径宽度$ k $的立方图的所有极端围绕值。此外，我们确定所有最小的图形，这些图具有这些极端周长值。作为我们框架的进一步应用，我们表征了路径宽3和周长4的极端立方图。
We present an interactive framework that, given a membership test for a graph class $\mathcal{G}$ and a number $k$, finds and tests unavoidable sets for the class of graphs in $\mathcal{G}$ of path-width at most $k$. We put special emphasis on the case that $\mathcal{G}$ is the class of cubic graphs and tailor the algorithm to this case. In particular, we introduce the new concept of high-degree-first path-decompositions, which yields highly efficient pruning techniques. Using this framework we determine all extremal girth values of cubic graphs of path-width $k$ for all $k \in \{3,\dots, 10\}$. Moreover, we determine all smallest graphs which take on these extremal girth values. As a further application of our framework we characterise the extremal cubic graphs of path-width 3 and girth 4.
