Talk:Perfect graph

1-perfect?

What is the interest of introducing "1-perfect" here? Is it just for the attached reference? — Preceding unsigned comment added by 88.121.200.153 (talk) 08:20, 13 October 2021 (UTC)

GA Review

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

Reviewer: Brachy0008 (talk · contribs) 03:24, 15 January 2024 (UTC)

I would like to get a second opinion because, well, the source review is kind of overwhelming for me. (I tried reading FN 1) Brachy08 _(Talk) 03:48, 24 January 2024 (UTC)

Hi! Brachy08 here! I will be your reviewer for this GA (because, you know, WikiCup 2024). However, I would take some time to review it (I am a math person, as a disclaimer regarding criterion 1).

Images

• All images are own work, passing 6b.

Sourcing

• Sources are reliable, passing 2b.

Tips

• Can do lots of summarization for non-mathematicians to understand.

Copyvio

• Violation unlikely (22.5%)

Comments

Thanks for taking this on! Please ping me when you have concrete improvements that need to be made to the article. Re summarization: there are quite a few short glosses of linked terms already in the article, if that's what you mean; more might be appropriate but to some extent this is limited by Good Article criterion 3b. —David Eppstein (talk) 08:31, 15 January 2024 (UTC)

You’re welcome Brachy08 _(Talk) 08:41, 15 January 2024 (UTC)

@Brachy0008 Sorry for butting in. I'm surprised that you have put the second opinion. Any reason why? Dedhert.Jr (talk) 03:51, 26 January 2024 (UTC)

I don’t think I can handle the review. Can you take over for me please? Thank you! Brachy08 _(Talk) 04:47, 26 January 2024 (UTC)

If you don't want to handle the review any more, with little already here, the usual process would be to get this review page deleted so that the nomination can wait until another reviewer has the time and interest to do so. You could request to be removed as reviewer at Wikipedia talk:Good article nominations. If you did, it could probably be handled as a speedy deletion under WP:CSD#G7, although G6 is more common. —David Eppstein (talk) 07:15, 26 January 2024 (UTC)

@Brachy0008 If you passed the review to me, it's fine. However, I have some important unfinished tasks in Wikipedia, such as take control over the GAR and some old GA before they delisted (and FA as well, but not neccessarily active).

@David Eppstein I do think I may ping someone for reviewing this article, the user who reviewing your previous GA, but the user is not active based on its contribution. Just in case, does it actually considered as WP:CANVASSING? Dedhert.Jr (talk) 12:57, 26 January 2024 (UTC)

I think it's not a canvassing violation, but I'd be happier putting this back into the nomination pool and letting a reviewer appear organically than pressuring someone who might not feel ready to do it into reviewing. —David Eppstein (talk) 18:57, 26 January 2024 (UTC)

@David Eppstein I believe that putting it back into the review pool might be the best course of action. I don't think the reviewer fully finished the review and also a Source Spotcheck hasn't been provided, so I think that's the best course of action. Dcdiehardfan (talk) 02:52, 14 February 2024 (UTC)

Yeah, that’s why I asked for second opinion Brachy08 _(Talk) 02:59, 14 February 2024 (UTC)

For sure, but just as a general side note, I do agree with your assessment that the overall article could be more lay-friendly. Dcdiehardfan (talk) 03:10, 14 February 2024 (UTC)

Please note WP:ONEDOWN. Writing for the widest possible audience is not the same as writing for a lay audience. Otherwise we would be reduced to the dumbed-down mush that one can often find in Quanta where anything technical is only vaguely alluded to by stretched analogies. Specific pointers to parts of the article that are unnecessarily technical are helpful and constructive. Vague complaints that math is hard are not. —David Eppstein (talk) 07:33, 14 February 2024 (UTC)

GA Review

This review is transcluded from Talk:Perfect graph/GA2. The edit link for this section can be used to add comments to the review.

Reviewer: Jakob.scholbach (talk · contribs) 13:08, 17 March 2024 (UTC)

I will start reviewing this article! Other comments welcome! Jakob.scholbach (talk) 13:08, 17 March 2024 (UTC)

I think it would be easy to finish off this GA nomination by mechanically checking the GA criteria and finding that they are all satisfied. I have however never liked this way of approaching such a GA nomination, so I will offer some comments that come to my mind while reading the article. As you will immediately notice from the comments, I'm very much not into this area of mathematics, so I acknowledge beforehand that some of these comments may be missing the point, so please tell me if this is the case.

