Talk:Graph coloring

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated B-class, High-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
High Importance
 Field: Discrete mathematics
WikiProject Computer science (Rated Mid-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles 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.
 ???  This article has not yet received a rating on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.
 


Running Time[edit]

Source for the claims in the info box? All I found was: http://www.cs.lu.se/home/Thore_Husfeldt/papers/xsat.pdf


A graph’s chromatic number is the smallest integer � � n such that there is a mapping V ! {1, . . . , �} that gives different values (‘colours’) to neighbouring vertices. This is a well-studied problem with a rich history of exponential-time algorithms.

We provide two such algorithms, based on divide-and-conquer in time O(8.33n), and based on

inclusion–exclusion in time O(2.4423n). —Preceding unsigned comment added by Voyager2378 (talkcontribs) 01:49, 23 April 2010 (UTC)

I think the paper you're looking for is http://www.cs.lu.se/home/Thore_Husfeldt/papers/Set_partitioning_via_inclusion-exclusion.pdf (published in SIAM J. Computing 2006). I'm not sure why it isn't cited in the article or mentioned in the text of the article, though. —David Eppstein (talk) 03:03, 23 April 2010 (UTC)
False modesty. I did some soul-searching with respect to including references to my own work, and left some parts in a messier state than I should. Thore Husfeldt (talk) 06:43, 23 April 2010 (UTC)
Thank you. BTW I'am very bad at editing... but IMHO somebody should put the reference next to the running time:O(n*2^n) in "the info box". I know that it is in the text. Just a suggestion. —Preceding unsigned comment added by 94.253.171.1 (talk) 21:32, 23 April 2010 (UTC)

Embedded TeX[edit]

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

Problem classification[edit]

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

Computational Complexity[edit]

The article currently says "Graph coloring remains NP-complete even on planar graphs of degree at most 4 [with reference to Garey and Johnson]." It should be improved to read "Graph coloring remains NP-complete even on planar graphs of degree 4 [with reference to David P. Dailey: Uniqueness of Colorability and Colorability of Planar 4-regular Graphs are NP-complete. Discrete Mathematics 1980, 30:289-293. ].David.daileyatsrudotedu (talk) 11:54, 21 August 2009 (UTC)

Please go ahead and make that change — see WP:Be Bold. —David Eppstein (talk) 13:56, 21 August 2009 (UTC)

k-colorable[edit]

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)

graph coloring and maximal clique[edit]

(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)
Grötzsch graph.svgBkell (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! :)

Chromatic number and maximal degree[edit]

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)

For topology[edit]

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)

Graphs only?[edit]

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)

Computing the chromatic polynomial[edit]

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

New page on Discharging Method[edit]

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)

Definition of "proper"[edit]

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 (talkcontribs) 12:48, 7 February 2007

Interpretations of chromatic polynomials with complex roots[edit]

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

Tutte polynomial etc.[edit]

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)

Welsh and Powell - note[edit]

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

Colouring Squares, Triangles and Hexagons[edit]

query - is this the correct article for this item - I am looking for a section on 'recreational maths puzzles'.

The 2-section-Square

With 2 colours has 3 forms (a2, ab, b2).

With 3 colours there are 6 forms ( as above plus ac, bc, c2)

With 4 colours there are 10 forms (as above plus ad, bd, cd & d2);


The 4-section-Square

The opportunities for recreational patterning vary considerably depending if the square is divided diagonally or orthogonally. The numbers alter if rotational or reflection variants are or are not allowed.

With 2 colours has 6 forms; (a4, a3b, a2b2, ab3, b4 & abab);

With 3 colours there are 24 forms (of which 3 are reflections);

With 4 colours there are 66 forms (of which 12 are reflections). There are 6 forms which use all 4 colours.


The 3-section-Triangle

With 2 colours has 4 forms; (a3, a2b, ab2, b3);

With 3 colours it has 13 forms depending as to whether 'abc' is "the same" as 'acb'.

