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 -