Talk:Graph coloring

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: B Class High Priority  Field: Discrete mathematics

Contents

[edit] Embedded TeX

On Wikipedia, TeX looks very good when "displayed", thus:

\int_0^\infty 1\,dx

but horrible when embedded in lines of text. Contrast χ(G) with χ(G). If I live forever, I may go through this article and correct it, but in the mean time, maybe those who have been tending to this article can beat me to it. Michael Hardy 21:57, 21 May 2004 (UTC)

OK, I think I've fixed everything. —Caesura(t) 13:22, 25 Apr 2005 (UTC)

To the contrary - As Nils Grimsmo pointed out to me, usage of the <math> tag is, by default, only rendered with TeX if the expression is sufficiently complicated. If it's simple, it will display in a textual manner which still looks better than the regular plain text. You can change this in the math section of your user preferences if you do not like how your math is being rendered. So, it's mostly best to go with using math tags everywhere, and let the viewer decide what works best. ~ Booya Bazooka 09:20, 17 December 2006 (UTC)

[edit] Problem classification

"The problem of finding a minimum coloring of a graph is NP-hard. The corresponding decision problem (is there a coloring which uses at most k colors?) is NP-complete."

If the decision problem is NP-complete, and there are only N possible answers, doesn't that mean finding a minimum coloring is also NP-complete?

--Dfeuer 00:30, 25 December 2005 (UTC)

No. Only decision problems (problems with yes/no answers) can be NP-complete. However, there are reductions that solve the function problem using the decision problem with a certain number of queries, and this can be used to prove that the function problem lies in a certain class of function problems. For example, binary search will allow you to find the chromatic number with a logarithmic number of queries of the form is there a coloring which uses at most k colors?, which shows that it lies in PNP[log] (see this class at Complexity Zoo). I don't know how many queries you need to actually find a graph coloring, but I'm pretty sure a linear number is enough. Deco 04:29, 25 December 2005 (UTC)
actually, loagrithmic time is enough. In the first run, you find an upper bound by querying 1,2,4,8,16... and then you do a binary search. Honnza 19:12, 12 May 2006 (UTC)
That comment of Deco referred to finding an actual colouring, not to finding the chromatic number. McKay 07:36, 17 May 2006 (UTC)

[edit] k-colorable

The usual meaning of "k-coloring" and "k-colorable" is that there are k colors available, but there is no requirement that each color is actually used. This is frequently unclear in formal definitions but I believe it is what most graph theorists understand. An example from this page where it matters is "If all finite subgraphs of an infinite graph G are k-colorable, then so is G." - this would be vacuous if "k-colorable" required use of all colours (consider the subgraphs with fewer than k vertices). McKay 07:29, 17 May 2006 (UTC)

[edit] graph coloring and maximal clique

(copied from Reference desk, should be incorporated in article probably)

Is there an undirected graph for which the chromatic number exceeds the maximal clique size by more than one?

--Henning

Yes. Mycielski proved in 1955 that for every k\ge1 there is a graph with chromatic number k that contains no triangle subgraphs, that is, whose maximal clique size is just 2. I'll make a drawing of such a graph with chromatic number 4 in a minute. —Bkell (talk) 10:24, 3 July 2006 (UTC)
—Bkell (talk) 10:34, 3 July 2006 (UTC)
Mycielski's proof is actually a constructive proof, so you can use it to make a graph with as large a chromatic number as you like with a maximal clique size of only 2. —Bkell (talk) 10:43, 3 July 2006 (UTC)
J. Mycielski. Sur le coloriage des graphes. Colloq. Math., 3:161–162, 1955. —Bkell (talk) 10:51, 3 July 2006 (UTC)

Thanks a bunch! :)

[edit] Chromatic number and maximal degree

The page says the chromatic number is Δ(G)+1 only when the graph is complete or an odd cycle. It seems that this assumes the graph is connected. If you have a graph whose connected components are all odd cycles or all complete graphs of the same size then the chromatic number and maximal degree are the same as they would be for one component, and so this is another case where the chromatic number is Δ(G)+1.

- Quite right; this is Brooks' Theorem and seems to be included correctly now. Adking80 20:12, 13 July 2007 (UTC)

