Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ Discussiones Mathema...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Discussiones Mathematicae Graph Theory
Article . 2024 . Peer-reviewed
Data sources: Crossref
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
image/svg+xml Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao Closed Access logo, derived from PLoS Open Access logo. This version with transparent background. http://commons.wikimedia.org/wiki/File:Closed_Access_logo_transparent.svg Jakob Voss, based on art designer at PLoS, modified by Wikipedia users Nina and Beao
zbMATH Open
Article . 2024
Data sources: zbMATH Open
https://dx.doi.org/10.48550/ar...
Article . 2022
License: CC BY
Data sources: Datacite
DBLP
Preprint . 2022
Data sources: DBLP
DBLP
Article . 2024
Data sources: DBLP
versions View all 8 versions
addClaim

Graph classes equivalent to 12-representable graphs

Authors: Asahi Takaoka;

Graph classes equivalent to 12-representable graphs

Abstract

Jones et al. (2015) introduced the notion of $u$-representable graphs, where $u$ is a word over $\{1, 2\}$ different from $22\cdots2$, as a generalization of word-representable graphs. Kitaev (2016) showed that if $u$ is of length at least 3, then every graph is $u$-representable. This indicates that there are only two nontrivial classes in the theory of $u$-representable graphs: 11-representable graphs, which correspond to word-representable graphs, and 12-representable graphs. This study deals with 12-representable graphs. Jones et al. (2015) provided a characterization of 12-representable trees in terms of forbidden induced subgraphs. Chen and Kitaev (2022) presented a forbidden induced subgraph characterization of a subclass of 12-representable grid graphs. This paper shows that a bipartite graph is 12-representable if and only if it is an interval containment bigraph. The equivalence gives us a forbidden induced subgraph characterization of 12-representable bipartite graphs since the list of minimal forbidden induced subgraphs is known for interval containment bigraphs. We then have a forbidden induced subgraph characterization for grid graphs, which solves an open problem of Chen and Kitaev (2022). The study also shows that a graph is 12-representable if and only if it is the complement of a simple-triangle graph. This equivalence indicates that a necessary condition for 12-representability presented by Jones et al. (2015) is also sufficient. Finally, we show from these equivalences that 12-representability can be determined in $O(n^2)$ time for bipartite graphs and in $O(n(\bar{m}+n))$ time for arbitrary graphs, where $n$ and $\bar{m}$ are the number of vertices and edges of the complement of the given graph.

12 pages, 6 figures, Corrected typos, Corrected Reference [22]

Related Organizations
Keywords

FOS: Computer and information sciences, Discrete Mathematics (cs.DM), simple-triangle graphs, Graph representations (geometric and intersection representations, etc.), vertex ordering characterization, 12-representable graphs, interval containment bigraphs, Graph theory (including graph drawing) in computer science, Graph algorithms (graph-theoretic aspects), QA1-939, forbidden induced subgraphs, Structural characterization of families of graphs, Mathematics, Computer Science - Discrete Mathematics, 05C62, 05C75

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    1
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
1
Average
Average
Average
Green
Published in a Diamond OA journal