Talk:Pathwidth

Strahler number

The pathwidth of a tree is almost the same thing as its Strahler number, right? Can this observation be sourced, adequately enough to include it in the article? —David Eppstein (talk) 17:31, 1 April 2009 (UTC)

(Much later): they still seem to be closely related, but they are definitely not identical, and the connection doesn't seem to be strong enough (or well sourced enough) to include in the article. —David Eppstein (talk) 00:42, 6 May 2010 (UTC)

Alternative definition

In section 2.4 of their book, Bondy and Murty provide a different definition for path decomposition. (This link might show you the page in question.) It's actually a *very* loose (and less interesting) definition of decomposition; they include any family of edge-disjoint subgraphs such that every edge belongs to one of the subgraphs.

• If the subgraphs are all paths, it is a "path decomposition".
• If the subgraphs are all cycles, then it's a "cycle decomposition".

They then give "Veblen's theorem" that says (just like necessary and sufficient conditions for the existence of an Eulerian circuit), a graph may have a cycle decomposition iff every vertex has even degree. (The current article has little to do with this definition of "cycle decomposition".) Justin W Smith ^talk/_stalk 05:04, 8 May 2010 (UTC)

If it's worthy of an article, it should be a separate article, as it's not particularly related (no more related than any other two subjects in graph theory). Actually, I've used something like this kind of "path decomposition" in this paper under the keyphrase linear arboricity (useful fact: any graph of maximum degree three can be decomposed into two subgraphs that are disjoint unions of paths). —David Eppstein (talk) 05:16, 8 May 2010 (UTC)

I removed the wikilink to Cycle decomposition (graph theory) from "See also". It doesn't really belong here unless there exists a definition of "cycle decomposition" that is more closely related. Perhaps the "See also" section is not needed.(?) Justin W Smith ^talk/_stalk 05:27, 8 May 2010 (UTC)

Strangely, the definition given on Cycle decomposition (graph theory) doesn't even match that of Bondy & Murty. (I've often heard that graph theory terminology is inconsistent, and evidence supporting this claim seems abundant!) I'll need to find multiple sources whose definitions agree with Bondy & Murty. It's disappointing that B&M appear to not even discuss the more common "path decomposition". Justin W Smith ^talk/_stalk 05:42, 8 May 2010 (UTC)

B&M was first published in 1976; Robertson and Seymour's work defining path decompositions was first published in 1983. —David Eppstein (talk) 06:27, 8 May 2010 (UTC)

I think you're right. B&M would have a strong interest in using terminology consistent with their previous work. (I don't have a copy of their earlier book so I can't verify this.) Assuming they defined "decomposition" in their earlier work, they could claim *precedence* for the term. Luckily, usage of terminology in this field appears to be based more on utility and interest, than on *precedence* Justin W Smith ^talk/_stalk 05:17, 9 May 2010 (UTC)

I few more things I want to note here:

1. B&M say, on the following page (still in section 2.4), that a "decomposition" is the same as a "uniform 1-cover". They then extend their concept to a "k-cover".
2. This "covering" is, again, a confusing term since it's incompatible with the well-known terms edge cover and vertex cover. There's also the unrelated Covering graph.
3. The article, Edge cycle cover, is the only place I can find a discussion of uses B&M's type of "cover". Its companion concept, Edge path cover, apparently doesn't have an article. I also just found Cycle double cover which is the same "cover". Covering (graph theory) was useful in finding this one. (05:21, 9 May 2010 (UTC))
4. It might be appropriate to create an article named "k-cover (graph theory)" to discuss B&M's concept. (The article above, Edge cycle cover, should probably, then, be a section within this more general article.)
5. Another common graph theory textbook (by Diestel, available online here; see page 339 – or 350 in the PDF) follows the terminology used here.

Justin W Smith ^talk/_stalk 05:17, 9 May 2010 (UTC)

Poorly Writen Introduction

The introduction to this article is absolutely absymal. After reading it I was so frustrated with the poor quality of the introduction that I seriously considered rewriting this myself, which I don't ever do. Pathwidth and path decomposition are two distinctly different concepts and should be treated as such. You should remove all reference to pathwidth in the introduction and form its own section or its own page. At the very least, give it a separate sentance.

Better would be something more like this:

In graph theory a path-decomposition is a sequence of subsets of vertices of a graph such that the endpoints of each edge appear in one of the subsets and such that each vertex appears in a contiguous subsequence of the subsets.[2] Path-decompositions are closely analogous to tree decompositions. They play a key role in the theory of graph minors.

66.87.4.250 (talk) 06:35, 26 December 2012 (UTC)

So you would propose to (1) remove any intuition from the start of the article, instead making the first sentence as technical as possible, and (2) treat pathwidth as such an unimportant tangent to the main topic that it shouldn't even be mentioned in the lead section (note: it's not exactly an introduction)? Neither of those things strikes me as particularly likely to be an improvement, but I'm open to persuasion. It might help if you explained in much more specific terms what you dislike about the current version and why. Vague phrases like "absolutely abysmal", "poor quality", "poorly written" are not particularly helpful in communicating to others your reasons for wanting this rewritten. —David Eppstein (talk) 07:42, 26 December 2012 (UTC)