Combinatorics / CONCEPT
Brooks' theorem and connected exceptions
Every finite graph that cannot be colored with its maximum degree contains a maximum-degree-plus-one clique or an odd cycle at maximum degree two. Connected exceptions are complete graphs or entire odd cycles.
Closed
DIRECT PREREQUISITES1
DIRECT CONSEQUENCES1
PROOF DEPTH4
DOCUMENT LINKS0
The arbitrary-degree alternative
RELATIONSHIP ATLAS
Every connection, in context.
Direct recorded relationships
Proof dependencyStructural affinityDocument link
Certified topology / UPSTREAM
Prerequisites
Certified topology / DOWNSTREAM
Consequences
RELATED KNOWLEDGE
Structural connections
- Clique and odd-cycle surgerystructural-affinity · Closed
- Clique color extensionsstructural-affinity · Closed
- Closed walks in regular graphsstructural-affinity · Closed
- Coloring extensions and degree reductionstructural-affinity · Closed
- Cycle partitionsstructural-affinity · Closed
- Cyclic tridiagonal determinants and transfer tracesstructural-affinity · Closed
- Defsstructural-affinity · Closed
- The cycle comparison boundstructural-affinity · Closed
Documents & exposition
None recorded in this release.
Other authored & advisory relationships
None recorded in this release.
LIBRARY / RELEASE VERSIONS
Content history
Loading release versions...
Browse the archiveCertified provenance