Talk:Greedy coloring/Archives/2021

Running time

What is the order of the number of steps the greedy algorithm needs to colour a graph on n vertices? This is a personal question, but also a suggestion for content to be added to the article. 86.196.177.253 (talk) 22:39, 4 September 2009 (UTC)

It depends on how the vertex ordering is found. Once the vertices are ordered, the rest is linear. —David Eppstein (talk) 00:40, 5 September 2009 (UTC)

Ok, suppose that the vertices are already ordered from 1 to n, in a random fashion. Then when the algorithm is at vertex i, it has to scan all potential edges ij with j < i, taking exactly i - 1 steps. Therefore, the total number of steps is 1 + 2 + ... + (n-1), which is of order n^2, no? 86.210.207.133 (talk) 16:31, 5 September 2009 (UTC)

The standard assumption for sparse graphs is that they are represented as an adjacency list. So you don't have to scan all potential edges, only the ones that actually exist, taking a total amount of time that is linear in the size of the graph. To be more specific, you can create a vector of boolean values (is this color available) the length of which is the degree of the vertex plus one, then scan the edges checking off the colors that are used, then scan the vector to find the first free color. —David Eppstein (talk) 18:11, 5 September 2009 (UTC)

Ok, but what do you mean by sparse graph? I'm interested in random graphs with edge probability 1/2. Are those sparse? (BTW, thanks for your time and patience.) 86.210.207.133 (talk) 20:11, 5 September 2009 (UTC)

By sparse I mean that the number of edges is a tiny fraction of the number of possible edges. For a random graph with edge probability 1/2, you are going to have roughly n²/4 edges, so it's as efficient to do what you suggested earlier, testing all potential edges: a running time of O(n²) is linear in the input size. —David Eppstein (talk) 20:29, 5 September 2009 (UTC)

"a running time of O(n²) is linear in the input size" is that so the terminology? Isn't O(n²) 'quadratic in the input size'? 86.210.207.133 (talk) 20:49, 5 September 2009 (UTC)

No, the input size is also Θ(n²), because you need to somehow specify which edges are present and which aren't. So the input size and the running time are within a constant factor of each other; that's what I mean by "linear in the input size". —David Eppstein (talk) 21:09, 5 September 2009 (UTC)

Got you! Many thanks David. 86.210.207.133 (talk) 23:14, 5 September 2009 (UTC)

Perfect elimination ordering from perfect ordering

Chordal graphs are perfectly orderable; a perfect ordering of a chordal graph may be found by reversing a perfect elimination ordering for the graph.

Is this relationship bidirectional? Is a reversed perfect ordering always a perfect elimination ordering, or not necessarily? Ged.R (talk) 11:23, 18 August 2010 (UTC)

I don't think so. If G is a three-vertex path graph then G is chordal, every ordering of G is a perfect ordering, but not every ordering is a perfect elimination ordering. —David Eppstein (talk) 16:43, 18 August 2010 (UTC)

The upperright figure to show the bad case of greedy coloring is wrong

The right part of the figure should be colored in 4 colors, not 8. Please correct it. — Preceding unsigned comment added by PengUBC (talk • contribs) 00:41, 19 February 2014 (UTC)

Huh? It is colored in four colors already. Vertices 1 & 2 are red, vertices 3 & 4 are blue, vertices 5 & 6 are green, and vertices 7 & 8 are yellow. —David Eppstein (talk) 01:45, 19 February 2014 (UTC)

Grundy coloring versus Greedy coloring

Given a coloring c : V → {1, 2, . . . , k}, a node i is called a Grundy node if c(i) = min { l ≥ 1 | ∀j ∈ N(i) c(j) ≠ l}. In a grundy coloring all nodes are Grundy.

Greedy coloring should be compared to Grundy coloring (I believe that a greedy coloring is also a grundy coloring and vis-versa)

reference on Grundy coloring :

• P.M. Grundy, Mathematics and games, Eureka 2 (1939) 6–8.
• T.R. Jensen, B. Toft, Graph Coloring Problems, John Wiley &

Sons, New York, 1995. — Preceding unsigned comment added by 2001:660:6101:402:4D26:113B:7FFD:C4FA (talk) 13:49, 20 September 2018 (UTC)

GA Review

The following discussion is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.

---

This review is transcluded from Talk:Greedy coloring/GA1. The edit link for this section can be used to add comments to the review.

Reviewer: Spinningspark (talk · contribs) 18:43, 18 March 2020 (UTC)

Looking... SpinningSpark 18:43, 18 March 2020 (UTC)

Lead

• Suggest wikilink "online" as this is not the usual meaning

Choice of ordering

• Kn/2,n/2 notation is not explained

• I know we are not supposed to refer back to a higher level heading, but I'm not sure that works for the subheadings of this section. It took a while before I understood what the "Bad" subheading was referring to. I think the difficulty is these headings are adjectives. The MOS does say that noun phrases should normally be used. Same issue in the following section too.

Indifferent

• Link co-NP-complete

Degenerate

• "The largest number d encountered during this algorithm as the degree of a removed vertex..." Does this mean d is the degree of the removed vertex? If so perhaps "The largest number d encountered during this algorithm, where d is the degree of a removed vertex, is called the degeneracy..."
• I'm not sure I understand how the diagram is meant to relate to vertex colouring. The vertices are not coloured in the image, but the caption claims to show "greedy coloring with the degeneracy ordering". If the image is just there because those shapes are mentioned in the text, then the caption should be changed to suit.
• 2-approximation is not linked or explained. The appropriate link seems to be Approximation algorithm#Performance guarantees if I have understood it correctly.

Adaptive

• I know it's a fairly basic concept, but it still might be worth linking cardinality

I've asked another editor to look at the Python code as that is outside my skills set to comment on. SpinningSpark 10:03, 19 March 2020 (UTC)

@Spinningspark: Ok, I think I've handled everything.

• In "Choice of ordering", I replaced the explanation of crown graphs using complete bipartite graphs and matchings (intuitive but requiring some background knowledge) with a lower-level direct construction of these graphs, also helpful for explaining the bad ordering of them.
• Subsection headings are all nouns or noun phrases now. I think they're less catchy that way, but maybe more informative.
• In degeneracy, "d" is the number for the whole graph, not a single vertex; reworded to clarify. The illustration indeed shows only the graphs, not their (many!) degeneracy-based greedy colorings and optimal colorings; I thought the caption already said that, but I have reworded to clarify. It is there to remind readers what the two graphs mentioned in the text look like. "2-approximation" expanded to a less technical explanation.
• Other minor suggestions done.

—David Eppstein (talk) 19:46, 19 March 2020 (UTC)

The discussion above is closed. Please do not modify it. Subsequent comments should be made on the appropriate discussion page. No further edits should be made to this discussion.