Content deleted Content added
Citation bot (talk | contribs) Added pages. | Use this bot. Report bugs. | Suggested by Abductive | Category:NP-complete problems | #UCB_Category 71/181 |
No edit summary |
||
Line 5:
In the mathematical field of [[graph theory]], a '''word-representable graph''' is a [[graph (discrete mathematics)|graph]] that can be characterized by a word (or sequence) whose entries alternate in a prescribed way. In particular, if the vertex set of the graph is ''V'', one should be able to choose a word ''w'' over the alphabet ''V'' such that letters ''a'' and ''b'' alternate in ''w'' if and only if the pair ''ab'' is an edge in the graph. (Letters ''a'' and ''b'' '''alternate''' in ''w'' if, after removing from ''w'' all letters but the copies of ''a'' and ''b'', one obtains a word ''abab''... or a word ''baba''....) For example, the [[cycle graph]] labeled by ''a'', ''b'', ''c'' and ''d'' in clock-wise direction is word-representable because it can be represented by ''abdacdbc'': the pairs ''ab'', ''bc'', ''cd'' and ''ad'' alternate, but the pairs ''ac'' and ''bd'' do not.
The word ''w'' is ''G''<nowiki/>'s ''word-representant'', and one says that that ''w'' ''represents'' ''G''. The smallest (by the number of
The definition of a word-representable graph works both in labelled and unlabelled cases since any labelling of a graph is equivalent to any other labelling. Also, the class of word-representable graphs is [[Hereditary property|hereditary]]. Word-representable graphs generalise several important classes of graphs such as [[circle graph]]s, [[Graph coloring|3-colorable graphs]] and [[comparability graph]]s. Various generalisations of the theory of word-representable graphs accommodate representation of ''any'' graph.
| |||