Function Repository Resource:

# PerfectGraphQ

Test whether a graph is perfect

Contributed by: Wolfram Staff (original content by Sriram V. Pemmaraju and Steven S. Skiena)
 ResourceFunction["PerfectGraphQ"][g] yields True if the Graph g is perfect and False otherwise.

## Details and Options

A graph is perfect if for every induced subgraph the size of the largest clique equals the chromatic number.

## Examples

### Basic Examples (2)

Test a perfect Graph:

 In[1]:=
 Out[1]=

Test an imperfect Graph:

 In[2]:=
 Out[2]=

### Properties and Relations (6)

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]=

## Version History

• 1.0.0 – 22 July 2020