Monday, March 23, 2015

013-2004

MO640 - Multiple-choice question

Considering the class of interval graphs, which alternative is correct:

  1. No polynomial-time algorithm is known for deciding whether a given graph is an interval graph.
  2. Every induced subgraph of an interval graph is itself an interval graph.
  3. If an induced subgraph of a graph G is an interval graph, then G is also an interval graph.
  4. The graph C4 (cycle with 4 vertices) belongs to this class.
  5. None of the abova
Original idea by: Marília Felippe Chiozo
Posted by at
Labels:

2 comments:

  1. UnknownApril 17, 2015 at 1:02 PM

    What do you mean in option 3 with "the original graph"? Maybe I didn't understand this right, but for me this option is tautological.

    ReplyDelete

Subscribe to: Post Comments (Atom)