Subdivided graphs preserve interval colorability

At least 12 years old · documented by

Let GG be a simple graph. Write S(G)S(G) for the graph obtained by subdividing every edge of GG once, and let N\mathfrak{N} denote the class of graphs admitting an interval coloring.

Subdivision conjecture. If G∈NG\in \mathfrak{N}, then

S(G)∈N.S(G)\in \mathfrak{N}.

This would generalize the known result that the subdivision of every regular graph belongs to N\mathfrak{N}; the statement for general simple graphs is posed as an interesting open problem.

References

Primary source

Petros A. Petrosyan and Hrant H. Khachatrian, “Interval non-edge-colorable bipartite graphs and multigraphs”, arXiv:1301.3811 (2013).

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.