adplus-dvertising
frame-decoration

Question

In K-coloring of an undirected graph G=(V,E) is a function. c:V→{0,1,…,K−1} such that c(u)≠c(v) for every edge (u,v)∈E.

Which of the following is not correct?

a.

G is bipartite

b.

G is 2-colorable

c.

G has cycles of odd length

d.

G has no cycles of odd length

Answer: (c).G has cycles of odd length

Engage with the Community - Add Your Comment

Confused About the Answer? Ask for Details Here.

Know the Explanation? Add it Here.

Q. In K-coloring of an undirected graph G=(V,E) is a function. c:V→{0,1,…,K−1} such that c(u)≠c(v) for every edge (u,v)∈E. Which of the following is not correct?

Similar Questions

Discover Related MCQs

Q. Consider a singly linked list. What is the worst case time complexity of the best-known algorithm to delete the node a, pointer to this node is q, from the list?

Q. The second smallest of n elements can be found with ............... comparisons in the worst case.

Q. Consider the following statements related to AND-OR Search algorithm.

S1: A solution is a subtree that has a goal node at every leaf.
S2: OR nodes are analogous to the branching in a deterministic environment.
S3: AND nodes are analogous to the branching in a non-deterministic environment.

Which of the following is true referencing the above statements?

Q. The solution of the recurrence relation
T(m) = T(3m/4) + 1 is:

Q. Consider the array A=<4, 1, 3, 2, 16, 9, 10, 14, 8, 7>. After building heap from the array A, the depth of the heap and the right child of max-heap are .............. and .................. respectively. (Root is at level 0).

Q. A hash function h defined h(key)=key mod 7, with linear probing, is used to insert the keys 44, 45, 79, 55, 91, 18, 63 into a table indexed from 0 to 6. What will be the location of key 18?

Q. Which of the following algorithms solves the single-source shortest paths?

Q. A text is made up of the characters A, B, C, D, E each occurring with the probability 0.08, 0.40, 0.25, 0.15 and 0.12 respectively. The optimal coding technique will have the average length of:

Q. A binary search tree in which every non-leaf node has non-empty left and right subtrees is called a strictly binary tree. Such a tree with 19 leaves:

Q. Match the following with respect to algorithm paradigms :

List - I
(a) The 8-Queen’s problem
(b) Single-Source shortest paths
(c) STRASSEN’s Matrix multiplication
(d) Optimal binary search trees

List - II
(i) Dynamic programming
(ii) Divide and conquer
(iii) Greedy approach
(iv) Backtracking

Code:
(a) (b) (c) (d)

Q. The maximum number of comparisons needed to sort 9 items using radix sort is (assume each item is 5 digit octal number):

Q. A 5-ary tree is tree in which every internal node has exactly 5 children. The number of left nodes in such a tree with 8 internal nodes will be:

Q. Consider a Boolean function of ‘n’ variables. The order of an algorithm that determines whether the Boolean function produces a output 1 is:

Q. Consider an array representation of an n element binary heap where the elements are stored from index 1 to index n of the array. For the element stored at index i of the array (i< = n), the index of the parent is:

Q. The following numbers are inserted into an empty binary search tree in the given order:

10, 1, 3, 5, 15, 12, 16.

What is the height of the binary search tree?

Q. Let G be an undirected connected graph with distinct edge weight. Let Emax be the edge with maximum weight and Emin the edge with minimum weight. Which of the following statements is false?

Q. A list of n strings, each of length n, is sorted into lexicographic order using merge - sort algorithm. The worst case running time of this computation is:

Q. Postorder traversal of a given binary search tree T produces following sequence of keys:

3, 5, 7, 9, 4, 17, 16, 20, 18, 15, 14

Which one of the following sequences of keys can be the result of an in-order traversal of the tree T?

Q. The three aspects of Quantization, programmers generally concerned with are:

Q. The logic of pumping lemma is an example of ....................