Subdivided graphs preserve interval colorability
Subdivided graphs preserve interval colorability
Let be a simple graph. Write for the graph obtained by subdividing every edge of once, and let denote the class of graphs admitting an interval coloring.
Subdivision conjecture. If , then
This would generalize the known result that the subdivision of every regular graph belongs to ; the statement for general simple graphs is posed as an interesting open problem.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.