← All problems

Akbari–Kano conjecture on two-valued factors of odd-regular graphs

12 years old · traced to

Let rr be a positive odd integer, let tt satisfy 0≤t≤r0\leq t\leq r, and let an {r−t,t}\{r-t,t\}-factor be a spanning subgraph in which every vertex has degree either r−tr-t or tt.

Akbari–Kano conjecture. Every rr-regular graph has an {r−t,t}\{r-t,t\}-factor.

The paper records partial positive and negative results identifying ranges of rr and tt for which such factors must exist or can fail to exist.

References

2 papers in this index state this conjecture (2014–2016). The statement above is taken from the most recent of them; the others are arXiv:1410.1219.

Status

  • Refuted: Maria Axenovich and Jonathan Rollin. Brooks Type Results for Conflict-Free Colorings and {a, b}-factors in graphs (Discrete Mathematics 338(12):2295–2301; arXiv:1410.1219, 2015) https://arxiv.org/abs/1410.1219

Source: Anton Bernshteyn, Omid Khormali, Ryan R. Martin, Jonathan Rollin, Danny Rorabaugh, Songling Shan and Andrew J. Uzzell, “Regular colorings and factors of regular graphs”, arXiv:1603.09384 (2016).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.