No label defined (Q4242210)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1285453
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 1285453

      Statements

      0 references
      10 May 1999
      0 references
      coloring
      0 references
      edge coloring
      0 references
      total coloring
      0 references
      interval graph
      0 references
      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)\).
      0 references

      Identifiers