ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

PDF Problems Column

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


 Zdzisław Skupień

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


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

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

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

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

 Theorem L′ (Skupień [2]). There exists an edge t-remainder R in Kp such that the floor class ⎣Kp/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.


[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