Geodesic
Forbidden pairs with a common graph generating almost the same sets
Shuya Chiba1 ; Jun Fujisawa2 ; Michitaka Furuya3 ; Hironobu Ikarashi4
1Kumamoto University
2Keio University
3Kitasato University
4Tokyo University of Science
The electronic journal of combinatorics, Tome 24 (2017) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Let $\mathcal{H}$ be a family of connected graphs. A graph $G$ is said to be $\mathcal{H}$-free if $G$ does not contain any members of $\mathcal{H}$ as an induced subgraph. Let $\mathcal{F}(\mathcal{H})$ be the family of connected $\mathcal{H}$-free graphs. In 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. Our main result is the following: Let $H_{1},H_{2},H_{3}$ be connected graphs of order at least three, and suppose that $H_{1}$ is twin-less. If 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. Furthermore, we refine a result in [Combin. Probab. Comput. 22 (2013) 733–748] concerning forbidden pairs.
DOI : 10.37236/6190
Classification : 05C60, 05C25, 05C40
Mots-clés : forbidden subgraph, star-free graph, vertex-transitive graph

Shuya Chiba  1   ; Jun Fujisawa  2   ; Michitaka Furuya  3   ; Hironobu Ikarashi  4

1 Kumamoto University
2 Keio University
3 Kitasato University
4 Tokyo University of Science 
@article{10_37236_6190,
     author = {Shuya Chiba and Jun Fujisawa and Michitaka Furuya and Hironobu Ikarashi},
     title = {Forbidden pairs with a common graph generating almost the same sets},
     journal = {The electronic journal of combinatorics},
     year = {2017},
     volume = {24},
     number = {2},
     doi = {10.37236/6190},
     zbl = {1361.05084},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/6190/}
}
TY  - JOUR
AU  - Shuya Chiba
AU  - Jun Fujisawa
AU  - Michitaka Furuya
AU  - Hironobu Ikarashi
TI  - Forbidden pairs with a common graph generating almost the same sets
JO  - The electronic journal of combinatorics
PY  - 2017
VL  - 24
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/6190/
DO  - 10.37236/6190
ID  - 10_37236_6190
ER  - 
%0 Journal Article
%A Shuya Chiba
%A Jun Fujisawa
%A Michitaka Furuya
%A Hironobu Ikarashi
%T Forbidden pairs with a common graph generating almost the same sets
%J The electronic journal of combinatorics
%D 2017
%V 24
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/6190/
%R 10.37236/6190
%F 10_37236_6190
Shuya Chiba; Jun Fujisawa; Michitaka Furuya; Hironobu Ikarashi. Forbidden pairs with a common graph generating almost the same sets. The electronic journal of combinatorics, Tome 24 (2017) no. 2. doi: 10.37236/6190

Cité par Sources :