Search

A graph G = ( V , E ) is a word-representable graph if there exists a word W over the alphabet V such that letters x and y alternate in W if and only if ( x , y ) ∈ E for each x ≠ y . In this paper we give an effective characterization of word-representable graphs in terms of orientations. Namely, we show that a graph is word-representable if and only if it admits a semi-transitive orientation defined in the paper. This allows us to prove a number of results about word-representable graphs, in particular showing that the recognition problem is in NP, and that word-representable graphs include all 3-colorable graphs. We also explore bounds on the size of the word representing the graph. The representation number of G is the minimum k such that G is a representable by a word, where each letter occurs k times; such a k exists for any word-representable graph. We show that the representation number of a word-representable graph on n vertices is at most 2 n , while there exist graphs for which it is n / 2 . [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we study the class of distance-hereditary comparability graphs, that is, those graphs which admit a transitive orientation and are completely decomposable with respect to the split decomposition. We provide a characterization based on a restricted number of forbidden subgraphs. We also provide further characterizations and one of them, based on the split decomposition, is used to devise a recognizing algorithm working in linear time. Finally, we show how to build distance-hereditary comparability graphs. [Copyright &y& Elsevier]