TY - JOUR
T1 - Adding Edges to Increase the Chromatic Number of a Graph
AU - Kostochka, Alexandr
AU - Nešetřil, Jaroslav
N1 - Funding Information:
DMS-1266016 and by grants 15-01-05867 and 16-01-00499 of the Russian Foundation for Basic Research.
PY - 2016/7/1
Y1 - 2016/7/1
N2 - If n ≤ k + 1 and G is a connected n-vertex graph, then one can add edges to G so that the resulting graph contains the complete graph K k+1. This yields that for any connected graph G with at least k + 1 vertices, one can add edges to G so that the resulting graph has chromatic number > k. A long time ago, Bollobás suggested that for every k ≤ 3 there exists a k-chromatic graph Gk such that after adding to it any-1 edges, the chromatic number of the resulting graph is still k. In this note we prove this conjecture.
AB - If n ≤ k + 1 and G is a connected n-vertex graph, then one can add edges to G so that the resulting graph contains the complete graph K k+1. This yields that for any connected graph G with at least k + 1 vertices, one can add edges to G so that the resulting graph has chromatic number > k. A long time ago, Bollobás suggested that for every k ≤ 3 there exists a k-chromatic graph Gk such that after adding to it any-1 edges, the chromatic number of the resulting graph is still k. In this note we prove this conjecture.
UR - http://www.scopus.com/inward/record.url?scp=84962088947&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84962088947&partnerID=8YFLogxK
U2 - 10.1017/S0963548316000146
DO - 10.1017/S0963548316000146
M3 - Article
AN - SCOPUS:84962088947
VL - 25
SP - 592
EP - 594
JO - Combinatorics Probability and Computing
JF - Combinatorics Probability and Computing
SN - 0963-5483
IS - 4
ER -