Human-verifiable proofs in the theory of word-representable graphs
From MaRDI portal
Publication:6129083
DOI10.1051/ITA/2024004arXiv2110.05405OpenAlexW4393194694MaRDI QIDQ6129083FDOQ6129083
Publication date: 16 April 2024
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Abstract: A graph is word-representable if it can be represented in a certain way using alternation of letters in words. Word-representable graphs generalise several important and well-studied classes of graphs, and they can be characterised by semi-transitive orientations. Recognising word-representability is an NP-complete problem, and the bottleneck of the theory of word-representable graphs is convincing someone that a graph is non-word-representable, keeping in mind that references to (even publicly available and user-friendly) software are not always welcome. (Word-representability can be justified by providing a semi-transitive orientation as a certificate that can be checked in polynomial time.) In the literature, a variety of (usually ad hoc) proofs of non-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-verifiable proofs of graph non-word-representability. As a proof-of-concept, we provide ``short proofs of non-word-representability, generated automatically by our publicly available user-friendly software, of the Shrikhande graph on 16 vertices and 48 edges (6 ``lines of proof) and the Clebsch graph on 16 vertices 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 25 non-word-representable graphs on 7 vertices were actually word-representable, while two non-word-representable graphs on 7 vertices were missing).
Full work available at URL: https://arxiv.org/abs/2110.05405
semi-transitive orientationShrikhande graphClebsch graphword-representable graphautomated proofnon-word-representability
Cited In (2)
This page was built for publication: Human-verifiable proofs in the theory of word-representable graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6129083)
