Colourings of path systems

Abstract: A

P_{m}

path in a graph is a path on

m

vertices. A

P_{m}

system of order

n > 1

is a partition of the edges of the complete graph

K_{n}

into

P_{m}

paths. A

P_{m}

system is said to be

k

-colourable if the vertex set of

K_{n}

can be partitioned into

k

sets called colour classes such that no path in the system is monochromatic. The system is

k

-chromatic if it is

k

-colourable but is not

(k - 1)

-colourable. If every

k

-colouring of a

P_{m}

system can be obtained from some

k

-colouring

p h i

by a permutation of the colours, we say that the system is uniquely

k

-colourable. In this paper, we first observe that there exists a

k

-chromatic

P_{m}

system for any

k g e q 2

and

m g e q 4

where

m

is even. Next, we prove that there exists an equitably 2-chromatic

P_{4}

system of order

n

for each admissible order

n

. We then show that for all

k g e q 3

, there exists a

k

-chromatic

P_{4}

system of order

n

for all sufficiently large admissible

n

. Finally, we show that there exists a uniquely 2-chromatic

P_{4}

system of order

n

for each admissible

n g e q 109

.

This page was built for publication: Colourings of path systems