scientific article; zbMATH DE number 1285453
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)\).
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4242210)