列表双临界图（英文）

List Bouble-Critical Graphs

G是k-可着色的连通图,如果对于G中的所有边uv,都有G-u-v是(k-2)-可着色的,则称图G是双临界图.由Erdo?s和Lova′sz提出了一个长期未能解决的猜想:完全图是唯一的双临界图[1].连通图G称为边双临界图,如果G中包含多对不相邻的边,并且对于任意一对不相邻的边e1,e2,都有χ(G-e1-e2)=χ(G)-2,其中χ(G)表示图G的色数.Kawarabayashi等人[2]及后来的Lattanzio[3]证明了完全图是唯一的边双临界图.文章证明了在图G中,对于任意的两个点u,v∈V(G),如果ch(G-u-v)=ch(G)-2,则图G是完全图,其中ch(G)表示G的选择数,还证明了完全图是唯一的列表双临界图.

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 Erd o？s and Lova′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, and χ（G-e1-e2） =χ（G）-2 for any two nonadjacent edges e1, e2∈ E（G）, where χ（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.