Talk:Graph minor

Untitled

Note: "branch sets" are used, but are never defined nor linked to. 71.139.164.223 (talk) 18:30, 21 December 2011 (UTC)

Flamholz's definition works. But it *should* refer to Wagner's theorem. Kuratowski's theorem is similar (and equivalent) but has a different statement. --75.3.130.58 23:57, 5 August 2006 (UTC)

Shouldn't edge deletion be included in the definition of minor?
Peter Kwok 20:22, 2004 Jun 22 (UTC)

I was pretty confused by this omission. The example doesn't make any sense unless you delete edges instead of contracting them. But I'm not an expert ... jrn 15:00, 2005 Apr 5 (UTC)

I agree. Can anybody fix the example (or the definition) please? Now I see; the example actually works, as edge deletions are included in the definition of subgraph. The explanation of the example is confusing, though.
IMHO, the contractions should be done on the subgraph of G obtained by deleting the "oblique" edges, and so it would be better to use a new image too. fudo (questions?) 13:28, 26 April 2007 (UTC)

I changed the definition so that a minor is a graph that can be obtained by edge contraction on a subgraph. This says deletion but more elegantly. It also points the definition of subgraph for clarification. Flamholz 17:26, 2005 Apr 7 (UTC)

Per the page for planar graph, shouldn't this refer to Wagner's theorem rather than Kuratowski's theorem? -- Sendhil 22:51, 7 July 2006 (UTC)

Fixed --- pom 09:51, 1 September 2006 (UTC)

Isomorphic

• In graph theory, a graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained [...]
  • Isomorphic as in Graph isomorphism? --Abdull (talk) 12:11, 28 July 2008 (UTC)
    • Yes. I replaced the link to make this more clear. —David Eppstein (talk) 15:07, 28 July 2008 (UTC)

---

---

Several Errors that Need Fixing

(1) The first sentence should have three words deleted:

"... zero or more edge deletions or edge contractions on a subgraph of G".  
Reason:  Deleting edges results in a subgraph, so we are confusing the reader with overkill.
   

(2) The second sentence may be superfluous given the link in the first sentence.

(3) The second sentence perhaps should read: "Edge contraction is the process of removing a non-loop edge and combining its two endpoints..."

Reasons:  Loops only have one endpoint.  Also, generally in graph and matroid theory,
the contraction of a loop is not defined.  Loops can only be deleted. See comment (6)

(4) Second sentence: The parenthetical phrase is unnecessary, distracting and incorrect. If the phrase does belong there, then it needs to be corrected to:

"...the resulting node has a loop if and only if the either one of the two endpoints has a loop
or the contracted edge is one of at least two multiple edges."
All this suggests that we ought to be pointing out that graph minors resides most naturally in the
context of connected multigraphs.  To stay within graphs, we must either forbid the contraction of
an edge contained in a triangle, or delete any resulting loops/multiple edges.

(5) Third sentence should read: "Alternatively Equivalently, H is a minor of G if a graph isomorphic to H can be obtained...".

Reasons: "Alternatively" should be "Equivalently" since we are not presenting an alternative definition,
just an equivalent restatement (yes, I admit I am being picky here). 
More seriously we must refer to graph isomorphism here (hence the added underlined text), as was done in the first sentence.]

(6) It might be mentioned that the deletion of a cut-edge is also generally not viewed to be a graph minor operation.

Rationale:  A contraction in a matroid always reduces its rank by one, whereas a deletion does not alter its rank.
That is why loops should be deleted rather than contracted and dually, coloops (such as graph cut-edges) 
should be contracted rather than deleted.
Abandoning this tenet when in the context of graphs gains very little and introduces trivial awkwardnesses
(such as leaving the class of connected graphs, or necessitating special considerations in statements and arguments).
Some authors may regard the deletion of a cut-edge to be a legal graph minor operation,
but this operation should be treated with as much caution as the contraction of a loop.

(7) The class of Laman graphs is not minor closed.

For example, the deletion of a single edge in an n-vertex Laman graph results in a graph with fewer than 6n-3 edges.

Luis Goddyn, Mathematics, Simon Fraser University --199.60.17.16 (talk) 22:49, 21 January 2009 (UTC)

I generally agree with all this, but I think leaving the class of connected graphs is a legitimate thing to do, for instance in the context of pseudoforests. Note that in that context there is an issue with what to do with loops, as mentioned in that article — if one only considers minors that are simple graphs, without loops and multiple adjacencies, then there are two forbidden minors with four and five vertices, while if loops are allowed then the forbidden minor characterization is much simpler, the single forbidden minor being a vertex with two loops. Your comments above don't mention edge multiplicity, though — how do you prefer that to be handled? Anyway, it would perhaps be easiest if you just went ahead and made these changes; if others quibble they can modify your edits. —David Eppstein (talk) 23:24, 21 January 2009 (UTC)

Assessment comment

The comment(s) below were originally left at Talk:Graph minor/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.

A diagram showing the process of edge conraction that leads from eth first graph to the second would be useful. General expansion needed, especially applications. Tompw (talk) 15:30, 4 January 2007 (UTC)

Substituted at 18:20, 17 July 2016 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Graph minor. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20090318165333/http://www2.renyi.hu/~p_erdos/1980-10.pdf to http://www2.renyi.hu/~p_erdos/1980-10.pdf

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 17:05, 22 October 2017 (UTC)

Unnecessarily complicated definition?

At present the definition in the article states:

An undirected graph H is a minor of another undirected graph G if a graph isomorphic to H can be obtained from G by contracting some edges, deleting some edges, and deleting some isolated vertices. (emphasis mine)

Is there some reason this cannot be simplified to the following?

An undirected graph H is a minor of another undirected graph G if a graph isomorphic to H can be obtained from G by contracting some edges and deleting some edges and vertices.

This definition can be obtained easily from the first as you can isolate any vertex you want by deleting all the edges leading to it, and then delete the isolated vertex. So the former definition seems unnecessarily complicated. --Saforrest (talk) 10:10, 19 October 2020 (UTC)

Graph major

RFC on the topic of graph majors, which are graphs that contain G as a minor, and can be constructed from G by INSERTing edges and vertices, and EXPANDing edges.

Darcourse (talk) 06:00, 16 December 2021 (UTC)

More Entries under Variations

Butterfly minors and strong minors are fairly major types. They are discussed in many publications, but don't appear in the list of common variations. A recent paper discussing how they could be applied to digraphs is here, and has the virtue of containing many references to classic undirected theory. [1] (also available on arxiv). Someone with more experience than me will need to discuss strong minors, but butterfly minors are created by either 1) deleting an edge, or 2) contracting an edge (a,b) if it is either the only only outgoing edge of a or the only incoming edge of b Oceanchaos (talk) 05:25, 11 August 2022 (UTC)