Mathematics版 - Re: How to show every comparability graph is perfect?? Thanks!!! |
|---|
|
|
|
|
|
|
o******d
发帖数: 1552 | 1 Here is my proof:
Let k be the size of the largest clique of G. Let r be the chromatic
number of G. Let me list some claims as lemma here:
[Lemma 1] k<=r (When k==r, G is perfect.)
Here is an example of not perfect graph:
o-----o-----o
| | |
| | |
o-----o o
\ /
\-------/
where k = 2, and r = 3
Now we only need to prove that the case of r > k does not exist.
[Lemma 2] There must exist a circle C which uses r colors and |C|>=r.
Pro | o******d
发帖数: 1552 | 2 I am sorry to tell you that there is a small hole in my proof. You have to
express the graph using the Hesse diagram, then the proof can be corrected
otherwise the "transtivity" does not hold. I check out the definition
in Math site and find it uses this definition for comparability graph:
if p<=q or q<=p, then p is connected to q. Actually, you only need one,
say, p<=q then the Hesse diagram is used:
p
|
|
q
If you don't say it clearly, then the proof may fail in this case:
p<=q |
|
|
|
|
|
|
|
