# Graphclass: square of tree

The following definitions are equivalent:
1. G is a square of tree iff it is chordal , 2-connected and its maximal cliques have the following properties:
• Every two distinct maximal cliques have at most two vertices in common.
• Every 2-cut belongs to exactly two maximal cliques.
• Every pair of non-disjoint 2-cuts belongs to the same maximal clique.
• All 2-cuts contained in the same maximal clique of G have a common vertex.

## Problems

Problems in italics have no summary page and are only listed when ISGCI contains a result for the current class.

#### Parameter decomposition

book thickness decomposition Unknown to ISGCI [+]Details
booleanwidth decomposition Unknown to ISGCI [+]Details
cliquewidth decomposition Unknown to ISGCI [+]Details
cutwidth decomposition Unknown to ISGCI [+]Details
treewidth decomposition Polynomial [+]Details

#### Unweighted problems

3-Colourability Linear [+]Details
Clique Polynomial [+]Details
Clique cover Polynomial [+]Details
Colourability Linear [+]Details
Domination Unknown to ISGCI [+]Details
Feedback vertex set Polynomial [+]Details
Graph isomorphism Unknown to ISGCI [+]Details
Hamiltonian cycle Unknown to ISGCI [+]Details
Hamiltonian path Unknown to ISGCI [+]Details
Independent dominating set Linear [+]Details
Independent set Linear [+]Details
Maximum cut Unknown to ISGCI [+]Details
Monopolarity Linear [+]Details
Polarity Polynomial [+]Details
Recognition Polynomial [+]Details

#### Weighted problems

Weighted clique Polynomial [+]Details
Weighted feedback vertex set Unknown to ISGCI [+]Details
Weighted independent set Linear [+]Details