I'm interested in knowing if finding the edge-chromatic number of a $k$-uniform $k$-partite hypergraph is NP-hard for $k\geq 3$ Could anyone provide a reference for the result? By edge-chromatic number i mean the smallest number of colours assigned to the edges such that incident edges receive different colours.

  • $\begingroup$ What about tripartite graphs, do you know the answer for those? $\endgroup$ – domotorp Jun 29 '16 at 4:07
  • $\begingroup$ No, i'm assuming it's hard but i'd love to see the reduction if you have a reference? $\endgroup$ – Pavan Sangha Jul 4 '16 at 15:19
  • $\begingroup$ cstheory.stackexchange.com/questions/36114/… $\endgroup$ – domotorp Jul 4 '16 at 19:31
  • $\begingroup$ Sorry where in that post does it reference a paper proving hardness for 3-partite 3-uniform hypergraphs? $\endgroup$ – Pavan Sangha Oct 13 '16 at 15:49
  • $\begingroup$ I'm not sure I understand what you're asking. Did you want a link to this paper? doi:10.1016/0166-218X(91)90010-T $\endgroup$ – domotorp Oct 13 '16 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.