As with the 4-section square, the patterns vary depending whether the triangle is divided corner-wise or edge-wise.


The 6-section-Hexagon

With 2 colours has 13 forms;

a6; a5b; a4b2; a3b3; a2b4; ab5; b6 plus the 'middle 3' variants aabaab & abaaab; aababab & abbaab; abbabb & ababbb.

As an example of a recreational maths puzzle, these thirteen hexes can be fitted with edge-matching into what shapes?

With 3 colours and depending on the reflection rules adopted - there are 76 variants.

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 & 27 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)

Loop cannot be legally colored?[edit]

What does this mean : "Whenever G contains a loop, it cannot be legally colored at all" ? —Preceding unsigned comment added by 72.48.91.143 (talk) 16:45, 16 July 2008 (UTC)

Both endpoints of a loop are the same vertex, so it is impossible for the loop to have different colors at its endpoints. —David Eppstein (talk) 16:51, 16 July 2008 (UTC)

Graph coloring = vertex coloring, other comments[edit]

Graph coloring
3-coloringEx.svg
Problem
Input Graph G with n vertices. Integer k
Output Does G admit a proper vertex coloring with k colors?
Algorithms
Running time O(2^nn)
Complexity NP-complete
Garey–Johnson GT4


Chromatic number
Problem
Input Graph G with n vertices.
Output \chi(G)
Algorithms
Running time O(2^nn)
Complexity NP-hard
Garey–Johnson GT4
Approximable O(n(\log n)^{-3}(\log\log n)^2)
Not approximable n^{1-\epsilon} unless P=NP
Chromatic polynomial
Graph with all three-colourings 2.svg
Problem
Input Graph G with n vertices. Integer k
Output The number P(G,k) of proper k-colorings of G
Algorithms
Running time O(2^nn)
Complexity #P-complete
Approximable FPRAS for restricted cases
Not approximable No PTAS unless P=NP


I’ve looked at this page from the outside of a long while, and think the topic could make a wonderful and quite accessible article. There are some things I’d like to do, but at least one of them is potentially contentious because it’s the defining first sentence, so I’d better take it up here first: currently the article’s first definition is agnostic about which elements of the graph are coloured (edges, vertices, or both). This is the proper “mathy” way of doing it, I understand that it’s tempting to be as general as possible, but 99% of the article, and most other occurrences of the term, refer specifically to vertex colouring. So I’d like the article to define graph colouring as vertex colouring and leave the variants (edge colouring, general graph labelling) out of the introduction. (Of course they should appear later.)

Specifically, the first sentences could be whittled down to this:

In graph theory, a graph coloring is a way of coloring the vertices of a graph such that no two adjacent vertices share the same color.

(If we’re looking for outside sources, many textbooks use that definition anyway. Toft and Jensen, for example.)

The sections on chromatic polynomials and the list of variants are comparatively long and detailed, so maybe these could be moved to separate articles eventually. Let me also announce that sooner or later I may reach a Citing oneself conflict of interest in the algorithms section. Thore Husfeldt (talk) 09:59, 2 December 2008 (UTC)

Should we do infoboxes? Horse and helium and sheet bends have them. Should computational problems? I’m not sure. Currently they’re just tables instead of proper infobox templates. What I like is that it displays useful information in a compact as accessible fashion. Argument against would be that the whole article is in danger of placing undue emphasis on the algorithmic aspect of the problem. Comments? Thore Husfeldt (talk) 09:56, 11 December 2008 (UTC)

