cograph

equivalent to: cograph

providers: ISGCI

Relations

Other	Relation from	Relation to
acyclic chromatic number	exclusion	unbounded
arboricity	exclusion	unbounded
average degree	exclusion	unbounded
average distance	exclusion	constant
bandwidth	exclusion	unbounded
bipartite	exclusion	exclusion
bipartite number	exclusion	constant
bisection bandwidth	exclusion	unbounded
block	exclusion	exclusion
book thickness	exclusion	unbounded
boolean width	exclusion	constant
bounded components	exclusion	unbounded
boxicity	exclusion	unknown to HOPS
branch width	exclusion	unbounded
c-closure	exclusion	unknown to HOPS
carving-width	exclusion	unbounded
chordal	exclusion	exclusion
chordality	exclusion	constant
chromatic number	exclusion	unbounded
clique cover number	exclusion	unbounded
clique-tree-width	exclusion	unknown to HOPS
clique-width	exclusion	constant
cluster	unknown to HOPS	exclusion
co-cluster	inclusion	exclusion
complete	inclusion	exclusion
connected	exclusion	unknown to HOPS
cutwidth	exclusion	unbounded
cycle	exclusion	exclusion
cycles	exclusion	exclusion
d-path-free	exclusion	unbounded
degeneracy	exclusion	unbounded
degree treewidth	exclusion	unbounded
diameter	exclusion	constant
diameter+max degree	exclusion	unbounded
disjoint cycles	exclusion	exclusion
distance to bipartite	exclusion	unbounded
distance to block	exclusion	unbounded
distance to bounded components	exclusion	unbounded
distance to chordal	exclusion	unbounded
distance to cluster	unknown to HOPS	unbounded
distance to co-cluster	unknown to HOPS	unknown to HOPS
distance to cograph	unknown to HOPS	constant
distance to complete	unknown to HOPS	unbounded
distance to edgeless	unknown to HOPS	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	constant
distance to planar	exclusion	unknown to HOPS
distance to stars	unknown to HOPS	unbounded
domatic number	exclusion	unbounded
domination number	exclusion	unbounded
edge clique cover number	exclusion	unknown to HOPS
edge connectivity	exclusion	unbounded
edgeless	inclusion	exclusion
feedback edge set	exclusion	unbounded
feedback vertex set	exclusion	unbounded
forest	exclusion	exclusion
genus	exclusion	unbounded
girth	exclusion	constant
grid	exclusion	exclusion
h-index	exclusion	unbounded
inf-flip-width	exclusion	constant
interval	exclusion	exclusion
iterated type partitions	exclusion	unknown to HOPS
linear clique-width	exclusion	unknown to HOPS
linear forest	exclusion	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	unknown to HOPS
maximum leaf number	exclusion	unbounded
maximum matching	unknown to HOPS	unbounded
maximum matching on bipartite graphs	unknown to HOPS	unbounded
mim-width	exclusion	constant
minimum degree	exclusion	unbounded
mm-width	exclusion	unbounded
modular-width	exclusion	unknown to HOPS
module-width	exclusion	constant
neighborhood diversity	exclusion	unknown to HOPS
NLC-width	exclusion	constant
NLCT-width	exclusion	unknown to HOPS
odd cycle transversal	exclusion	unbounded
outerplanar	exclusion	exclusion
path	exclusion	exclusion
pathwidth	exclusion	unbounded
pathwidth+maxdegree	exclusion	unbounded
perfect	exclusion	inclusion
planar	exclusion	exclusion
radius-r flip-width	exclusion	constant
rank-width	exclusion	constant
shrub-depth	exclusion	unknown to HOPS
sim-width	exclusion	constant
star	unknown to HOPS	exclusion
stars	unknown to HOPS	exclusion
topological bandwidth	exclusion	unbounded
tree	exclusion	exclusion
tree-independence number	exclusion	unknown to HOPS
treedepth	exclusion	unbounded
treelength	exclusion	constant
treewidth	exclusion	unbounded
twin-cover number	unknown to HOPS	unbounded
twin-width	exclusion	constant
vertex connectivity	unknown to HOPS	unknown to HOPS
vertex cover	unknown to HOPS	unbounded
vertex integrity	exclusion	unbounded

Results

1994 k-NLC graphs and polynomial algorithms by Wanke
- page 5 : graph class cograph has constant NLC-width – Fact 2.3. $G$ is a $1$-NLC graph if and only if $unlab(G)$ is a co-graph.
assumed
- graph class cograph is included in graph class perfect
- graph class perfect is not included in graph class cograph
- graph class co-cluster is included in graph class cograph
- graph class cograph is not included in graph class co-cluster
- graph class cograph has constant distance to cograph – by definition