acyclic chromatic number

tags: coloring

providers: ISGCI

Definition: Minimum number of colors such that there is a proper coloring and the graph induced on any two colors is acyclic.


Relations

OtherRelation fromRelation to
acyclic chromatic numberyellowequalequal
admissibilitygrayunknown to HOPSunknown to HOPS
arboricityredexclusionupper bound
average degreeredexclusionupper bound
average distanceblueexclusionexclusion
bandwidthgreenupper boundexclusion
bipartiteblueunboundedexclusion
bipartite numberblueexclusionexclusion
bisection bandwidthblueexclusionexclusion
blockblueunboundedexclusion
book thicknesslimeupper boundunknown to HOPS
boolean widthblueexclusionexclusion
bounded componentsgreenupper boundexclusion
bounded expansiongrayunknown to HOPSunknown to HOPS
boxicityredexclusionupper bound
branch widthgreenupper boundexclusion
c-closureblueexclusionexclusion
carving-widthgreenupper boundexclusion
chi-boundedmagentaexclusionunknown to HOPS
chordalblueunboundedexclusion
chordalityredexclusionupper bound
chromatic numberredexclusionupper bound
clique cover numberblueexclusionexclusion
clique-tree-widthblueexclusionexclusion
clique-widthblueexclusionexclusion
clusterblueunboundedexclusion
co-clusterblueunboundedexclusion
cographblueunboundedexclusion
completeblueunboundedexclusion
connectedblueexclusionavoids
contraction complexitygreenupper boundexclusion
cutwidthgreenupper boundexclusion
cyclegreenupper boundexclusion
cyclesgreenupper boundexclusion
d-admissibilitygrayunknown to HOPSunknown to HOPS
d-path-freegreenupper boundexclusion
degeneracyredexclusionupper bound
degree treewidthgreenupper boundexclusion
diameterblueexclusionexclusion
diameter+max degreegreenupper boundexclusion
distance to bipartiteblueexclusionexclusion
distance to blockblueexclusionexclusion
distance to bounded componentsgreenupper boundexclusion
distance to chordalblueexclusionexclusion
distance to clusterblueexclusionexclusion
distance to co-clusterblueexclusionexclusion
distance to cographblueexclusionexclusion
distance to completeblueexclusionexclusion
distance to edgelessgreenupper boundexclusion
distance to forestgreenupper boundexclusion
distance to intervalblueexclusionexclusion
distance to linear forestgreenupper boundexclusion
distance to maximum degreegreenupper boundexclusion
distance to outerplanargreenupper boundexclusion
distance to perfectblueexclusionexclusion
distance to planargreenupper boundexclusion
distance to starsgreenupper boundexclusion
domatic numberredexclusionupper bound
domination numberblueexclusionexclusion
domino treewidthgreenupper boundexclusion
edge clique cover numberblueexclusionexclusion
edge connectivityredexclusionupper bound
edge-cut widthgreenupper boundexclusion
edge-treewidthgreenupper boundexclusion
edgelessgreenupper boundavoids
excluded minorgrayunknown to HOPSunknown to HOPS
excluded planar minorgreenupper boundavoids
excluded top-minorgrayunknown to HOPSunknown to HOPS
feedback edge setgreenupper boundexclusion
feedback vertex setgreenupper boundexclusion
flip-widthmagentaexclusionunknown to HOPS
forestgreenupper boundexclusion
genusgreenupper boundexclusion
gridgreenupper boundexclusion
h-indexgreenupper boundexclusion
intervalblueunboundedexclusion
iterated type partitionsblueexclusionexclusion
linear clique-widthblueexclusionexclusion
linear forestgreenupper boundexclusion
linear NLC-widthblueexclusionexclusion
linear rank-widthblueexclusionexclusion
maximum cliqueredexclusionupper bound
maximum degreegreenupper boundexclusion
maximum independent setblueexclusionexclusion
maximum induced matchingblueexclusionexclusion
maximum leaf numbergreenupper boundexclusion
maximum matchinggreenupper boundexclusion
maximum matching on bipartite graphsgreenupper boundexclusion
merge-widthmagentaexclusionunknown to HOPS
mim-widthmagentaexclusionunknown to HOPS
minimum degreeredexclusionupper bound
mm-widthgreenupper boundexclusion
modular-widthblueexclusionexclusion
module-widthblueexclusionexclusion
monadically dependentmagentaexclusionunknown to HOPS
monadically stablegrayunknown to HOPSunknown to HOPS
neighborhood diversityblueexclusionexclusion
NLC-widthblueexclusionexclusion
NLCT-widthblueexclusionexclusion
nowhere densegrayunknown to HOPSunknown to HOPS
odd cycle transversalblueexclusionexclusion
outerplanargreenupper boundexclusion
overlap treewidthgreenupper boundexclusion
pathgreenupper boundexclusion
pathwidthgreenupper boundexclusion
pathwidth+maxdegreegreenupper boundexclusion
perfectblueunboundedexclusion
planargreenupper boundexclusion
radius-inf flip-widthblueexclusionexclusion
radius-r flip-widthmagentaexclusionunknown to HOPS
rank-widthblueexclusionexclusion
series-parallelgrayunknown to HOPSunknown to HOPS
shrub-depthblueexclusionexclusion
sim-widthmagentaexclusionunknown to HOPS
sizegreenupper boundexclusion
slim tree-cut widthgreenupper boundexclusion
sparse twin-widthcyanunknown to HOPSexclusion
stargreenupper boundexclusion
starsgreenupper boundexclusion
strong coloring numbergrayunknown to HOPSunknown to HOPS
strong d-coloring numbergrayunknown to HOPSunknown to HOPS
strong inf-coloring numbergreenupper boundexclusion
topological bandwidthgreenupper boundexclusion
treegreenupper boundexclusion
tree-cut widthgreenupper boundexclusion
tree-independence numbermagentaexclusionunknown to HOPS
tree-partition-widthgreenupper boundexclusion
treebandwidthgreenupper boundexclusion
treedepthgreenupper boundexclusion
treelengthmagentaexclusionunknown to HOPS
treespangreenupper boundexclusion
treewidthgreenupper boundexclusion
twin-cover numberblueexclusionexclusion
twin-widthblueexclusionexclusion
vertex connectivitygrayunknown to HOPSunknown to HOPS
vertex covergreenupper boundexclusion
vertex integritygreenupper boundexclusion
weak coloring numbergrayunknown to HOPSunknown to HOPS
weak d-coloring numbergrayunknown to HOPSunknown to HOPS
weak inf-coloring numbergreenupper boundexclusion
weakly sparseredexclusionupper bound
weakly sparse and merge widthgrayunknown to HOPSunknown to HOPS

Results