The Ringel-Kotzig conjecture, also known as the graceful tree conjecture, is a major open problem in graph theory named after Gerhard Ringel and Anton Kotzig. A graceful labeling of a graph with m edges labels its vertices with distinct integers from 0 to m so that each edge is uniquely identified by the absolute difference between its two endpoint labels; a graph admitting such a labeling is called graceful. The conjecture hypothesizes that every tree is graceful, and it remains open. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
StatementEvery tree is graceful. 1 Progress Toward ResolutionStill open. The weaker Ringel conjecture was partially proven in 2020 by Montgomery, Pokrovskiy and Sudakov, and all trees up to 35 vertices are verified graceful. 1 Classification
Resolution Status Prize Status
Prize Status (category) Connections
In Branch
Source Graceful Labeling (Wikipedia)
Sources
1. Graceful Labeling (Wikipedia)
Ringel-Kotzig conjecture paragraph
It hypothesizes that all trees are graceful.
Status paragraph
It is still an open conjecture, although a related but weaker conjecture known as 'Ringel's conjecture' was partially proven in 2020 by Montgomery, Pokrovskiy and Sudakov.
- Lead section
In Branch: Graph Theory, Lead sentence
In graph theory, a graceful labeling of a graph with m edges is a labeling of its vertices with some subset of the integers from 0
View the SourceRingel-Kotzig Conjecture (Wikipedia)
Wikimedia FoundationLead sectionQuote, Lead section
It hypothesizes that all trees are graceful.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.