# Weakly chordal graphs#

This module deals with everything related to weakly chordal graphs. It currently contains the following functions:

 is_long_hole_free() Tests whether g contains an induced cycle of length at least 5. is_long_antihole_free() Tests whether g contains an induced anticycle of length at least 5. is_weakly_chordal() Tests whether g is weakly chordal.

Author:

• Birk Eisermann (initial implementation)

• Nathann Cohen (some doc and optimization)

• David Coudert (remove recursion)

## Methods#

sage.graphs.weakly_chordal.is_long_antihole_free(g, certificate=False)[source]#

Tests whether the given graph contains an induced subgraph that is isomorphic to the complement of a cycle of length at least 5.

INPUT:

• certificate – boolean (default: False)

Whether to return a certificate. When certificate = True, then the function returns

• (False, Antihole) if g contains an induced complement of a cycle of length at least 5 returned as Antihole.

• (True, []) if g does not contain an induced complement of a cycle of length at least 5. For this case it is not known how to provide a certificate.

When certificate = False, the function returns just True or False accordingly.

ALGORITHM:

This algorithm tries to find a cycle in the graph of all induced $$\overline{P_4}$$ of $$g$$, where two copies $$\overline{P}$$ and $$\overline{P'}$$ of $$\overline{P_4}$$ are adjacent if there exists a (not necessarily induced) copy of $$\overline{P_5}=u_1u_2u_3u_4u_5$$ such that $$\overline{P}=u_1u_2u_3u_4$$ and $$\overline{P'}=u_2u_3u_4u_5$$.

This is done through a depth-first-search. For efficiency, the auxiliary graph is constructed on-the-fly and never stored in memory.

The run time of this algorithm is $$O(n+m^2)$$ for SparseGraph and $$O(n^2\log{m} + m^2)$$ for DenseGraph [NP2007] (where $$n$$ is the number of vertices and $$m$$ is the number of edges of the graph).

EXAMPLES:

The Petersen Graph contains an antihole:

sage: g = graphs.PetersenGraph()
sage: g.is_long_antihole_free()
False

>>> from sage.all import *
>>> g = graphs.PetersenGraph()
>>> g.is_long_antihole_free()
False


The complement of a cycle is an antihole:

sage: g = graphs.CycleGraph(6).complement()
sage: r,a = g.is_long_antihole_free(certificate=True)
sage: r
False
sage: a.complement().is_isomorphic(graphs.CycleGraph(6))
True

>>> from sage.all import *
>>> g = graphs.CycleGraph(Integer(6)).complement()
>>> r,a = g.is_long_antihole_free(certificate=True)
>>> r
False
>>> a.complement().is_isomorphic(graphs.CycleGraph(Integer(6)))
True

sage.graphs.weakly_chordal.is_long_hole_free(g, certificate=False)[source]#

Tests whether g contains an induced cycle of length at least 5.

INPUT:

• certificate – boolean (default: False)

Whether to return a certificate. When certificate = True, then the function returns

• (True, []) if g does not contain such a cycle. For this case, it is not known how to provide a certificate.

• (False, Hole) if g contains an induced cycle of length at least 5. Hole returns this cycle.

If certificate = False, the function returns just True or False accordingly.

ALGORITHM:

This algorithm tries to find a cycle in the graph of all induced $$P_4$$ of $$g$$, where two copies $$P$$ and $$P'$$ of $$P_4$$ are adjacent if there exists a (not necessarily induced) copy of $$P_5=u_1u_2u_3u_4u_5$$ such that $$P=u_1u_2u_3u_4$$ and $$P'=u_2u_3u_4u_5$$.

This is done through a depth-first-search. For efficiency, the auxiliary graph is constructed on-the-fly and never stored in memory.

The run time of this algorithm is $$O(n+m^2)$$ for SparseGraph and $$O(n^2 + m^2)$$ for DenseGraph [NP2007] (where $$n$$ is the number of vertices and $$m$$ is the number of edges of the graph).

EXAMPLES:

The Petersen Graph contains a hole:

sage: g = graphs.PetersenGraph()
sage: g.is_long_hole_free()
False

>>> from sage.all import *
>>> g = graphs.PetersenGraph()
>>> g.is_long_hole_free()
False


The following graph contains a hole, which we want to display:

sage: g = graphs.FlowerSnark()
sage: r,h = g.is_long_hole_free(certificate=True)
sage: r
False
sage: Graph(h).is_isomorphic(graphs.CycleGraph(h.order()))
True

>>> from sage.all import *
>>> g = graphs.FlowerSnark()
>>> r,h = g.is_long_hole_free(certificate=True)
>>> r
False
>>> Graph(h).is_isomorphic(graphs.CycleGraph(h.order()))
True

sage.graphs.weakly_chordal.is_weakly_chordal(g, certificate=False)[source]#

Tests whether the given graph is weakly chordal, i.e., the graph and its complement have no induced cycle of length at least 5.

INPUT:

• certificate – Boolean value (default: False) whether to return a certificate. If certificate = False, return True or False according to the graph. If certificate = True, return

• (False, forbidden_subgraph) when the graph contains a forbidden subgraph H, this graph is returned.

• (True, []) when the graph is weakly chordal.

For this case, it is not known how to provide a certificate.

ALGORITHM:

This algorithm checks whether the graph g or its complement contain an induced cycle of length at least 5.

Using is_long_hole_free() and is_long_antihole_free() yields a run time of $$O(n+m^2)$$ for SparseGraph and $$O(n^2\log{m} + m^2)$$ for DenseGraph (where $$n$$ is the number of vertices and $$m$$ is the number of edges of the graph).

EXAMPLES:

The Petersen Graph is not weakly chordal and contains a hole:

sage: g = graphs.PetersenGraph()
sage: r,s = g.is_weakly_chordal(certificate=True)
sage: r
False
sage: l = s.order()
sage: s.is_isomorphic(graphs.CycleGraph(l))
True

>>> from sage.all import *
>>> g = graphs.PetersenGraph()
>>> r,s = g.is_weakly_chordal(certificate=True)
>>> r
False
>>> l = s.order()
>>> s.is_isomorphic(graphs.CycleGraph(l))
True