Geodesic
Strongly Unichord-Free Graphs
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 2, pp. 365-374.

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

Several recent papers have investigated unichord-free graphs—the graphs in which no cycle has a unique chord. This paper proposes a concept of strongly unichord-free graph, defined by being unichord-free with no cycle of length 5 or more having exactly two chords. In spite of its overly simplistic look, this can be regarded as a natural strengthening of unichordfree graphs—not just the next step in a sequence of strengthenings—and it has a variety of characterizations. For instance, a 2-connected graph is strongly unichord-free if and only if it is complete bipartite or complete or “minimally 2-connected” (defined as being 2-connected such that deleting arbitrary edges always leaves non-2-connected subgraphs).
Keywords: unichord-free graph, strongly chordal graph 
@article{DMGT_2019_39_2_a5,
     author = {McKee, Terry A.},
     title = {Strongly {Unichord-Free} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {365--374},
     publisher = {mathdoc},
     volume = {39},
     number = {2},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a5/}
}
TY  - JOUR
AU  - McKee, Terry A.
TI  - Strongly Unichord-Free Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 365
EP  - 374
VL  - 39
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a5/
LA  - en
ID  - DMGT_2019_39_2_a5
ER  - 
%0 Journal Article
%A McKee, Terry A.
%T Strongly Unichord-Free Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 365-374
%V 39
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a5/
%G en
%F DMGT_2019_39_2_a5
McKee, Terry A. Strongly Unichord-Free Graphs. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 2, pp. 365-374. http://geodesic.mathdoc.fr/item/DMGT_2019_39_2_a5/

[1] 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

[2] G.A. Dirac, Minimally 2 -connected graphs, J. Reine Angew. Math. 228 (1967) 204–216. doi:10.1515/crll.1967.228.204

[3] B. Lévêque, F. Maffray and N. Trotignon, On graphs with no induced subdivision of K 4, J. Combin. Theory Ser. B 102 (2012) 924–947. doi:10.1016/j.jctb.2012.04.005

[4] R.C.S. Machado and C.M.H. de Figueiredo, Total chromatic number of unichordfree graphs, Discrete Appl. Math. 159 (2011) 1851–1864. doi:10.1016/j.dam.2011.03.024

[5] R.C.S. Machado, C.M.H. de Figueiredo and N. Trotignon, Edge-colouring and total-colouring chordless graphs, Discrete Math. 313 (2013) 1547–1552. doi:10.1016/j.disc.2013.03.020

[6] 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

[7] R.C.S. Machado, C.M.H. de Figueiredo and K. Vušković, Chromatic index of graphs with no cycle with a unique chord, Theoret. Comput. Sci. 411 (2010) 1221–1234. doi:10.1016/j.tcs.2009.12.018

[8] W. Mader, On vertices of degree n in minimally n-connected graphs and digraphs, in: Combinatorics, Paul Erdős is Eighty 2 (Bolyai Soc. Stud. Math. Budapest, 1996) 423–449.

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

[10] T.A. McKee, A new characterization of unichord-free graphs, Discuss. Math. Graph Theory 35 (2015) 765–771. doi:10.7151/dmgt.1831

[11] T.A. McKee, Double-crossed chords and distance-hereditary graphs, Australas. J. Combin. 65 (2016) 183–190.

[12] T.A. McKee and P. De Caria, Maxclique and unit disk characterizations of strongly chordal graphs, Discuss. Math. Graph Theory 34 (2014) 593–602. doi:10.7151/dmgt.1757

[13] M.D. Plummer, On minimal blocks, Trans. Amer. Math. Soc. 134 (1968) 85–94. doi:10.1090/S0002-9947-1968-0228369-8

[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