A new approach to the chromatic number of the square of Kneser graph |
| |
Authors: | Jeong-Hyun Kang |
| |
Institution: | Department of Mathematics, University of West Georgia, Carrollton, GA 30118, USA |
| |
Abstract: | The vertices of Kneser graph are the subsets of of cardinality , two vertices are adjacent if and only if they are disjoint. The square of a graph is defined on the vertex set of with two vertices adjacent if their distance in is at most 2. Z. Füredi, in 2002, proposed the problem of determining the chromatic number of the square of the Kneser graph. The first non-trivial problem arises when . It is believed that where is a constant, and yet the problem remains open. The best known upper bounds are by Kim and Park: for 1 (Kim and Park, 2014) and for (Kim and Park, 2016). In this paper, we develop a new approach to this coloring problem by employing graph homomorphisms, cartesian products of graphs, and linear congruences integrated with combinatorial arguments. These lead to , where is a constant in , depending on . |
| |
Keywords: | Square of Kneser graph Chromatic number Kneser graph |
本文献已被 ScienceDirect 等数据库收录! |
|