The edge-face chromatic number Xef （G） of a plane graph G is the least number of colors assigned to the edges and faces such that every adjacent or incident pair of them receives different colors. In this article, t...The edge-face chromatic number Xef （G） of a plane graph G is the least number of colors assigned to the edges and faces such that every adjacent or incident pair of them receives different colors. In this article, the authors prove that every 2-connected plane graph G with △（G）≥｜G｜ - 2≥9 has Xef（G） = △（G）.展开更多
Let the chromatic number of G, the edge chromatic number of G and thetotal chromatic number of G be denoted by x（G）, x<sub>1</sub>（G） and x<sub>2</sub>（G）, respectively. Forany simple gra...Let the chromatic number of G, the edge chromatic number of G and thetotal chromatic number of G be denoted by x（G）, x<sub>1</sub>（G） and x<sub>2</sub>（G）, respectively. Forany simple graph G of order p and its complement G, the following inequalities of theNordhaus-Gaddum class are obtained:（i）|2p<sup>1/2</sup>|-ε<sub>1</sub>≤x（G）+x<sub>1</sub>（G）≤2p-2 and 0≤x（G）·x<sub>1</sub>（G）≤（p-1）<sup>2</sup> for p≥2,（ii）|2p<sup>1/2</sup>|+ε<sub>1</sub>≤x（G）+x<sub>2</sub>（G）≤2p-1 and 0≤x（G）·x<sub>2</sub>（G）≤p（p-1） for p≥3,（iii）p≤x<sub>1</sub>（G）+x<sub>2</sub>（G）≤2p-1 and 0≤x<sub>1</sub>（G）·x<sub>2</sub>（G）≤p（p-1） for p≥3,where ε<sub>1</sub>=0, if p<sup>1/2</sup> is an odd integer, 1, otherwise,ε<sub>2</sub>=1, if p<sup>1/2</sup> 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.展开更多
基金This research is supported by NNSF of China(40301037, 10471131)
文摘The edge-face chromatic number Xef （G） of a plane graph G is the least number of colors assigned to the edges and faces such that every adjacent or incident pair of them receives different colors. In this article, the authors prove that every 2-connected plane graph G with △（G）≥｜G｜ - 2≥9 has Xef（G） = △（G）.
文摘Let the chromatic number of G, the edge chromatic number of G and thetotal chromatic number of G be denoted by x（G）, x<sub>1</sub>（G） and x<sub>2</sub>（G）, respectively. Forany simple graph G of order p and its complement G, the following inequalities of theNordhaus-Gaddum class are obtained:（i）|2p<sup>1/2</sup>|-ε<sub>1</sub>≤x（G）+x<sub>1</sub>（G）≤2p-2 and 0≤x（G）·x<sub>1</sub>（G）≤（p-1）<sup>2</sup> for p≥2,（ii）|2p<sup>1/2</sup>|+ε<sub>1</sub>≤x（G）+x<sub>2</sub>（G）≤2p-1 and 0≤x（G）·x<sub>2</sub>（G）≤p（p-1） for p≥3,（iii）p≤x<sub>1</sub>（G）+x<sub>2</sub>（G）≤2p-1 and 0≤x<sub>1</sub>（G）·x<sub>2</sub>（G）≤p（p-1） for p≥3,where ε<sub>1</sub>=0, if p<sup>1/2</sup> is an odd integer, 1, otherwise,ε<sub>2</sub>=1, if p<sup>1/2</sup> 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.