• I find the definitions section very short. It almost sends the reader away to other articles, which it should not. Is it possible to include a few illustrations or other explanatory text to make the article more self-contained? The later section on bipartite graphs contains some information that would be easy enough to digest as an illustration of the notion of clique number and chromatic number, for example. Another idea: is it sensible / possible to make little "zoo" of examples with graphs with small clique number and chromatic number? Or give examples of some graphs that fail to be perfect very badly / fail for interesting reasons.
• "The perfect graph theorem has a short proof," -- does this refer to the first proof in 1972, or did it get simplified later on?
• In several spots the word "perfection" is seemingly referred to the property of being perfect. Is this intentional (in my non-native English unterstanding, perfection refers to the process of rendering something perfect)?
• I'm not sure how actionable this is, but somehow the article doesn't convey (to me) the importance of the concept. Is it possible to shed light on why this is a difficult / interesting / noteworthy topic?
• The paragraph "The strong perfect graph theorem gives a different ..." has as a reference what seems to be the original article on the proof of the theorem. Is there a text-book account of this?
• The paragraph "Finite comparability graphs (and their complementary incomparability graphs) ..." could make better use of the illustration by referring to it. E.g. it could point out that A-B-D is a chain etc.
• "Mirsky's theorem is easier than Dilworth's theorem to prove directly" - maybe reword to "Mirsky's theorem is easier to prove directly than Dilworth's theorem" ?
• To an uninitiated reader (like me), lists such as "They include as subclasses the trees, even-length cycle graphs, lattice graphs, knight's graphs, modular graphs, median graphs, and partial cubes, among many others.[16]" are not so valuable. Maybe consider highlighting what is really crucial (to this article), and consider removing some such mentions that might be secondary?
• In the secion on split graphs, it would be beautiful to color the illustration in order to match the text. Or at least label the vertices, and refer to them in the text? (OR the image caption?)
• Inspired by the heading "random perfect graphs" -- I take it that the condition of being perfect is a rather strong condition. Is there any honest statement in such a direction?
• This may be another not-so-actionable comment, but I can't quite refrain from pointing it out: the section on families of perfect graphs is very long, and it just fails to catch me. E.g. "The threshold graphs are formed from an empty graph ..." this section seems (from the little I understand) to be a relatively trivial observation (right?) If this is true, it is just the n+1-st mention of several classes of graphs being contained in one another. If it is possible to highlight more of a red thread throughout, that would greatly improve the article. (I can imagine this is difficult though.)
• I will continue reviewing the rest of the article as soon as I can. Jakob.scholbach (talk) 22:12, 23 March 2024 (UTC)

Some responses to I think all of the above:

I'm much happier with a GA review that produces a dialogue about the article (even with points I might disagree with) than with one that just mechanically checks the criteria — ideally the process should end up improving the article and not merely certifying that it was already good enough. So thanks for that!

Re the definitions section being too short: Are you maybe thinking only of the first paragraph of the section, the one defining coloring number, clique number, and perfect graphs as (1) having those numbers equal in all induced subgraphs? It glosses all those topics, and also provides wikilinks to our separate articles on those topics, as it should. What part of it is not self-contained? Or are you referring to the later paragraphs of this section, the ones that provide equivalent definitions of perfect graphs in terms of (2) equal independence number and clique cover number, (3) no odd holes or their complements, or (4) product of clique number and independence number? That is, we have four paragraphs each providing a different definition of these graphs. I am not sure from your comment which part of this you think is too short.

I was referring to the first paragraph in the section "Definitions and characterizations". I think it does define all necessary preliminary notions, and does give links to the subtopics. However, to 95+% of readers who are not already familiar with these topics you basically have to follow these links to the subpages in order to get a better idea, and this need not (and IMO should not) be so. Why not include a few more sentences about these preliminary notions, maybe with a few illustrations? Jakob.scholbach (talk) 20:42, 31 March 2024 (UTC)

Re the perfect graph theorem has a short proof: I was mostly referring to the proof through the product characterization of perfect graphs, Lovasz (the other 1972 paper) and Gasparyan. I added footnotes to clarify that point.

Thanks. Jakob.scholbach (talk) 20:42, 31 March 2024 (UTC)

Re "perfection" meaning "being perfect" rather than "making perfect" or "becoming perfect": in colloquial English it can have any of these three meanings. "Perfecting", instead, would only mean "making perfect". Google Scholar claims to have 634 hits for the combination of "perfect graph" and "perfection" and I suspect most or all of them are about being perfect rather than becoming perfect.

OK, alright Jakob.scholbach (talk) 20:42, 31 March 2024 (UTC)

Re why perfection is difficult / interesting / noteworthy: these are three different questions. Re difficult, see history: "The conjectured strong perfect graph theorem became the focus of research in the theory of perfect graphs for many years ... the proof of the strong perfect graph theorem is long and technical, based on a deep structural decomposition". Re interesting, see lead "include many important families of graphs and serve to unify results relating colorings and cliques in those families ... several important minimax theorems in combinatorics". Re noteworthy, see the many publications listed as references and the much larger number of publications not listed.

With my comment I didn't intend to say that I find this not difficult / not interesting or not noteworthy, but just that the difficulty / interest / noteworthyness of the topic didn't come across to me so well. But I agree that the snippets you cite do adress these, so maybe this is just me. Jakob.scholbach (talk) 20:42, 31 March 2024 (UTC)

