Maximum independent edge set conjecture for 3-token graphs of paths
Maximum independent edge set conjecture for 3-token graphs of paths
Let be the path graph on vertices, and let denote its -token graph. Write for the maximum size of an independent edge set in a graph . For any , the -token graph satisfies
Maximum independent edge set conjecture.
and equivalently
The conjecture asserts that the displayed independent edge sets are maximum. The proposed formulas are based on explicit constructions for even and odd ; determining whether these constructions are largest remains an open problem for the -token graphs of path graphs.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Felicia Servina Djuang, Arizka Yuliana, Widi Bagaskara and Yeni Susanti, “Exploring the 3-Token Graph of Particular Graphs”, arXiv:2511.10875 (2025).
Additional references
2 papers in this index state this conjecture (2021–2025). The statement above is taken from the most recent of them; the others are arXiv:2107.00295.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.