An edge-coloring of a graph \(G\) with colors \(1,...,t\) is called an interval \(t\)-coloring if all colors are used, and the colors of edges incident to any vertex of \(G\) are distinct and form an interval of integers. In 1991 Erdős constructed a bipartite graph with 27 vertices and maximum degree 13 which has no interval coloring. Erdős's count...

Interval non-edge-colorable bipartite graphs and multigraphs