Combinatorics / CONCEPT
Coloring Hereditarily Sparse Graphs
Hereditary average degree at most three and exclusion of four-cliques suffice for a proper three-coloring.
Closed
DIRECT PREREQUISITES1
DIRECT CONSEQUENCES0
PROOF DEPTH4
DOCUMENT LINKS1
Hereditary Sparsity and Three Colors
RELATIONSHIP ATLAS
Every connection, in context.
Direct recorded relationships
Proof dependencyStructural affinityDocument link
Certified topology / UPSTREAM
Prerequisites
Certified topology / DOWNSTREAM
Consequences
None recorded in this release.
RELATED KNOWLEDGE
Structural connections
- A Good Triple from a Two-Vertex Cutstructural-affinity · Closed
- A nearly empty Cartesian layerstructural-affinity · Closed
- Clique color extensionsstructural-affinity · Closed
- Coloring extensions and degree reductionstructural-affinity · Closed
- Components and Vertex Cutsstructural-affinity · Closed
- Connected encoder classes and powers of threestructural-affinity · Closed
- Deterministic Rainbow Two-Edge Choicesstructural-affinity · Closed
- Subcubic Brooks Theoremstructural-affinity · Closed
Documents & exposition
Other authored & advisory relationships
None recorded in this release.
LIBRARY / RELEASE VERSIONS
Content history
Loading release versions...
Browse the archiveCertified provenance