{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:43:45Z","timestamp":1753893825711,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>Let $\\mathcal{H}$ be a family of connected graphs.\u00a0A graph $G$ is said to be $\\mathcal{H}$-free if $G$ does not contain any members of $\\mathcal{H}$ as an induced subgraph.\u00a0Let $\\mathcal{F}(\\mathcal{H})$ be the family of connected $\\mathcal{H}$-free graphs.\u00a0In this context, the members of $\\mathcal{H}$ are called forbidden subgraphs.In this paper, we focus on two pairs of forbidden subgraphs containing a common graph, and compare the classes of graphs satisfying each of the two forbidden subgraph conditions.\u00a0Our main result is the following:\u00a0Let $H_{1},H_{2},H_{3}$ be connected graphs of order at least three, and suppose that $H_{1}$ is twin-less.\u00a0If the symmetric difference of $\\mathcal{F}(\\{H_{1},H_{2}\\})$ and $\\mathcal{F}(\\{H_{1},H_{3}\\})$ is finite and the tuple $(H_{1};H_{2},H_{3})$ is non-trivial in a sense, then $H_{2}$ and $H_{3}$ are obtained from the same vertex-transitive graph by successively replacing a vertex with a clique and joining the neighbors of the original vertex and the clique.\u00a0Furthermore, we refine a result in [Combin. Probab. Comput. 22 (2013) 733\u2013748] concerning forbidden pairs.<\/jats:p>","DOI":"10.37236\/6190","type":"journal-article","created":{"date-parts":[[2020,1,10]],"date-time":"2020-01-10T15:58:20Z","timestamp":1578671900000},"source":"Crossref","is-referenced-by-count":0,"title":["Forbidden Pairs with a Common Graph Generating Almost the Same Sets"],"prefix":"10.37236","volume":"24","author":[{"given":"Shuya","family":"Chiba","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jun","family":"Fujisawa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michitaka","family":"Furuya","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hironobu","family":"Ikarashi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"23455","published-online":{"date-parts":[[2017,4,13]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v24i2p13\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v24i2p13\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,17]],"date-time":"2020-01-17T05:02:31Z","timestamp":1579237351000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v24i2p13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,13]]},"references-count":0,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2017,4,13]]}},"URL":"https:\/\/doi.org\/10.37236\/6190","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2017,4,13]]},"article-number":"P2.13"}}