×

List bouble-critical graphs. (English) Zbl 1399.05078

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
PDFBibTeX XMLCite
Full Text: DOI