[edit] For topolgy

I read from Martin Gardner that chromatic number is the maximum regions that can be drawn where every region touches every other region. Joerite 04:44, 1 October 2006 (UTC)

I also think that maximal chromaticity of any downwards closed family of graphs (as are graphs ebbeddable on a ___) is equal to the size of the largest Kn belonging to the family, or equally, that any graph not containing Kn are (n-1)colorable. Proof for one to three colors is straightforward. But I'm not sure on K5-forbidden graphs (the non-planar ones) and higherHonnza 12:55, 14 January 2007 (UTC)

It sounds to me like you're talking about Hadwiger's Conjecture, which posits that a graph is (k-1)-colourable unless it contains a K_k minor. This has been proven for k at most six. Adking80 20:16, 13 July 2007 (UTC)

[edit] Graphs only?

Would we want to extend this article to include colorings of the (positive) integers? Or perhaps have another article (linked to the Coloring disambig) wherein colorings on structures besides graphs are explained and/or defined? It would be helpful for things like Van der Waerden's theorem. If anybody wants to add a paragraph or something, go ahead, or I could; but I'd want a go-ahead, since I haven't contributed to or watched this article before. -- 149.43.x.x 07:02, 13 December 2006 (UTC)

Since this article is called Graph coloring, it should clearly go to another article. But feel free to create one. --Mellum 11:31, 16 December 2006 (UTC)

[edit] Computing the chromatic polynomial

Perhaps someone who understands this a bit better can help to clarify this section, because it seems a bit unclear. The confusing bit is how the text refers to e, "the edge". What edge? Just any arbitrary edge, no matter which edge is chosen? I have a small amount of experience with the deletion-contraction algorithm (just used it on simple cycle graphs Cn) and still don't fully understand the article text, so I really don't think it's layperson-friendly enough. ~ Booya Bazooka 09:14, 17 December 2006 (UTC)

[edit] New page on Discharging Method

I recently created a page on the Discharging Method. Would anyone be willing to read it any and give some feedback? Thanks. Ptrillian 07:26, 2 January 2007 (UTC)

[edit] Definition of "proper"

Most pages on specific colorings seem to have to define the term proper. This is not very nice and also detracts IMO from the legibility of definitions. Is it worth creating a separate page to define proper colorings (or maybe just have a distinct section of this article - can you link to them specifically in wiki markup?) that other pages can link to? —Preceding unsigned comment added by 129.132.208.80 (talk • contribs) 12:48, 7 February 2007

[edit] Interpretations of chromatic polynomials with complex roots

Could something perhaps be added with respect to chromatic polynomials with complex roots, such as the cp of the petersen graph?

[edit] Tutte polynomial etc.

The Tutte polynomial of a matroid might be worth mentioning, since it's a sort of generalization of the chromatic polynomial. LDH 05:05, 14 April 2007 (UTC)

[edit] Welsh and Powell - note

Could someone find a better example to illustrate the non-optimality of Welsh-Powell algorithm? The example with the star is plainly wrong... Making the steps of the algorithm listed in the article will color the star with 2 colors. —The preceding unsigned comment was added by 83.131.41.128 (talk) 17:11, 1 May 2007 (UTC).

[edit] Colouring Squares, Triangles and Hexagons

query - is this the correct article for this item -

The 2-section-Square in 2 colours has 3 forms (a2, ab, b2); at 3 colours there are 6 forms; at 4 colours there are 10 colours. The numbers alter if rotational or reflection variants are or are not allowed.

The 4-section-Square in 2 colours has 6 forms; in 3 colours there are 24 forms;

The 3-section-Triangle in 2 colours has 4 forms; in 3 colours it has 13 forms depending as to whether 'abc' is "the same" as 'acb'.

The 6-section-Hexagon in 2 colours has 13 forms;

There are opportunities for using these to make puzzles and for other recreational mathematics JK-Salisbury 86.160.138.236 (talk) 14:08, 3 June 2008 (UTC)

You want to count the number of different colorings of small cycle graphs? The closest I can think of to a correct article for that would be chromatic polynomial, although it does not factor out the symmetries. —David Eppstein (talk) 14:49, 3 June 2008 (UTC)