Talk:Hadwiger conjecture (graph theory)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated B-class, Mid-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
B Class
Mid Importance
 Field: Discrete mathematics


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.


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)

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)
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 (talk) 06:04, 28 March 2009 (UTC)

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 (talkcontribs) 22:28, 26 November 2010 (UTC)

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)

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... 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 (talk) 20:27, 5 March 2012 (UTC)

(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)

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 (talk) 02:12, 6 March 2012 (UTC)

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