perfect

tags: coloring

providers: ISGCI

Definition: Has maximum clique equal to chromatic number.


Relations

OtherRelation fromRelation to
acyclic chromatic numberblueexclusionunbounded
admissibilityblueexclusionunbounded
arboricityblueexclusionunbounded
average degreeblueexclusionunbounded
average distanceblueexclusionunbounded
bandwidthblueexclusionunbounded
bipartitegreeninclusionexclusion
bipartite numberblueexclusionunbounded
bisection bandwidthblueexclusionunbounded
blockgreenupper boundexclusion
book thicknessblueexclusionunbounded
boolean widthblueexclusionunbounded
bounded componentsblueexclusionunbounded
bounded expansionblueexclusionavoids
boxicitymagentaexclusionunknown to HOPS
branch widthblueexclusionunbounded
c-closuremagentaexclusionunknown to HOPS
carving-widthblueexclusionunbounded
chi-boundedredexclusionupper bound
chordalgreeninclusionexclusion
chordalitymagentaexclusionunknown to HOPS
chromatic numberblueexclusionunbounded
clique cover numberblueexclusionunbounded
clique-tree-widthblueexclusionunbounded
clique-widthblueexclusionunbounded
clustergreenupper boundexclusion
co-clustergreenupper boundexclusion
cographgreeninclusionexclusion
completegreenupper boundexclusion
connectedcyanunknown to HOPSavoids
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 blockblueexclusionunbounded
distance to bounded componentsblueexclusionunbounded
distance to chordalblueexclusionunbounded
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
gridgreenupper boundexclusion
h-indexblueexclusionunbounded
intervalgreenupper boundexclusion
iterated type partitionsblueexclusionunbounded
linear clique-widthblueexclusionunbounded
linear forestgreenupper boundexclusion
linear NLC-widthblueexclusionunbounded
linear rank-widthblueexclusionunbounded
maximum cliqueblueexclusionunbounded
maximum degreeblueexclusionunbounded
maximum independent setblueexclusionunbounded
maximum induced matchingblueexclusionunbounded
maximum leaf numberblueexclusionunbounded
maximum matchingblueexclusionunbounded
maximum matching on bipartite graphsgreenupper boundunbounded
merge-widthmagentaexclusionunknown to HOPS
mim-widthmagentaexclusionunknown to HOPS
minimum degreeblueexclusionunbounded
mm-widthblueexclusionunbounded
modular-widthblueexclusionunbounded
module-widthblueexclusionunbounded
monadically dependentmagentaexclusionunknown to HOPS
monadically stablemagentaexclusionunknown to HOPS
neighborhood diversityblueexclusionunbounded
NLC-widthblueexclusionunbounded
NLCT-widthblueexclusionunbounded
nowhere densemagentaexclusionunknown to HOPS
odd cycle transversalblueexclusionunbounded
outerplanarcyanunknown to HOPSexclusion
overlap treewidthblueexclusionunbounded
pathgreenupper boundexclusion
pathwidthblueexclusionunbounded
pathwidth+maxdegreeblueexclusionunbounded
perfectyellowequalequal
planarblueexclusionexclusion
radius-inf flip-widthblueexclusionunbounded
radius-r flip-widthmagentaexclusionunknown to HOPS
rank-widthblueexclusionunbounded
series-parallelgrayunknown to HOPSunknown to HOPS
shrub-depthblueexclusionunbounded
sim-widthmagentaexclusionunknown to HOPS
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 numbermagentaexclusionunknown to HOPS
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