Distance graphs with maximum chromatic number |
| |
Authors: | Javier Barajas |
| |
Institution: | Universitat Politècnica de Catalunya, Jordi Girona, 1, E-08034 Barcelona, Spain |
| |
Abstract: | The distance graph G(D) has the set of integers as vertices and two vertices are adjacent in G(D) if their difference is contained in the set D⊂Z. A conjecture of Zhu states that if the chromatic number of G(D) achieves its maximum value |D|+1 then the graph has a triangle. The conjecture is proven to be true if |D|?3. We prove that the chromatic number of a distance graph with D={a,b,c,d} is five only if either D={1,2,3,4k} or D={a,b,a+b,b-a}. This confirms a stronger version of Zhu's conjecture for |D|=4, namely, if the chromatic number achieves its maximum value then the graph contains K4. |
| |
Keywords: | Distance graphs Chromatic number |
本文献已被 ScienceDirect 等数据库收录! |
|