Representation Number of Word-Representable Graphs

Abstract

The thesis aims to further the study of the representation number of word-representable graphs and the permutation-representation number (prn) of comparability graphs. Focusing on the (𝑛4)-conjecture of Glen et al. on the representation number of bipartite graphs, the thesis proves that the conjecture is valid for all bipartite graphs, leaving the bipartite graphs with partite sets of even and equal size. For the bipartite graphs, the thesis provides a better upper bound for the prn. Towards contributing to the classes of graphs of representation number three and of prn three, the thesis completely characterizes and classifies melon graphs and their line graphs, and certain special classes of bipartite graphs, viz., extended crown graphs and stacked book graphs, with respect to their representation number and prn. Furthermore, utilizing the tool of semi-transitive orientations, the thesis settles one of the open problems on line graphs and shows that the line graphs of non-word-representable graphs are not always non-word-representable. The thesis also studies the relationship between the representation number defined via a semi-transitive orientation of a word-representable graph and the dimension of the poset induced by the semi-transitive orientation. In establishing the aforementioned results, the thesis constructs word-representants extensively in an efficient manner.