HOPS web view
This page lists:
Parameters
- NLC-width
- NLCT-width
- acyclic chromatic number
- arboricity
- average degree
- average distance
- bandwidth
- bisection bandwidth
- book thickness
- boolean width
- bounded components
- boxicity
- branch width
- c-closure
- carving-width
- chordality
- chromatic number
- clique cover number
- clique-tree-width
- clique-width
- cutwidth
- d-path-free
- degeneracy
- degree treewidth
- diameter
- distance to bipartite
- distance to block
- distance to bounded components
- distance to chordal
- distance to cluster
- distance to co-cluster
- distance to cograph
- distance to complete
- distance to disconnected
- distance to edgeless
- distance to forest
- distance to interval
- distance to linear forest
- distance to maximum degree
- distance to outerplanar
- distance to perfect
- distance to planar
- distance to stars
- domatic number
- domination number
- edge clique cover number
- edge connectivity
- feedback edge set
- feedback vertex set
- genus
- girth
- h-index
- inf-flip-width
- linear NLC-width
- linear clique-width
- linear rank-width
- maximum clique
- maximum degree
- maximum independent set
- maximum induced matching
- maximum leaf number
- maximum matching
- maximum matching on bipartite graphs
- mim-width
- minimum degree
- modular-width
- neighborhood diversity
- odd cycle transversal
- outerthickness
- pathwidth
- pathwidth+maxdegree
- radius-r flip-width
- rank-width
- reduced bandwidth
- reduced edgeless
- shrub-depth
- star-arboricity
- thickness
- topological bandwidth
- treedepth
- treewidth
- twin-cover number
- twin-width
- vertex connectivity
- vertex cover
- vertex integrity
Graph classes
Some parameters are derived from associated graph classes. Graph classes can be also used as witnesses of proper inclusions. For these purposes, we use the following graph class hierarchy. We assume that all of the graph class inclusions are proper.
We aim to have here only the graph classes that influence parameter inclusions. Please, see Information System on Graph Classes and their Inclusions (ISGCI) for an exhaustive list of graph classes and their inclusions.
- bipartite
- block
- chordal
- cluster
- co-cluster
- cograph
- complete
- connected
- cycle
- cycles
- disconnected
- disjoint cycles
- edgeless
- forest
- grid
- interval
- linear forest
- outerplanar
- path
- perfect
- planar
- star
- stars
- tree
Sources
- twwsurfaces2024
- Torunczyk2023
- Tran2022
- twinWidthI2021
- SchroderThesis
- mimwidth2020
- Sorge2019
- Ganian2019
- Froemmrich2018
- Diestel2017
- ParameterizedAlgorithms2015
- ganianTwinCover2015
- Adler2015
- Jansen2013
- Belmonte2013
- modularwidth2013
- Vatshelle2012
- GanianTwinCover2012
- lampis2012
- BuiXuan2011
- bipboxicity2011
- Sasak2010
- Jelinek2010
- cliquewidthnpc2009
- gradnesetril2008
- spanningTreesManyLeaves2008
- GeometricThickness2007
- Oum2006
- Gurski2005
- TackLayouts2004
- courcelle2000
- Johansson1998
- Bodlaender1998
- Wanke1994
- BodlaenderMohring1993
- RobertsonSymour1991
- RobertsonSymour1986V
- Malitz1994
- chordality1993
- RobertsonSymour1986
- Chung1985