perfect
tags: coloring
equivalent to: perfect
providers: ISGCI
Relations
| Other | Relation from | Relation to |
|---|---|---|
| acyclic chromatic number | exclusion | unbounded |
| arboricity | exclusion | unbounded |
| average degree | exclusion | unbounded |
| average distance | exclusion | unbounded |
| bandwidth | exclusion | unbounded |
| bipartite | inclusion | exclusion |
| bipartite number | exclusion | unknown to HOPS |
| bisection bandwidth | exclusion | unbounded |
| block | inclusion | exclusion |
| book thickness | exclusion | unbounded |
| boolean width | exclusion | unbounded |
| bounded components | exclusion | unbounded |
| boxicity | exclusion | unknown to HOPS |
| branch width | exclusion | unbounded |
| c-closure | exclusion | unknown to HOPS |
| carving-width | exclusion | unbounded |
| chordal | inclusion | exclusion |
| chordality | exclusion | unknown to HOPS |
| chromatic number | exclusion | unbounded |
| clique cover number | exclusion | unbounded |
| clique-tree-width | exclusion | unbounded |
| clique-width | exclusion | unbounded |
| cluster | inclusion | exclusion |
| co-cluster | inclusion | exclusion |
| cograph | inclusion | exclusion |
| complete | inclusion | exclusion |
| connected | unknown to HOPS | unknown to HOPS |
| cutwidth | exclusion | unbounded |
| cycle | unknown to HOPS | exclusion |
| cycles | exclusion | exclusion |
| d-path-free | exclusion | unbounded |
| degeneracy | exclusion | unbounded |
| degree treewidth | exclusion | unbounded |
| diameter | exclusion | unbounded |
| diameter+max degree | exclusion | unbounded |
| disjoint cycles | exclusion | exclusion |
| distance to bipartite | unknown to HOPS | unbounded |
| distance to block | unknown to HOPS | unbounded |
| distance to bounded components | exclusion | unbounded |
| distance to chordal | unknown to HOPS | unbounded |
| distance to cluster | unknown to HOPS | unbounded |
| distance to co-cluster | unknown to HOPS | unbounded |
| distance to cograph | unknown to HOPS | unbounded |
| distance to complete | unknown to HOPS | unbounded |
| distance to edgeless | unknown to HOPS | unbounded |
| distance to forest | unknown to HOPS | unbounded |
| distance to interval | unknown to HOPS | unbounded |
| distance to linear forest | unknown to HOPS | unbounded |
| distance to maximum degree | exclusion | unbounded |
| distance to outerplanar | exclusion | unbounded |
| distance to perfect | unknown to HOPS | 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 | unbounded |
| edge connectivity | exclusion | unbounded |
| edgeless | inclusion | exclusion |
| feedback edge set | unknown to HOPS | unbounded |
| feedback vertex set | unknown to HOPS | unbounded |
| forest | inclusion | exclusion |
| genus | exclusion | unbounded |
| girth | exclusion | unbounded |
| grid | inclusion | exclusion |
| h-index | exclusion | unbounded |
| inf-flip-width | exclusion | unbounded |
| interval | inclusion | exclusion |
| iterated type partitions | exclusion | unbounded |
| linear clique-width | exclusion | unbounded |
| linear forest | inclusion | exclusion |
| linear NLC-width | exclusion | unbounded |
| linear rank-width | exclusion | unbounded |
| maximum clique | exclusion | unbounded |
| maximum degree | exclusion | unbounded |
| maximum independent set | exclusion | unbounded |
| maximum induced matching | exclusion | unbounded |
| maximum leaf number | unknown to HOPS | unbounded |
| maximum matching | unknown to HOPS | unbounded |
| maximum matching on bipartite graphs | inclusion | unbounded |
| mim-width | exclusion | unknown to HOPS |
| minimum degree | exclusion | unbounded |
| mm-width | exclusion | unbounded |
| modular-width | exclusion | unbounded |
| module-width | exclusion | unbounded |
| neighborhood diversity | exclusion | unbounded |
| NLC-width | exclusion | unbounded |
| NLCT-width | exclusion | unbounded |
| odd cycle transversal | unknown to HOPS | unbounded |
| outerplanar | exclusion | exclusion |
| path | inclusion | exclusion |
| pathwidth | exclusion | unbounded |
| pathwidth+maxdegree | exclusion | unbounded |
| planar | exclusion | exclusion |
| radius-r flip-width | exclusion | unknown to HOPS |
| rank-width | exclusion | unbounded |
| shrub-depth | exclusion | unbounded |
| sim-width | exclusion | unknown to HOPS |
| star | inclusion | exclusion |
| stars | inclusion | exclusion |
| topological bandwidth | exclusion | unbounded |
| tree | inclusion | exclusion |
| tree-independence number | exclusion | unknown to HOPS |
| treedepth | exclusion | unbounded |
| treelength | exclusion | unknown to HOPS |
| treewidth | exclusion | unbounded |
| twin-cover number | unknown to HOPS | unbounded |
| twin-width | exclusion | unknown to HOPS |
| vertex connectivity | unknown to HOPS | unknown to HOPS |
| vertex cover | unknown to HOPS | unbounded |
| vertex integrity | exclusion | unbounded |
Results
- 2017 Graph Theory by Diestel
- page 135 : perfect – A graph is called perfect if every induced subgraph $H \subseteq G$ has chromatic number $\chi(H)=\omega(H)$, i.e. if the trivial lower bound of $\omega(H)$ colours always suffices to colour the vertices of $H$.
- assumed
- graph class chordal is included in graph class perfect
- graph class perfect is not included in graph class chordal
- graph class cograph is included in graph class perfect
- graph class perfect is not included in graph class cograph
- graph class bipartite is included in graph class perfect
- graph class perfect is not included in graph class bipartite
- graph class perfect has constant distance to perfect – by definition