search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.43k stars 479 forks source link

Implement a function to check if a graph is trivially perfect or not #37243

Open sanskarfc opened 9 months ago

sanskarfc commented 9 months ago

Problem Description

The objective of this feature request is to address the absence of a function in the SageMath library for graph theory that determines whether a given graph is trivially perfect or not. In graph theory, a trivially perfect graph is a graph with the property that in each of its induced subgraphs the size of the maximum independent set equals the number of maximal cliques.

Proposed Solution

My implementation is based upon the following: "They are the graphs that do not have a P4 path graph or a C4 cycle graph as induced subgraphs.[6]". I check all the connected induced subgraphs of size 4 for C4 and P4.

Alternatives Considered

An alternative implementation using LexBFS (Lexicographic breadth-first search) algorithm described by Chu (https://www.sciencedirect.com/science/article/abs/pii/S0020019007003377) which is a linear time algorithm for recognizing trivially perfect graphs was considered. Currently, I have implemented the algorithm mentioned in Proposed Solution due to it's simplicity.

Additional Information

Checking that a graph is trivially perfect or not is useful for understanding its structural properties, therefore this functionality can be very useful for researchers.

Is there an existing issue for this?

sanskarfc commented 9 months ago

I have completed the implementation and would be creating a pull request following the coding style of the repository soon. I hope it solves the issue.