Li, Zhonghua; Wu, Baoyindurengy; An, Xinhui; Liu, Fengxia List bouble-critical graphs. (English) Zbl 1399.05078 J. Xinjiang Univ., Nat. Sci. 35, No. 1, 1-3 (2018). Summary: 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 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 non-adjacent edges, and \(\chi({G-{e_1}-{e_2}})=\chi(G)-2\) for any two non-adjacent edges \({e_1}, {e_2} \in E(G)\), where \(\chi(G)\) denotes the chromatic number of \(G\). Some previous researchers proved that the complete graphs are the only edge double-critical graphs. In this note, we show that for a graph \(G\), if \({\mathrm{ch}}({G-u-v})={\mathrm{ch}}(G)-2\) for any vertices \(u, v \in V(G)\), then \(G\) is a complete graph, where \({\mathrm{ch}}(G)\) denotes the choice number of \(G\). We also prove that the complete graphs are the only edge list double-critical graphs. MSC: 05C15 Coloring of graphs and hypergraphs Keywords:chromatic number; list coloring; double-critical graph PDFBibTeX XMLCite \textit{Z. Li} et al., J. Xinjiang Univ., Nat. Sci. 35, No. 1, 1--3 (2018; Zbl 1399.05078) Full Text: DOI