Edge Coloring a K-Tree into Two Smaller Trees

Dilip Chhajed

Research output: Contribution to journalArticlepeer-review


The problem of the edge coloring partial k-tree into two partial p- and q-trees with p, q < k is considered. An algorithm is provided to construct such a coloring with p + q = k. Usefulness of this result in a Lagrangian decomposition framework to solve certain combinatorial optimization problems is discussed.

Original languageEnglish (US)
Pages (from-to)191-194
Number of pages4
Issue number4
StatePublished - Jul 1997


  • Analysis of algorithms
  • Facilities planning
  • Location
  • Networks/graphs
  • Suboptimal algorithms
  • Theory

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Edge Coloring a K-Tree into Two Smaller Trees'. Together they form a unique fingerprint.

Cite this