SOME THEOREMS OF THE NORDHAUS-GADDUM CLASS

摘要

Let the chromatic number of G, the edge chromatic number of G and thetotal chromatic number of G be denoted by x（G）, x₁（G） and x₂（G）, respectively. Forany simple graph G of order p and its complement G, the following inequalities of theNordhaus-Gaddum class are obtained:（i）|2p1/2|-ε₁≤x（G）+x₁（G）≤2p-2 and 0≤x（G）·x₁（G）≤（p-1）2 for p≥2,（ii）|2p1/2|+ε₁≤x（G）+x₂（G）≤2p-1 and 0≤x（G）·x₂（G）≤p（p-1） for p≥3,（iii）p≤x₁（G）+x₂（G）≤2p-1 and 0≤x₁（G）·x₂（G）≤p（p-1） for p≥3,where ε₁=0, if p1/2 is an odd integer, 1, otherwise,ε₂=1, if p1/2 is an even integer, 0, otherwise,and [x] denotes the ceiling of x. We also show that these bounds are sharp for everypositive integer p.