On graphs with representation number 3

DOI10.25596/JALC-2013-097MaRDI QIDQ5507086zbMATH OpenFDO

Authors Sergey Kitaev

Publication date 16 December 2016

Full work available at URL https://arxiv.org/abs/1403.1616

zbMATH Keywords

circle graphcomparability graphcrown graphladder graphprismword-representable graph

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph theory (including graph drawing) in computer science (68R10)

Abstract: A graph $G=(V,E)$ is word-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)$ is an edge in $E$. A graph is word-representable if and only if it is $k$-word-representable for some $k$, that is, if there exists a word containing $k$ copies of each letter that represents the graph. Also, being $k$-word-representable implies being $(k+1)$-word-representable. The minimum $k$ such that a word-representable graph is $k$-word-representable, is called graph's representation number. Graphs with representation number 1 are complete graphs, while graphs with representation number 2 are circle graphs. The only fact known before this paper on the class of graphs with representation number 3, denoted by $mathcal{R}_3$, is that the Petersen graph and triangular prism belong to this class. In this paper, we show that any prism belongs to $mathcal{R}_3$, and that two particular operations of extending graphs preserve the property of being in $mathcal{R}_3$. Further, we show that $mathcal{R}_3$ is not included in a class of $c$-colorable graphs for a constant $c$. To this end, we extend three known results related to operations on graphs. We also show that ladder graphs used in the study of prisms are $2$-word-representable, and thus each ladder graph is a circle graph. Finally, we discuss $k$-word-representing comparability graphs via consideration of crown graphs, where we state some problems for further research.

Recommendations

• On the representation number of a crown graph
• Word-representability of triangulations of grid-covered cylinder graphs
• On 132-representable graphs
• On representable graphs
• Word-Representable Graphs: a Survey

Cited in

(12)

• On the representation number of a crown graph
• Graphs of gonality three
• Solving computational problems in the theory of word-representable graphs
• scientific article; zbMATH DE number 1465768 (Why is no real title available?)
• Word-Representable Graphs: a Survey
• Representing graphs via pattern avoiding words
• Minimum length word-representants of word-representable graphs
• Minimum length word-representants of graph products
• On semi-transitive orientability of circulant graphs
• An exact result for 3-graphs
• On word-representability of polyomino triangulations
• An \(S_ 3(3,5,21)\) using graphs

This page was built for publication: On graphs with representation number 3

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5507086)