×

Edge and total coloring of interval graphs. (Russian) Zbl 0913.05044

Let \(\chi_e(G)\) and \(\chi_{ve}(G)\) be the edge and total chromatic number of a graph \(G\). It is clear that \(\chi_{e}(G)\geq\Delta(G)\) and \(\chi_{ve}(G)\geq\Delta(G)+1\), where \(\Delta(G)\) is the maximum degree of \(G\). By Vizing’s theorem, \(\chi_{e}(G)\leq\Delta(G)+1\) for each \(G\). Behzad and Vizing conjectured that \(\chi_{ve}(G)\leq\Delta(G)+2\) for each \(G\). It is NP-hard to find both \(\chi_{ve}(G)\) and \(\chi_e(G)\) for an arbitrary graph \(G\). Precise values of \(\chi_{ve}(G)\) and \(\chi_e(G)\) are known only for narrow classes of graphs.
The graphs of intersections of finite closed intervals on the straight line are called interval graphs. For interval graphs \(G\), it is proven that \(\chi_{ve}(G)\leq\Delta(G)+2\) and that the equality \(\Delta(G)=2m+1\) implies \(\chi_{e}(G)=\Delta(G)\).

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite