Wolfram Function Repository
Instant-use add-on functions for the Wolfram Language
Function Repository Resource:
Test whether a graph is perfect
The GraphComplement of a perfect Graph is perfect:
In[3]:= |
In[4]:= |
Out[4]= |
In[5]:= |
Out[5]= |
In[6]:= |
Out[6]= |
If the graph complement of g is imperfect, then so is g:
In[7]:= |
In[8]:= |
Out[8]= |
In[9]:= |
Out[9]= |
Bipartite graphs are perfect:
In[10]:= |
In[11]:= |
Out[11]= |
Line graphs of bipartite graphs are perfect:
In[12]:= |
Out[12]= |
In[13]:= |
Out[13]= |
Interval graphs (and chordal graphs in general) are perfect:
In[14]:= |
Out[15]= |
In[16]:= |
Out[16]= |
For named graphs, you can check the "Perfect" and "Imperfect" properties within GraphData without computing PerfectGraphQ:
In[17]:= |
Out[17]= |
In[18]:= |
Out[18]= |
In[19]:= |
Out[19]= |
In[20]:= |
Out[20]= |
This work is licensed under a Creative Commons Attribution 4.0 International License