Geodesic
A New Characterization of Unichord-Free Graphs
Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 4, pp. 765-771.

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: chordal graph, unichord-free graph, minimal separator 
@article{DMGT_2015_35_4_a12,
     author = {McKee, Terry A.},
     title = {A {New} {Characterization} of {Unichord-Free} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {765--771},
     publisher = {mathdoc},
     volume = {35},
     number = {4},
     year = {2015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a12/}
}
TY  - JOUR
AU  - McKee, Terry A.
TI  - A New Characterization of Unichord-Free Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2015
SP  - 765
EP  - 771
VL  - 35
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a12/
LA  - en
ID  - DMGT_2015_35_4_a12
ER  - 
%0 Journal Article
%A McKee, Terry A.
%T A New Characterization of Unichord-Free Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2015
%P 765-771
%V 35
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a12/
%G en
%F DMGT_2015_35_4_a12
McKee, Terry A. A New Characterization of Unichord-Free Graphs. Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 4, pp. 765-771. http://geodesic.mathdoc.fr/item/DMGT_2015_35_4_a12/

[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

[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

[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

[4] S. Klein and C.M.H. de Figueiredo, The NP-completeness of multi-partite cutset testing, Congr. Numer. 119 (1996) 217-222.

[5] T. Kloks and D. Kratsch, Listing all minimal separators of a graph, SIAM J. Comput. 27 (1998) 605-613. doi:10.1137/S009753979427087X

[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

[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

[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

[9] T.A. McKee, Independent separator graphs, Util. Math. 73 (2007) 217-224.

[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

[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

[12] Y. Shibata, On the tree representation of chordal graphs, J. Graph Theory 12 (1988) 421-428. doi:10.1002/jgt.3190120313

[13] R.E. Tarjan, Decomposition by clique separators, Discrete Math. 55 (1985) 221-232. doi:10.1016/0012-365X(85)90051-2

[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

[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