chordal
tags: vertex order, tree decomposition, intersection
providers: ISGCI
Definitions:
- Contains no induced cycle on 4 or more vertices.
- Has a vertex order, called perfect elimination scheme, such that future neighborhoods are always cliques.
- Has a tree-decomposition such that every bag is a clique.
- Is an intersection graph of subtrees of a tree.
Relations
Other | Relation from | Relation to | |
---|---|---|---|
acyclic chromatic number | ■ | exclusion | unbounded |
admissibility | ■ | exclusion | unbounded |
arboricity | ■ | exclusion | unbounded |
average degree | ■ | exclusion | unbounded |
average distance | ■ | exclusion | unbounded |
bandwidth | ■ | exclusion | unbounded |
bipartite | ■ | exclusion | exclusion |
bipartite number | ■ | exclusion | unbounded |
bisection bandwidth | ■ | exclusion | unbounded |
block | ■ | inclusion | exclusion |
book thickness | ■ | exclusion | unbounded |
boolean width | ■ | exclusion | unknown to HOPS |
bounded components | ■ | exclusion | unbounded |
bounded expansion | ■ | exclusion | avoids |
boxicity | ■ | exclusion | unknown to HOPS |
branch width | ■ | exclusion | unbounded |
c-closure | ■ | exclusion | unknown to HOPS |
carving-width | ■ | exclusion | unbounded |
chi-bounded | ■ | exclusion | upper bound |
chordal | ■ | equal | equal |
chordality | ■ | exclusion | upper bound |
chromatic number | ■ | exclusion | unbounded |
clique cover number | ■ | exclusion | unbounded |
clique-tree-width | ■ | exclusion | unknown to HOPS |
clique-width | ■ | exclusion | unknown to HOPS |
cluster | ■ | upper bound | exclusion |
co-cluster | ■ | exclusion | exclusion |
cograph | ■ | exclusion | exclusion |
complete | ■ | upper bound | exclusion |
connected | ■ | exclusion | avoids |
contraction complexity | ■ | exclusion | unbounded |
cutwidth | ■ | exclusion | unbounded |
cycle | ■ | unknown to HOPS | exclusion |
cycles | ■ | exclusion | exclusion |
d-admissibility | ■ | exclusion | unknown to HOPS |
d-path-free | ■ | exclusion | unbounded |
degeneracy | ■ | exclusion | unbounded |
degree treewidth | ■ | exclusion | unbounded |
diameter | ■ | exclusion | unbounded |
diameter+max degree | ■ | exclusion | unbounded |
distance to bipartite | ■ | exclusion | unbounded |
distance to block | ■ | exclusion | unknown to HOPS |
distance to bounded components | ■ | exclusion | unbounded |
distance to chordal | ■ | exclusion | upper bound |
distance to cluster | ■ | exclusion | unbounded |
distance to co-cluster | ■ | exclusion | unbounded |
distance to cograph | ■ | exclusion | unbounded |
distance to complete | ■ | exclusion | unbounded |
distance to edgeless | ■ | exclusion | unbounded |
distance to forest | ■ | exclusion | unbounded |
distance to interval | ■ | exclusion | unbounded |
distance to linear forest | ■ | exclusion | unbounded |
distance to maximum degree | ■ | exclusion | unbounded |
distance to outerplanar | ■ | exclusion | unbounded |
distance to perfect | ■ | exclusion | upper bound |
distance to planar | ■ | exclusion | unbounded |
distance to stars | ■ | exclusion | unbounded |
domatic number | ■ | exclusion | unbounded |
domination number | ■ | exclusion | unbounded |
domino treewidth | ■ | exclusion | unbounded |
edge clique cover number | ■ | exclusion | unbounded |
edge connectivity | ■ | exclusion | unbounded |
edge-cut width | ■ | exclusion | unbounded |
edge-treewidth | ■ | exclusion | unbounded |
edgeless | ■ | upper bound | avoids |
excluded minor | ■ | exclusion | avoids |
excluded planar minor | ■ | unknown to HOPS | avoids |
excluded top-minor | ■ | exclusion | avoids |
feedback edge set | ■ | exclusion | unbounded |
feedback vertex set | ■ | exclusion | unbounded |
flip-width | ■ | exclusion | unknown to HOPS |
forest | ■ | upper bound | exclusion |
genus | ■ | exclusion | unbounded |
grid | ■ | exclusion | exclusion |
h-index | ■ | exclusion | unbounded |
interval | ■ | inclusion | exclusion |
iterated type partitions | ■ | exclusion | unbounded |
linear clique-width | ■ | exclusion | unknown to HOPS |
linear forest | ■ | upper bound | exclusion |
linear NLC-width | ■ | exclusion | unknown to HOPS |
linear rank-width | ■ | exclusion | unknown to HOPS |
maximum clique | ■ | exclusion | unbounded |
maximum degree | ■ | exclusion | unbounded |
maximum independent set | ■ | exclusion | unbounded |
maximum induced matching | ■ | exclusion | unbounded |
maximum leaf number | ■ | exclusion | unbounded |
maximum matching | ■ | exclusion | unbounded |
maximum matching on bipartite graphs | ■ | unknown to HOPS | unbounded |
merge-width | ■ | exclusion | unknown to HOPS |
mim-width | ■ | exclusion | unknown to HOPS |
minimum degree | ■ | exclusion | unbounded |
mm-width | ■ | exclusion | unbounded |
modular-width | ■ | exclusion | unbounded |
module-width | ■ | exclusion | unknown to HOPS |
monadically dependent | ■ | exclusion | unknown to HOPS |
monadically stable | ■ | exclusion | unknown to HOPS |
neighborhood diversity | ■ | exclusion | unbounded |
NLC-width | ■ | exclusion | unknown to HOPS |
NLCT-width | ■ | exclusion | unknown to HOPS |
nowhere dense | ■ | exclusion | unknown to HOPS |
odd cycle transversal | ■ | exclusion | unbounded |
outerplanar | ■ | unknown to HOPS | exclusion |
overlap treewidth | ■ | exclusion | unbounded |
path | ■ | upper bound | exclusion |
pathwidth | ■ | exclusion | unbounded |
pathwidth+maxdegree | ■ | exclusion | unbounded |
perfect | ■ | exclusion | inclusion |
planar | ■ | exclusion | exclusion |
radius-inf flip-width | ■ | exclusion | unknown to HOPS |
radius-r flip-width | ■ | exclusion | unknown to HOPS |
rank-width | ■ | exclusion | unknown to HOPS |
series-parallel | ■ | unknown to HOPS | unknown to HOPS |
shrub-depth | ■ | exclusion | unknown to HOPS |
sim-width | ■ | exclusion | upper bound |
size | ■ | exclusion | unbounded |
slim tree-cut width | ■ | exclusion | unbounded |
sparse twin-width | ■ | exclusion | unbounded |
star | ■ | upper bound | exclusion |
stars | ■ | upper bound | exclusion |
strong coloring number | ■ | exclusion | unbounded |
strong d-coloring number | ■ | exclusion | unknown to HOPS |
strong inf-coloring number | ■ | exclusion | unbounded |
topological bandwidth | ■ | exclusion | unbounded |
tree | ■ | upper bound | exclusion |
tree-cut width | ■ | exclusion | unbounded |
tree-independence number | ■ | exclusion | upper bound |
tree-partition-width | ■ | exclusion | unbounded |
treebandwidth | ■ | exclusion | unbounded |
treedepth | ■ | exclusion | unbounded |
treelength | ■ | exclusion | unknown to HOPS |
treespan | ■ | exclusion | unbounded |
treewidth | ■ | exclusion | unbounded |
twin-cover number | ■ | exclusion | unbounded |
twin-width | ■ | exclusion | unknown to HOPS |
vertex connectivity | ■ | unknown to HOPS | unknown to HOPS |
vertex cover | ■ | exclusion | unbounded |
vertex integrity | ■ | exclusion | unbounded |
weak coloring number | ■ | exclusion | unbounded |
weak d-coloring number | ■ | exclusion | unknown to HOPS |
weak inf-coloring number | ■ | exclusion | unbounded |
weakly sparse | ■ | exclusion | unknown to HOPS |
weakly sparse and merge width | ■ | exclusion | unbounded |
Results
- 2017 Graph Theory by Diestel
- page 135 : chordal – … a graph is chordal (or triangulated) if each of its cycles of length at least $4$ has a chord, i.e. if it contains no induced cycles other than triangles.
- assumed
- graph class chordal has contained in perfect
- graph class perfect does not have contained in chordal
- graph class interval has contained in chordal
- graph class chordal does not have contained in interval
- graph class block has contained in chordal
- graph class chordal does not have contained in block
- chordal upper bounds distance to chordal by a constant – by definition
- chordal is equivalent to chordal – assumed