Talk:Hadwiger conjecture (graph theory)
Appearance
Please add
{{WikiProject banner shell}}
to this page and add the quality rating to that template instead of this project banner. See WP:PIQA for details.![]() | Mathematics B‑class Mid‑priority | |||||||||
|
![]() | 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:
| ![]() |
Ambiguity!
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)
- 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 82.108.163.171 (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 (talk • contribs) 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)