A theorem of Gaddum and Nordhaus

   Given a graph G with n vertices. Let G' be the complementary graph of G, which has the same vertex set as G and two vertices are adjacent in G' iff they are not adjacent in G. Let \chi(G) and \chi(G') be the chromatic number of G and G'. In 1956, two mathematicians Edward Alfred Nordhaus and Jerry William Gaddum obtained the following estimates:
   (i) 2\sqrt{n} <= \chi(G) + \chi(G') <= n + 1
   (ii) n <= \chi(G)\chi(G') <= ((n + 1)/2)^2
   The result was written in the paper "On complementary graphs", which was published in The American Mathematical Monthly. To show that \chi(G)\chi(G') >= n, we assume that the vertices of G can be colored by k colors and the vertices of G' can be colored by k' colors. For each vertex v, let G(v) be the color of v in G and G'(v) be the color of v in G'. Since for any two different vertices v, u, either v is adjacent to u in G (which means that G(v) and G(u) must be different) or v is adjacent to u in G' (which means that G'(v) and G'(u) must be different), the n pairs (G(v), G'(v)), where v ranges over the vertex set of G, are pairwise different. As G(v) can be chosen in k ways and G'(v) can be chosen in k' ways, we must have k*k' >= n. This shows that \chi(G)\chi(G') >= n. 
   Next, to show that \chi(G) + \chi(G') <= n + 1, we consider a coloring of the vertices of G by k = \chi(G) colors c(1), c(2), ..., c(k). Let C(i) be the set of vertices colored with c(i). We show that G' can be colored with at most n - k + 1 colors by proceeding as follows: 
   - Set COLOR = 0, VERTICES = 0. COLOR represents the number of colors used and VERTICES represents the number of vertices that are colored. 
   - Find a vertex v in C(2) that is adjacent to a vertex u in C(1). Such u, v must exist, otherwise we can color alternatively as follows: all vertices in C(1) \cup C(2) are colored with c(1) and all vertices in C(i) are colored with c(i) for i = 3, 4, ..., k. This requires only k - 1, contradicting the fact that \chi(G) = k. 
   - After finding u, v, color u, v with the same color c'(1) in G'. Reset COLOR = 1, VERTICES = 2. 
   - Similarly, at step i (i = 2, 3, ..., k - 1), we do as follows: 
   + Find a vertex v in C(i + 1) that is adjacent to i vertices v(1) \in C(1), v(2) \in C(2), ..., v(i) \in C(i). Similarly as above, such v and v(1), v(2), ..., v(i) must exist. Otherwise, for each v in C(i + 1), there exists j <= i such that v is not adjacent to any vertex in C(j) and v can be colored with c(j) instead. By doing this for all vertices v in C(i + 1), the colored c(i + 1) can be removed from the list of colors, which contradicts k = \chi(G). 
   + If v(1), v(2), ..., v(i) are all colored in the previous steps, we can simply color v with the same color as v(1). In this case, set VERTICES := VERTICES + 1, while COLOR remains unchanged.
   + Otherwise, we pick v(j) that is not colored in the previous step and color v, v(j) with a new color that is not used before. Set VERTICES := VERTICES + 2, COLOR := COLOR + 1. 
   At each step, the difference VERTICES - COLOR increase by 1. Therefore, after step k - 1, VERTICES - COLOR = k - 1. By assigning n - VERTICES different unused colors to the n - VERTICES uncolored vertices, we obtain a coloring of G' with COLOR + n - VERTICES = n - k + 1 colors. This shows that \chi(G) + \chi(G') <= n + 1. 
   The inequality \chi(G) + \chi(G') >= 2\sqrt{n} follows easily by \chi(G)\chi(G') >= n and the AM-GM inequality. Similarly, the inequality \chi(G)\chi(G') <= ((n + 1)/2)^2 follows easily from \chi(G) + \chi(G') <= n + 1 and the AM-GM inequality. 

Nhận xét

Đăng nhận xét

Bài đăng phổ biến từ blog này

Trước khi đi du học ngành toán tại Đức

Hình ảnh
Bài viết này tổng hợp những câu chuyện mang tính cá nhân về quá trình tôi chuẩn bị cho chuyến du học tại Đại học Bonn (Đức), một ngôi trường khá danh tiếng về ngành toán. Tôi đã chia sẻ khá đầy đủ những kinh nghiệm hữu ích cho mọi người trong  quyển guideline này , do đó trong bài viết này tôi sẽ đề cập đến những khía cạnh khác, chẳng hạn như trải nghiệm của tôi với các giáo sư ở Đức, hướng nghiên cứu của bản thân, hay là cả những câu chuyện mang tính giải trí cực cao.  1. Trước khi có ý định đi Đức, tôi KHÔNG BIẾT GÌ về Đại học Bonn và những trường khác ở Đức      Hồi năm thứ 1 và năm thứ 2, tôi chỉ tập trung học chứ gần như không tìm hiểu về các nhà toán học cũng như nơi công tác của họ. Lúc đó tôi chỉ thấy các trường ở Mỹ hấp dẫn vì có khá nhiều hướng nghiên cứu, hơn nữa hầu hết các trường đều có các giáo sư làm về đại số  và tổ hợp , những lĩnh vực tôi yêu thích nhất vào lúc đó. Tôi cũng biết rằng  Giáo sư Phan Thành Nam là một trong những cựu si...
Đọc thêm

Some remarkable statistics about the major of (pure) mathematics at several universities in the world

Hình ảnh
1. The number of PhD/Graduate students at some US universities    Many US universities indicated all of their graduate students on their websites. For example, the following image shows the list of graduate students in mathematics at Harvard University.     Based on these lists, I just counted the number of graduate students at some universities and got the following result(s): MIT has 122 students, Cornell University has 80 students, Texas A&M University has 105 students, Stanford University has 65 students, Harvard University has 64 students, Yale University has 46 students, University of Utah has 90 students, The University of Chicago has 81 students, City University of New York has 76 students and University of California, Berkeley (UCB) has 175 students.  2. The number of PhD/Graduate students from several universities who later became speakers at International Congress of Mathematicians    Being invited at International Congress of Mathe...
Đọc thêm

Some interesting facts about Vietnamese

Here is a collection of interesting facts about the language of Vietnamese (tiếng Việt) that I just found out when talking to my friends, who are all Europeans, in Bonn (Germany).  1. In Vietnamese, grandson and nephew are called the same (cháu trai). Similarly, granddaughter and niece are also called the same (cháu gái).  2. In Vietnamese, you can use the same pronoun "em" to call your younger sibling, no matter whether it is your younger brother or your younger sister. Similarly, this pronoun can be used to call someone who is just a few years younger than you, no matter whether this person is a man or a woman.  3. However, when referring to your older sibling, you must use the pronoun "anh" to call your older brother and the pronoun "chị" to cold your older sister. Similarly, you can use the pronoun "anh" to call a boy who is just a few years older than you and the pronoun "chị" to call a girl who is just a few years older than you. ...
Đọc thêm