摘要：
A connected k-chromatic graph G is double-critical if for all edges uv of G the graph G-u-v is (k-2)-colorable.A long-standing conjecture,due to Erdrs and Lovász[1],states that the complete graphs are the only double-critical graphs.A connected graph G is called edge double-critical if it contains some pairs of nonadjacent edges,andx(G-e1-e2) =x(G)-2 for any two nonadjacent edges e1,e2 ∈ E(G),where x(G) denotes the chromatic number of G.Kawarabayashi et al.[2] and later,Lattanzio[3] proved that the complete graphs are the only edge double-critical graphs.In this note,we show that for a graph G,if ch(G-u-v) =ch(G)-2 for any vertices u,v ∈ V(G),then G is a complete graph,where ch(G) denotes the choice number of G.We also prove that the complete graphs are the only edge list double-critical graphs.%G是k-可着色的连通图,如果对于G中的所有边uv,都有G-u-v是(k-2)-可着色的,则称图G是双临界图.由Erd6s和Lovász提出了一个长期未能解决的猜想:完全图是唯一的双临界图[1].连通图G称为边双临界图,如果G中包含多对不相邻的边,并且对于任意一对不相邻的边e1,e2,都有x(G-et-e2)=x(G)-2,其中x(G)表示图G的色数.Kawarabayashi等人[2]及后来的Lattanzio[3]证明了完全图是唯一的边双临界图.文章证明了在图G中,对于任意的两个点u,v∈V(G),如果ch(G-u-v)=ch(G)-2,则图G是完全图,其中ch(G)表示G的选择数,还证明了完全图是唯一的列表双临界图.
