Talk:Hadwiger conjecture (graph theory)

A fact from Hadwiger conjecture (graph theory) appeared on Wikipedia's Main Page in the Did you know column on 28 May 2008, and was viewed approximately 4,500 times (disclaimer) (check views). The text of the entry was as follows:

Did you know... that mathematician Paul Erdős called the Hadwiger conjecture, a still-open generalization of the four-color problem, "one of the deepest unsolved problems in graph theory"?

A record of the entry may be seen at Wikipedia:Recent additions/2008/May.

Wikipedia

Ambiguity![edit]

The article says:

if an undirected graph G requires k or more colors in any vertex coloring, then one can find k disjoint connected subgraphs of G such that each subgraph is connected by an edge to each other subgraph.

Sigh.

What does "any" mean?

Does it mean

if there is any vertex coloring that requires k or more colors, then.......

or does it mean

Suppose any vertex coloring requires k or more colors. Then.......

The first means "there is at least one"; the second means "for every". If the latter is meant, then "any" should be changed to "every". Michael Hardy (talk) 06:59, 10 February 2009 (UTC)[reply]

Only one of those two meanings makes any sense. But I've reworded it to (I hope) remove any ambiguity. —David Eppstein (talk) 07:16, 10 February 2009 (UTC)[reply]

For "any" read "each". A k-chromatic graph has at least one k-colouring but may have and usually does have many k-colourings. —Preceding unsigned comment added by 82.108.163.171 (talk) 06:04, 28 March 2009 (UTC)[reply]

I don't feel that David Eppstein is THE expert, unless he has... first,... an answer, and second,... a proof! I know why the graph on the demonstrated page has no more than 4 disjoint proper subgraphs; I have a simple formula. He's just a moderator that someone has chosen to rebut the simple questions. —Preceding unsigned comment added by Leavemsg2 (talk • contribs) 22:28, 26 November 2010 (UTC)[reply]

In case anyone else was wondering, as I was, about the context for this little outburst: see Talk:Crossing number (graph theory)#I have proven the both Guy's and Zarankiewicz's guesses are right!. —David Eppstein (talk) 06:01, 27 November 2010 (UTC)[reply]

again, Eppstein is NOT AN EXPERT; here's the proof. this problem is NOT very hard. theorem: if 2E >= 3V, then Hadwiger's conjecture is true. proof: assume 2E < 3V; if we let V= 4, then E < 6, and the complete graph, K4, could have no more than 5 edges and wouldn't require 4 differently-colored vertices. if 2E >= 3V, then using Euler's characteristic, 2V -2E +2F = 4, and by substitution 2F -V >= 4; also, 6F -3V >= 12, -2E < -3V, and 3F -E >= 6; thus, {3F -E >= 6} minus {2F -V >= 4} implies that V -E +F >= 2; thus, if the graph is "at least" planar, V >= 4, and 2E >= 3V, then Hadwiger's conjecture is absolutely valid. you can view it at... www.oddperfectnumbers.com. I'm not trying to find fault with David, but the reason why this problem has remained un- solved for so long is simple-- if a Mother duck runs out into traffic, then all of her chicks are sure to follow. *QED 03/4/2012 —Preceding unsigned comment added by 99.118.131.124 (talk) 20:27, 5 March 2012 (UTC)[reply]

(1) This is not the place to publish proofs, or even to discuss proofs that have not been reliably published, because we can't include the material in the article until it has been published; (2) What makes you think Euler's characteristic is applicable in that form to graphs that might not be planar? —David Eppstein (talk) 21:54, 5 March 2012 (UTC)[reply]

I know... that's not I think, or I hope, etc. The math facts are telling me that if V -E +F >= 2, then the only possible residual graphs are the complete graph, K4, a solid tetrahedron, or a square with diagonals that cross but don't form a vertex. Examine them for yourself; that's not difficult. —Preceding unsigned comment added by 99.118.131.124 (talk) 02:12, 6 March 2012 (UTC)[reply]

Bill, would you please sign your posts in the conventional way - Thanks! — MFH:Talk 20:12, 5 May 2013 (UTC)[reply]

Infinite Result[edit]

The result of Van der Zypen on the conjecture for infinite graphs shouldn't really be mentioned here for a number of reasons. The first point is the result was already known. For example, Diestel (in the paper "Simplicial decompositions of graphs") cites the result as being in Halin's book "Graphentheorie II", I think even as an exercise, although I can't find a copy.

The second point is that the content of the paper, which is an unpublished preprint, is a very obvious counterexample. Take the disjoint union of a clique of size n for each natural number n, this graph clearly doesn't have finite chromatic number, but also has no infinite component and so no infinite clique minor.

(Technically, Van der Zypen shows a little more, that you can take the graph to be connected, but that is just achieved by joining the cliques together along a ray) — Preceding unsigned comment added by 134.100.221.55 (talk) 07:56, 18 June 2018 (UTC)[reply]