2008/10/01 by Magnus Mar Halldorsson, Magnús M. Halldórsson, Sergey Kitaev +5 · 1 citation
Computer Science · Decision Sciences · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Fuzzy and Soft Set Theory #Graph Labeling and Dimension Problems #math.CO
paper · pdf · doi:10.48550/arxiv.0810.0310
12 pages, 3 figures
arxiv created 2008/10/01 · openalex publication_date 2008/10/01 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph G=(V,E) is representable 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. If W is k-uniform (each letter of W occurs exactly k times in it) then G is called k-representable. It was shown that a graph is representable if and only if it is k-representable for some k. Minimum k for which a representable graph G is k-representable is called its representation number. In this paper we give a characterization of representable graphs in terms of orientations. Namely, we show that a graph is representable if and only if it admits an orientation into a so-called semi-transitive digraph. This allows us to prove a number of results about representable graphs, not the least that 3-colorable graphs are representable. We also prove that the representation number of a graph on n nodes is at most n, from which one concludes that the recognition problem for representable graphs is in NP. This bound is tight up to a constant factor, as we present a graph whose representation number is n/2. We also answer several questions, in particular, on representability of the Petersen graph and local permutation representability.