Return to Answer

This problem was proved to be NP-complete in https://link.springer.com/article/10.1007/BF00340774, but a mistake was discovered, and later corrected, for a simple proof and brief history, see https://link.springer.com/article/10.1007%2FBF01108825.

I've asked the same question myself earlier this year from some people working in the field, the above links were given to me by Piotr Micek. Some papers to read are also given in https://arxiv.org/pdf/1908.08250.pdf on page 2, before Theorem 1. Also see https://link.springer.com/article/10.1007/BF00400288.

This problem was proved to be NP-complete in

• J. Nešetřil, V. Rödl, Complexity of diagrams, Order 3 (1987) 321–330, https://doi.org/10.1007/BF00340774,

but a mistake was discovered, and later corrected, for a simple proof and brief history, see

• G. Brightwell, On the complexity of diagram testing, Order 10 (1993) 297–303, https://doi.org/10.1007/BF01108825.

I've asked the same question myself earlier this year from some people working in the field, the above links were given to me by Piotr Micek. Some papers to read are also given in

• Janos Pach, Istvan Tomon, Coloring Hasse diagrams and disjointness graphs of curves, https://arxiv.org/abs/1908.08250v1

on page 2, before Theorem 1. Also see

• B. Bollobás, G. Brightwell & J. Nešetřil, Random graphs and covering graphs of posets, Order 3 (1986) 245–255, https://doi.org/10.1007/BF00400288.

This problem was proved to be NP-complete in https://link.springer.com/article/10.1007/BF00340774, but a mistake was discovered and corrected in https://link.springer.com/article/10.1007%2FBF01108825.

I've asked the same question myself earlier this year from some people working in the field, the above links were given to me by Piotr Micek. Some papers to read are also given in https://arxiv.org/pdf/1908.08250.pdf on page 2, before Theorem 1. Also see https://link.springer.com/article/10.1007/BF00400288.

This problem was proved to be NP-complete in https://link.springer.com/article/10.1007/BF00340774, but a mistake was discovered, and later corrected, for a simple proof and brief history, see https://link.springer.com/article/10.1007%2FBF01108825.

I've asked the same question myself earlier this year from some people working in the field, the above links were given to me by Piotr Micek. Some papers to read are also given in https://arxiv.org/pdf/1908.08250.pdf on page 2, before Theorem 1. Also see https://link.springer.com/article/10.1007/BF00400288.

I've asked the same question myself earlier this year from some people working in the field. There's no nice characterization, but some papers to read are given in https://arxiv.org/pdf/1908.08250.pdf on page 2, before Theorem 1. Also see https://link.springer.com/article/10.1007/BF00400288.

This problem was proved to be NP-complete in https://link.springer.com/article/10.1007/BF00340774, but a mistake was discovered and corrected in https://link.springer.com/article/10.1007%2FBF01108825.

I've asked the same question myself earlier this year from some people working in the field, the above links were given to me by Piotr Micek. Some papers to read are also given in https://arxiv.org/pdf/1908.08250.pdf on page 2, before Theorem 1. Also see https://link.springer.com/article/10.1007/BF00400288.