I like the idea of having infoboxes for computational problem. In addition to the "algorithmic" information that you have in your examples, I suggest that we add more "combinatorial" information that interlinks different problems. (For example, the infobox for clique could tell that it is equal to independent set in the complement graph. The infobox for dominating set could tell that a maximal independent set is a dominating set. The infobox for vertex cover could tell that it is a special case of set cover. The infobox for edge coloring could refer to vertex coloring in the line graph, etc.) To save some space, it might be a good idea to combine the infoboxes for graph coloring & chromatic number (and domatic partition & domatic number, etc.) – after all, many (algorithmic) results are related to both of them. One question: would you put the infobox on the Dominating set page or on the Dominating set problem page or both? There are several similar cases where there are two pages for one problem. — Miym (talk) 12:05, 11 December 2008 (UTC)
Ad your question: looking at a few examples, I can’t actually see a good reason why Dominating set and Dominating set problem are different pages, nor Covering (graph theory) and Vertex cover problem. I think that the Graph coloring algorithm is a much better model for how these things should be organised. Thore Husfeldt (talk) 14:14, 11 December 2008 (UTC)
I absolutely agree with you; many things (reading, editing, linking) would be easier if we always had just a page "X" and not "X problem". Unfortunately some people seem to oppose merging "X" and "X problem"; see, e.g., Talk:Independent set problem. — Miym (talk) 14:52, 11 December 2008 (UTC)
The opposition seems be regarding merging Foo to Foo problem. But lets see. I’ll start the merger proposal again. Thore Husfeldt (talk) 20:45, 14 December 2008 (UTC)

Distributed graph coloring?[edit]

Should we mention distributed (or parallel) algorithms for graph coloring here? I was thinking about classics like the Cole–Vishkin (1986) algorithm for 3-coloring an n-cycle in O(\log^* n) time, and Linial's (1992) seminal \Omega(\log^* n) lower bound. One could also briefly mention some generalisations that give a distributed (\Delta+1)-coloring in poly(\Delta) + O(\log^* |V|) time. — Miym (talk) —Preceding undated comment was added at 21:35, 17 December 2008 (UTC).

That, and on-line graph coloring. Go ahead. Thore Husfeldt (talk) 05:45, 18 December 2008 (UTC)
Yes please. :-) I'll review the new content. Dcoetzee 22:48, 18 December 2008 (UTC)

Order of references?[edit]

What is the order of references in the end of the page? Should it be alphabetical or the order of reference or something else? Miym (talk) 20:53, 21 December 2008 (UTC)

Alphabetical. I tried to clean them up, but didn’t sort them, because I hoped to find a tool that would do just that for me. Thore Husfeldt (talk) 21:23, 21 December 2008 (UTC)
I don't know of a lot of tools for working with Wikipedia bibliography templates. There's http://zeteo.info/ but I think that's more for individual bibliographies than sorting whole bibliography sections. I have an application I wrote myself that can read and write bibtex files, edit entries in them, and convert to and from the Wikipedia citation templates — it doesn't currently know how to spit out more than one template at a time, but it does know how to sort people by last name, so likely it could be made to work for this task as well. Just a small matter of programming. But the user interface only works on OS X versions 10.5 or greater and though I'd be happy to share it individually I don't think it's ready for public distribution yet. —David Eppstein (talk) 21:45, 21 December 2008 (UTC)

New Algorithm Solves The Colouring Problem An Order Of Magnitude More Quickly[edit]

...or should that be the counting problem? Somebody with a more detailed understanding can correct me if necessary. It appears to use graph theory algebra to achieve the claimed result. There's an overview article here: http://www.physorg.com/news153588084.html and there's a PDF containing more detail about how the algorithm works at http://www.iop.org/EJ/article/1367-2630/11/2/023001/njp9_2_023001.pdf New Thought (talk) 22:04, 12 February 2009 (UTC)

This looks like a legitimate paper, but it's about the counting version of the problem (which is much more difficult), not the decision version. See Sharp P for more details. Dcoetzee 22:36, 12 February 2009 (UTC)
... or to Tutte polynomial, where I already wrote a section on computation, since the paper essentially solves the general problem. But from a brief look, I find it difficult to summarise the contribution of the linked result -- especially, I could not quickly find a description of what they compare their performance to. Thore Husfeldt (talk) 06:17, 13 February 2009 (UTC) Later edit: scratch that. It would belong to the Algorithms section of Chromatic polynomial. Thore Husfeldt (talk) 08:26, 13 February 2009 (UTC)

