(Translated by https://www.hiragana.jp/)
Talk:Hadwiger conjecture (graph theory) - Wikipedia Jump to content

Talk:Hadwiger conjecture (graph theory)

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Ideogram (talk | contribs) at 11:41, 27 February 2012 (i really don't think graph theory should be considered part of computer science). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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.
WikiProject iconMathematics B‑class Mid‑priority
WikiProject iconThis 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.
BThis article has been rated as B-class on Wikipedia's content assessment scale.
MidThis article has been rated as Mid-priority on the project's priority scale.

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)[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 (talkcontribs) 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]