most recent 30 from http://mathoverflow.net 2013-05-19T00:10:37Z http://mathoverflow.net/feeds/question/48197 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/48197/the-girthwidth-of-a-graph Suresh Venkat 2010-12-03T17:29:02Z 2010-12-06T07:43:47Z

<p>Abstractly, tree/path decompositions of a graph $G$ can be thought of as doing the following:</p> <ul> <li>fix a "skeleton" class of graphs (tree or path)</li> <li>Pick a member of this class $H$. Associate with each node of $H$ a subset of vertices of $G$ such that (1) For each edge $e = (u,v)$ in $G$, there exists a node of $H$ containing both $u$ and $v$ and (2) the set of nodes of $H$ containing a fixed vertex of $G$ form a connected subgraph</li> <li>minimize the maximum cardinality of the set associated with a node of $H$, over all such associations and skeletons. </li> </ul> <p>Suppose that rather than choosing a tree or a path, we are allowed to pick any graph of girth at least $g$, for some fixed parameter $g$. Is there anything known about the resulting "girthwidth" of a graph ? </p>

http://mathoverflow.net/questions/48197/the-girthwidth-of-a-graph/48423#48423 Aaron Meyerowitz 2010-12-06T07:43:47Z 2010-12-06T07:43:47Z

<p>The (finite) "girthwidth" is always 1 so this is not going to be that useful (as defined here anyway). First some notation: Let a $g$-decomposition of a graph $G$ consist of a graph $H$ with girth at least $g$ and an assignment to each node of $H$ of a set of vertices as above, the width of such a decomposition be one less than the maximum number of vertices assigned to any node of $H$, and $w_g(G)$ be the minimum width of any $g$-decomposition of $G$. Then $w_3(G)$ is the minimum width where $H$ is completely unrestricted. So $w_3(G)=1$ as we can take $H$ to be a complete graph and put the endpoints of each edge in their own node. Since the girth of a tree is infinite a tree decomposition is an $\infty$-decomposition and the tree width is $w_{\infty}$. Actually these are the only widths that matter since $w_3=w_b \le w_{\infty}$ for any finite $3 \le b$: If $a \lt b \le \infty$ then $w_a \le w_b$ simply by the definitions. However if $a \lt b \lt \infty$ then also $w_b \le w_a$ since we can turn an $a$-decomposition into a $2a$-decomposition by putting a new node in the middle of each edge and assigning it the same vertex set as one of its neighbors. </p> <p>Maybe one could restrict to $H$ being a planar graph although $w_3(G)$ would still be 1 for planar $G$. I wonder when the "cycle-width" is less than the path-width. If one demands that no two nodes get the same vertex set (which is no restriction for tree width) it would get harder (and sometimes impossible if we forbid empty nodes)</p> <p>A use of tree-width is that many hard (NP complete, say) problems become easy (say polynomial time) when restricted to bounded tree-width. A variant width could be justified merely by its own intrinsic appeal, but would be more motivated if it had similar applications.</p>