chordal

tags: vertex order, tree decomposition, intersection

providers: ISGCI

Definitions:

  1. Contains no induced cycle on 4 or more vertices.
  2. Has a vertex order, called perfect elimination scheme, such that future neighborhoods are always cliques.
  3. Has a tree-decomposition such that every bag is a clique.
  4. Is an intersection graph of subtrees of a tree.


Relations

OtherRelation fromRelation to
acyclic chromatic numberblueexclusionunbounded
admissibilityblueexclusionunbounded
arboricityblueexclusionunbounded
average degreeblueexclusionunbounded
average distanceblueexclusionunbounded
bandwidthblueexclusionunbounded
bipartiteblueexclusionexclusion
bipartite numberblueexclusionunbounded
bisection bandwidthblueexclusionunbounded
blockgreeninclusionexclusion
book thicknessblueexclusionunbounded
boolean widthmagentaexclusionunknown to HOPS
bounded componentsblueexclusionunbounded
bounded expansionblueexclusionavoids
boxicitymagentaexclusionunknown to HOPS
branch widthblueexclusionunbounded
c-closuremagentaexclusionunknown to HOPS
carving-widthblueexclusionunbounded
chi-boundedredexclusionupper bound
chordalyellowequalequal
chordalityredexclusionupper bound
chromatic numberblueexclusionunbounded
clique cover numberblueexclusionunbounded
clique-tree-widthmagentaexclusionunknown to HOPS
clique-widthmagentaexclusionunknown to HOPS
clustergreenupper boundexclusion
co-clusterblueexclusionexclusion
cographblueexclusionexclusion
completegreenupper boundexclusion
connectedblueexclusionavoids
contraction complexityblueexclusionunbounded
cutwidthblueexclusionunbounded
cyclecyanunknown to HOPSexclusion
cyclesblueexclusionexclusion
d-admissibilitymagentaexclusionunknown to HOPS
d-path-freeblueexclusionunbounded
degeneracyblueexclusionunbounded
degree treewidthblueexclusionunbounded
diameterblueexclusionunbounded
diameter+max degreeblueexclusionunbounded
distance to bipartiteblueexclusionunbounded
distance to blockmagentaexclusionunknown to HOPS
distance to bounded componentsblueexclusionunbounded
distance to chordalredexclusionupper bound
distance to clusterblueexclusionunbounded
distance to co-clusterblueexclusionunbounded
distance to cographblueexclusionunbounded
distance to completeblueexclusionunbounded
distance to edgelessblueexclusionunbounded
distance to forestblueexclusionunbounded
distance to intervalblueexclusionunbounded
distance to linear forestblueexclusionunbounded
distance to maximum degreeblueexclusionunbounded
distance to outerplanarblueexclusionunbounded
distance to perfectredexclusionupper bound
distance to planarblueexclusionunbounded
distance to starsblueexclusionunbounded
domatic numberblueexclusionunbounded
domination numberblueexclusionunbounded
domino treewidthblueexclusionunbounded
edge clique cover numberblueexclusionunbounded
edge connectivityblueexclusionunbounded
edge-cut widthblueexclusionunbounded
edge-treewidthblueexclusionunbounded
edgelessgreenupper boundavoids
excluded minorblueexclusionavoids
excluded planar minorcyanunknown to HOPSavoids
excluded top-minorblueexclusionavoids
feedback edge setblueexclusionunbounded
feedback vertex setblueexclusionunbounded
flip-widthmagentaexclusionunknown to HOPS
forestgreenupper boundexclusion
genusblueexclusionunbounded
gridblueexclusionexclusion
h-indexblueexclusionunbounded
intervalgreeninclusionexclusion
iterated type partitionsblueexclusionunbounded
linear clique-widthmagentaexclusionunknown to HOPS
linear forestgreenupper boundexclusion
linear NLC-widthmagentaexclusionunknown to HOPS
linear rank-widthmagentaexclusionunknown to HOPS
maximum cliqueblueexclusionunbounded
maximum degreeblueexclusionunbounded
maximum independent setblueexclusionunbounded
maximum induced matchingblueexclusionunbounded
maximum leaf numberblueexclusionunbounded
maximum matchingblueexclusionunbounded
maximum matching on bipartite graphscyanunknown to HOPSunbounded
merge-widthmagentaexclusionunknown to HOPS
mim-widthmagentaexclusionunknown to HOPS
minimum degreeblueexclusionunbounded
mm-widthblueexclusionunbounded
modular-widthblueexclusionunbounded
module-widthmagentaexclusionunknown to HOPS
monadically dependentmagentaexclusionunknown to HOPS
monadically stablemagentaexclusionunknown to HOPS
neighborhood diversityblueexclusionunbounded
NLC-widthmagentaexclusionunknown to HOPS
NLCT-widthmagentaexclusionunknown to HOPS
nowhere densemagentaexclusionunknown to HOPS
odd cycle transversalblueexclusionunbounded
outerplanarcyanunknown to HOPSexclusion
overlap treewidthblueexclusionunbounded
pathgreenupper boundexclusion
pathwidthblueexclusionunbounded
pathwidth+maxdegreeblueexclusionunbounded
perfectredexclusioninclusion
planarblueexclusionexclusion
radius-inf flip-widthmagentaexclusionunknown to HOPS
radius-r flip-widthmagentaexclusionunknown to HOPS
rank-widthmagentaexclusionunknown to HOPS
series-parallelgrayunknown to HOPSunknown to HOPS
shrub-depthmagentaexclusionunknown to HOPS
sim-widthredexclusionupper bound
sizeblueexclusionunbounded
slim tree-cut widthblueexclusionunbounded
sparse twin-widthblueexclusionunbounded
stargreenupper boundexclusion
starsgreenupper boundexclusion
strong coloring numberblueexclusionunbounded
strong d-coloring numbermagentaexclusionunknown to HOPS
strong inf-coloring numberblueexclusionunbounded
topological bandwidthblueexclusionunbounded
treegreenupper boundexclusion
tree-cut widthblueexclusionunbounded
tree-independence numberredexclusionupper bound
tree-partition-widthblueexclusionunbounded
treebandwidthblueexclusionunbounded
treedepthblueexclusionunbounded
treelengthmagentaexclusionunknown to HOPS
treespanblueexclusionunbounded
treewidthblueexclusionunbounded
twin-cover numberblueexclusionunbounded
twin-widthmagentaexclusionunknown to HOPS
vertex connectivitygrayunknown to HOPSunknown to HOPS
vertex coverblueexclusionunbounded
vertex integrityblueexclusionunbounded
weak coloring numberblueexclusionunbounded
weak d-coloring numbermagentaexclusionunknown to HOPS
weak inf-coloring numberblueexclusionunbounded
weakly sparsemagentaexclusionunknown to HOPS
weakly sparse and merge widthblueexclusionunbounded

Results