An exact value for the path-chromatic index of a complete graph

  • Frank Harary
  • Źsolt Tuza

Abstract

We prove that the edge of Kn cannot be partitioned into less than (n-1)/t Pi+2-free subgraphs. We show that this inequality is sharp and characterize the edge partitions which attain it. In the process, we point out a surprising connection between the combinatorial designs and the conditional chromatic index.
Published
1991-05-01
Section
Articoli