Impropriety bound for 2-trees

Let GG be a 2-tree, that is, a graph obtained from a triangle by repeatedly adding a new vertex adjacent to both endpoints of an existing edge. Let μint(G)\mu_{\operatorname{int}}(G) denote the impropriety of an interval coloring of GG. 2-tree impropriety conjecture.

μint(G)2.\mu_{\operatorname{int}}(G)\leq 2.

The conjecture is motivated by the fact that the smallest 2-tree, K3K_3, has impropriety 22, while the source reports no 2-tree with larger impropriety. Its status is unresolved in the supplied text.

Sources & referencesView supporting material

Primary source

MacKenzie Carr, Eun-Kyung Cho, Nicholas Crawford, Vesna Iršič, Leilani Pai and Rebecca Robinson, “On the interval coloring impropriety of graphs”, arXiv:2312.14881 (2024).

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.