Graphs whose indecomposability graph is 2-covered

Abstract

Given a graph $G=(V,E)$, a subset $X$ of $V$ is an interval of $G$ provided that for any $a,b\in X$ and $x\in V\setminus X$, $\{a,x\}\in E$ if and only if $\{b,x\}\in E$. For example, $\varnothing$, $\{x\}(x\in V)$ and $V$ are intervals of $G$, called trivial intervals. A graph whose intervals are trivial is indecomposable; otherwise, it is decomposable. According to Ille, the indecomposability graph of an undirected indecomposable graph $G$ is the graph $\mathbb{I}(G)$ whose vertices are those of $G$ and edges are the unordered pairs of distinct vertices $\{x,y\}$ such that the induced subgraph $G[V\setminus \{x,y\}]$ is indecomposable. We characterize the indecomposable graphs $G$ whose $\mathbb{I}(G)$ admits a vertex cover of size 2.

arXiv comment31 pages, 5 figures