English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

A graph is word-representable if it can be represented in a certain way usingalternation of letters in words. Word-representable graphs generalise severalimportant and well-studied classes of graphs, and they can be characterised bysemi-transitive orientations. Recognising word-representability is anNP-complete problem, and the bottleneck of the theory of word-representablegraphs is convincing someone that a graph is non-word-representable, keeping inmind that references to (even publicly available and user-friendly) softwareare not always welcome. (Word-representability can be justified by providing asemi-transitive orientation as a certificate that can be checked in polynomialtime.)  In the literature, a variety of (usually ad hoc) proofs ofnon-word-representability for particular graphs, or families of graphs, appear,but for a randomly selected graph, one should expect looking at O(2^{#{edges}})orientations and justifying that none of them is semi-transitive.  In this paper, we develop methods for an automatic search of human-verifiableproofs of graph non-word-representability. As a proof-of-concept, we provide``short'' proofs of non-word-representability, generated automatically by ourpublicly available user-friendly software, of the Shrikhande graph on 16vertices and 48 edges (6 ``lines'' of proof) and the Clebsch graph on 16vertices and 40 edges (10 ``lines'' of proof). As a bi-product of our studies,we correct two mistakes published multiple times (two graphs out of the 25non-word-representable graphs on 7 vertices were actually word-representable,while two non-word-representable graphs on 7 vertices were missing).

Human-verifiable proofs in the theory of word-representable graphs