Unichord-free graphs are defined as having no cycle with a unique chord. They have appeared in several papers recently and are also characterized by minimal separators always inducing edgeless subgraphs (in contrast to characterizing chordal graphs by minimal separators always inducing complete subgraphs). A new characterization of unichord-free graphs corresponds to a suitable reformulation of the standard simplicial vertex characterization of chordal graphs.
@article{bwmeta1.element.doi-10_7151_dmgt_1831,
author = {Terry A. McKee},
title = {A New Characterization of Unichord-Free Graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {35},
year = {2015},
pages = {765-771},
zbl = {1327.05291},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1831}
}
Terry A. McKee. A New Characterization of Unichord-Free Graphs. Discussiones Mathematicae Graph Theory, Tome 35 (2015) pp. 765-771. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1831/
[1] A. Berry, J.-P. Bordat and O. Cogis, Generating all the minimal separators of a graph, Internat. J. Found. Comput. Sci. 11 (2000) 397-403. doi:10.1142/S0129054100000211[Crossref] | Zbl 1320.05120
[2] A. Brandstädt, F.F. Dragan, V.B. Le and T. Szymczak, On stable cutsets in graphs, Discrete Appl. Math. 105 (2000) 39-50. doi:10.1016/S0166-218X(00)00197-9[Crossref] | Zbl 0962.68138
[3] A. Brandstädt, V.B. Le, and J.P. Spinrad, Graph Classes: A Survey (Society for Industrial and Applied Mathematics, Philadelphia, 1999). doi:10.1137/1.9780898719796[Crossref]
[4] S. Klein and C.M.H. de Figueiredo, The NP-completeness of multi-partite cutset testing, Congr. Numer. 119 (1996) 217-222. | Zbl 0897.68070
[5] T. Kloks and D. Kratsch, Listing all minimal separators of a graph, SIAM J. Comput. 27 (1998) 605-613. doi:10.1137/S009753979427087X[Crossref] | Zbl 0907.68136
[6] R.C.S. Machado and C.M.H. de Figueiredo, Total chromatic number of unichord- free graphs, Discrete Appl. Math. 159 (2011) 1851-1864. doi:10.1016/j.dam.2011.03.024[Crossref][WoS] | Zbl 1228.05157
[7] R.C.S. Machado, C.M.H. de Figueiredo and N. Trotignon, Complexity of colouring problems restricted to unichord-free and {square,unichord}-free graphs, Discrete Appl. Math. 164 (2014) 191-199. doi:10.1016/j.dam.2012.02.016[WoS][Crossref] | Zbl 1321.05089
[8] R.C.S. Machado, C.M.H. de Figueiredo and K. Vušković, Chromatic index of graphs with no cycle with unique chord, Theoret. Comput. Sci. 411 (2010) 1221-1234. doi:10.1016/j.tcs.2009.12.018[WoS][Crossref] | Zbl 1213.05150
[9] T.A. McKee, Independent separator graphs, Util. Math. 73 (2007) 217-224. | Zbl 1140.05037
[10] T.A. McKee, When all minimal vertex separators induce complete or edgeless sub- graphs, Discrete Math. Algorithms Appl. 5 (2013) #1350015. doi:10.1142/S1793830913500158[Crossref] | Zbl 1276.05063
[11] T.A. McKee and F.R. McMorris, Topics in Intersection Graph Theory (Society for Industrial and Applied Mathematics, Philadelphia, 1999). doi:10.1137/1.9780898719802[Crossref] | Zbl 0945.05003
[12] Y. Shibata, On the tree representation of chordal graphs, J. Graph Theory 12 (1988) 421-428. doi:10.1002/jgt.3190120313[Crossref] | Zbl 0654.05022
[13] R.E. Tarjan, Decomposition by clique separators, Discrete Math. 55 (1985) 221-232. doi:10.1016/0012-365X(85)90051-2[Crossref]
[14] N. Trotignon and K. Vušković, A structure theorem for graphs with no cycle with a unique chord and its consequences, J. Graph Theory 63 (2010) 31-67. doi:10.1002/jgt.20405[Crossref] | Zbl 1186.05104
[15] S.H. Whitesides, An algorithm for finding clique cut-sets, Inform. Process. Lett. 12 (1981) 31-32. doi:10.1016/0020-0190(81)90072-7 [Crossref] | Zbl 0454.68078