Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650593 | Discrete Mathematics | 2008 | 11 Pages |
Abstract
The distance graph G(D)G(D) has the set of integers as vertices and two vertices are adjacent in G(D)G(D) if their difference is contained in the set D⊂ZD⊂Z. A conjecture of Zhu states that if the chromatic number of G(D)G(D) achieves its maximum value |D|+1|D|+1 then the graph has a triangle. The conjecture is proven to be true if |D|⩽3|D|⩽3. We prove that the chromatic number of a distance graph with D={a,b,c,d}D={a,b,c,d} is five only if either D={1,2,3,4k}D={1,2,3,4k} or D={a,b,a+b,b-a}D={a,b,a+b,b-a}. This confirms a stronger version of Zhu's conjecture for |D|=4|D|=4, namely, if the chromatic number achieves its maximum value then the graph contains K4K4.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Javier Barajas, Oriol Serra,