Re "Is there a text-book account" of the proof of the strong perfect graph theorem? I added another reference, Cornuéjols' 2002 overview of the proof. You might expect it to be in the 2004 edition of Golumbic's book Algorithmic Graph Theory and Perfect Graphs but I don't have a copy of that edition and from my limited previous I suspect it's not there. Diestel's Graph Theory states the theorem but then immediately says "the proof...is long and technical, and it would not be too illuminating to attempt to sketch it".

OK! Jakob.scholbach (talk) 20:42, 31 March 2024 (UTC)

Re comparability graphs: added examples of chains and antichains to 2nd paragraph; reordered sentence about Mirski being easier to prove than Dilworth per your suggestion.

OK. Jakob.scholbach (talk) 20:42, 31 March 2024 (UTC)

Re lists [of graph classes] not being valuable, and re "the section on families of perfect graphs is very long": this goes back to the lead's "The perfect graphs include many important families of graphs". For many decades a central subtopic of graph theory research was the push to prove special cases of the strong perfect graph theorem for special classes of graphs, and in turn many now-important special classes of graphs were identified as part of this push. It is central to the topic. In drafting this article, I tried to keep this part of the article organized into logical subsections, and to reduce its length by avoiding some not-very-important subclasses, but it is still long. Expanding out sentences like "They include as subclasses the trees, even-length cycle graphs, lattice graphs, knight's graphs, modular graphs, median graphs, and partial cubes, among many others" to detail the relations among these graphs would make it even longer.

Later, I trimmed the list of bipartite graph classes, and found some other changes to tighten the section on families of perfect graphs and focus it more clearly on properties related to perfection: [1]. It's not much shorter than it was before, though. —David Eppstein (talk) 18:20, 27 March 2024 (UTC)

Yes, I think trimming it there was a good decision. Jakob.scholbach (talk) 20:42, 31 March 2024 (UTC)

Re "on split graphs, it would be beautiful to color the illustration": I replaced the illustration with a new one depicting the coloring method.

Great, thanks! Jakob.scholbach (talk) 20:42, 31 March 2024 (UTC)

Re random graphs, you mean, if one chooses a random graph without prior restrictions on its structure, is it extremely unlikely to be perfect? Yes, at least in the basic version of the Erdős–Rényi model where all graphs on the same vertex set are equally likely, because for any subset of vertices all induced subgraphs are equally likely. So each five-vertex set has some constant probability of inducing a hole and there are so many five-vertex sets that the probability of avoiding a hole becomes exponentially small. The same thing would be true for any nontrivial hereditary family of graphs. Probably it's difficult to source, though, because it's not very interesting (it doesn't have anything specific to do with being perfect). For very sparse random graphs, the graph will be a forest and therefore perfect. Random graphs with a linear number of edges below the threshold of a giant component are pseudoforests with a constant expected number of cycles, and I suspect that there is a constant probability of remaining bipartite (decreasing with edge density) up to the threshold, and therefore a constant probability of being perfect. But again finding a source that says anything about this specifically with respect to perfection is likely to be difficult.

OK, if this is trivial for an insider, then it's fine, it just came to my mind while reading. Jakob.scholbach (talk) 20:42, 31 March 2024 (UTC)

It is mostly trivial. The part that is nontrivial (but I think doable) is proving that critical random graphs (that is, with edge probability ${\tfrac {1}{n}}$) are whp imperfect. All other probabilities are easy. But without sources, I can't add anything about this to the article. —David Eppstein (talk) 06:39, 9 April 2024 (UTC)

—David Eppstein (talk) 19:01, 26 March 2024 (UTC)

@Jakob.scholbach: I expanded the first paragraph of the definitions section and moved up an image to illustrate it. Was that the last unfinished business, or did you still have more to review? —David Eppstein (talk) 07:04, 14 April 2024 (UTC)

Sorry @David Eppstein, I meant to read the rest of the article but I have not found the time to do that. I will try to allocate some time to this until the weekend. If I don't manage, I'll just content myself with the GA criteria proper. Sorry for the delay! Jakob.scholbach (talk) 12:28, 25 April 2024 (UTC)

GA review (see here for what the criteria are, and here for what they are not)
It is reasonably well written. a (prose, spelling, and grammar): b (MoS for lead, layout, word choice, fiction, and lists): It is factually accurate and verifiable, as shown by a source spot-check. a (references): b (citations to reliable sources): c (OR): d (copyvio and plagiarism): It is broad in its coverage. a (major aspects): b (focused): It follows the neutral point of view policy. Fair representation without bias: It is stable. No edit wars, etc.: It is illustrated by images, where possible and appropriate. a (images are tagged and non-free images have fair use rationales): b (appropriate use with suitable captions):
Overall: Pass/Fail:
· · ·