PDF Problems Column

Discussiones Mathematicae Graph Theory 22(2) (2002) 361
DOI: https://doi.org/10.7151/dmgt.1181

CLIQUE PARTS INDEPENDENT OF REMAINDERS

 Zdzisław Skupień

 Faculty of Applied Mathematics
University of Mining and Metallurgy AGH
al. Mickiewicza 30, 30-059 Kraków, Poland

e-mail: skupien@uci.agh.edu.pl

Let p and t stand for positive integers. Let R denote an edge subset of size |R| = (^p₂) mod t in the complete graph K_p. Call R a remainder (or an edge t-remainder) in the clique K_p.

Conjecture L (L reminds of floor symbol). The floor class ⎣K_p/t⎦ is nonempty. In other words, there exists a graph F such that, for each edge t-remainder R in K_p, F is a tth part of K_p−R, i.e., F ∈ ⎣K_p/t⎦.

Conjecture L implies the following conjecture stated in [2].

 Conjecture L*. For each edge t-remainder R in K_p, there is an F_R ∈ (K_p−R)/t = :⎣K_p/t⎦_R.

 Theorem L′ (Skupień [2]). There exists an edge t-remainder R in K_p such that the floor class ⎣K_p/t⎦_R is nonempty.

 Plantholt's theorem [1] on chromatic index is equivalent to the truth of Conjecture L with t = p−1 and p being odd.

     Conjecture L can be seen true for many pairs p, t, e.g., if t ≥ p−1 or t is small: t ≤ 5. If t is a constant (t ≥ 4), both Conjectures can be reduced to some values of p in the interval t+2 ≤ p ≤ 4t−5.

References

[1]	M. Plantholt, The chromatic index of graphs with a spanning star, J. Graph Theory 5 (1981) 45-53, doi: 10.1002/jgt.3190050103.
[2]	Z. Skupień, The complete graph t-packings and t-coverings, Graphs Combin. 9 (1993) 353-363, doi: 10.1007/BF02988322.

Received 28 November 2001