NP-completeness of planar 3-colorability, attribution[edit]

The attribution for NP-completeness for 3-colorability of planar graphs of degree 4 was changed from Garey, Johnsson, Stockmeyer to Dailey. I don’t have online access to the Discrete Mathematics volume from 1980 (I could get that tomorrow.) Is the improvement in the Dailey-paper the restriction to regular graphs? Thore Husfeldt (talk) 10:45, 26 August 2009 (UTC)

See above discussion under Computational Complexity . The change was indeed because of the restriction to regular graphs of degree four. I can restrict it further to regular graphs of degree four which have a tangle number of one (citing my dissertation of 1978), but that gets a little esoteric for the purpose I think. David.daileyatsrudotedu (talk) 04:22, 22 December 2009 (UTC)

Brute Force search[edit]

I can't believe the formula, \scriptstyle\binom{n}{k}, given here for the number of possible assignments, valid or not, of k colors to n nodes. Note that this evaluates to 2(n-1)/2 for the case k = 2, instead of the 2^n-2 I would expect. Shouldn't the number be something like k^n, for assigning at most k colors, or like \sum_{i=0}^{k}\binom{k}{i}{(k-i)}^{n}{(-1)}^{i} for assigning exactly k colors?--192.4.227.200 (talk) 19:27, 19 October 2009 (UTC)

You're right. I think the original editor meant \left\{\begin{matrix} n \\ k \end{matrix}\right\} (Stirling numbers of the second kind). I'm still not sure how the O(n!) upper bound arises though, since the brute force algorithm should stop when a valid colouring is found, having time complexity O(kn) at most. I'm editing the article to reflect this, someone correct me if I'm wrong. --Robin (talk) 03:41, 20 October 2009 (UTC)
On second thought, computing the Chromatic polynomial is not the same as computing the Chromatic number. I've left the upper bound as it is, but I've changed the n choose k to n brace k, which is what the editor probably meant in the first place. --Robin (talk) 03:50, 20 October 2009 (UTC)
Strange indeed. I suspect these are my own descriptions; I don’t know what I was thinking. I’ll replace the description by something simpler. Thore Husfeldt (talk) 09:47, 20 October 2009 (UTC)

TeX solecisms[edit]

My comments above stand, and in the mean time I've found a bunch of stuff like this:

\chi (G) \, \Delta (G) \,

This should look like this:

\chi (G) \le \Delta (G) \,

Michael Hardy (talk) 20:03, 24 October 2009 (UTC)

I agree that mixing TeX and html like this is wrong, but for this particular example, what's wrong with formatting it in pure HTML, e.g.
χ(G) ≤ Δ(G)
? That way the formula size matches the text size rather than being (in my browser) about twice as tall. —David Eppstein (talk) 21:25, 24 October 2009 (UTC)

Placement of pictures[edit]

The article contains this large picture:

Chromatic polynomial of all 3-vertex graphs.png

It was placed on the left. I've changed the placement to the right side, and rearranged its placement. I think its distracting to have it on the left. Also, I believe we could decrease the height of this picture by displaying the Y-axis only up to 20, instead of 30. Any comments on the rearrangement / reduction of image size? --Robin (talk) 19:50, 3 November 2009 (UTC)


Color/Colour[edit]

Given the history of the four colour problem, and the early study of similar problems being a practically solely English thing, why is this article spelt the american way? —Preceding unsigned comment added by 134.219.202.104 (talk) 11:02, 1 April 2010 (UTC)

Because the first major contributor used American English. See WP:ENGVAR. VMS Mosaic (talk) 02:11, 2 April 2010 (UTC)
You're never going to win this one. I am currently submitting a paper which is full of American spellings and it kills me! Unfortunately colorability as a computational problem has been a largely american endeavour, and the entire mathematical community with the exception of Britain and Canada seem to have accept color as standard. My coauthor is Russian for example. Triangl (talk) 15:37, 10 April 2011 (UTC)