Let the chromatic number of G, the edge chromatic number of G and thetotal chromatic number of G be denoted by x（G）, x1（G） and x2（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|-ε1≤x（G）+x1（G）≤2p-2 and 0≤x（G）·x1（G）≤（p-1）2 for p≥2,（ii）|2p1/2|+ε1≤x（G）+x2（G）≤2p-1 and 0≤x（G）·x2（G）≤p（p-1） for p≥3,（iii）p≤x1（G）+x2（G）≤2p-1 and 0≤x1（G）·x2（G）≤p（p-1） for p≥3,where ε1=0, if p1/2 is an odd integer, 1, otherwise,ε2=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.
展开▼
