Content deleted Content added
Nominated for deletion; see Wikipedia:Articles for deletion/Word-representable graph. (TW) |
Mark viking (talk | contribs) →top: Replacing incmprehensible tag with technical tag. The article is definitely comprehensible with some knowledge of graph theory and formal language theory, but asking for a more accessible intro is reasonable |
||
Line 5:
{{Multiple issues|
{{COI|date=February 2020}}
{{
}}
<!-- Note: The following pages were redirects to [[Word-representable_graph]] before draftification:
Line 11:
*[[Word-representable graphs]]
-->
In [[graph theory]], a graph ''G'' = (''V'',''E'') is '''word-representable''' iff there exists a word ''w'' over the alphabet ''V'' such that letters ''a'' and ''b'' alternate in ''w'' if and only if the edge ''ab'' is in ''E''. Letters ''a'' and ''b'' '''alternate''' in ''w'' if after removing from ''w'' all letters but the copies of ''a'' and ''b'' we either obtain a word ''abab''... or a word ''baba''.... In this context, we say that [[W|''w'']] is ''G''<nowiki/>'s '''word-representant''', or that ''w'' '''represents''' ''G''. For example, the [[cycle graph]] labeled by ''x'', ''y'', ''z'' and ''s'' in clock-wise direction is word-representable because it can be represented by ''szxsyxzy''. 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|circle graphs]], [[Graph coloring|3-colorable graphs]] and [[Comparability graph|comparability graphs]]. Various generalisations of the theory of word-representable graphs accommodate representation of ''any'' graph.
| |||