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
10 May 1999
0 references
coloring
0 references
edge coloring
0 references
total coloring
0 references
interval graph
0 references
0.9075291752815248
0 references
0.816182553768158
0 references
0.8008555769920349
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