A New Characterization of Unichord-Free Graphs

Terry A. McKee

Discussiones Mathematicae Graph Theory (2015)

  • Volume: 35, Issue: 4, page 765-771
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

Terry A. McKee. "A New Characterization of Unichord-Free Graphs." Discussiones Mathematicae Graph Theory 35.4 (2015): 765-771. <http://eudml.org/doc/276023>.

@article{TerryA2015,
abstract = {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.},
author = {Terry A. McKee},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {chordal graph; unichord-free graph; minimal separator},
language = {eng},
number = {4},
pages = {765-771},
title = {A New Characterization of Unichord-Free Graphs},
url = {http://eudml.org/doc/276023},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Terry A. McKee
TI - A New Characterization of Unichord-Free Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 4
SP - 765
EP - 771
AB - 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.
LA - eng
KW - chordal graph; unichord-free graph; minimal separator
UR - http://eudml.org/doc/276023
ER -

References

top
  1. [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] Zbl1320.05120
  2. [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] Zbl0962.68138
  3. [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. [4] S. Klein and C.M.H. de Figueiredo, The NP-completeness of multi-partite cutset testing, Congr. Numer. 119 (1996) 217-222. Zbl0897.68070
  5. [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] Zbl0907.68136
  6. [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] Zbl1228.05157
  7. [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] Zbl1321.05089
  8. [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] Zbl1213.05150
  9. [9] T.A. McKee, Independent separator graphs, Util. Math. 73 (2007) 217-224. Zbl1140.05037
  10. [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] Zbl1276.05063
  11. [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] Zbl0945.05003
  12. [12] Y. Shibata, On the tree representation of chordal graphs, J. Graph Theory 12 (1988) 421-428. doi:10.1002/jgt.3190120313[Crossref] Zbl0654.05022
  13. [13] R.E. Tarjan, Decomposition by clique separators, Discrete Math. 55 (1985) 221-232. doi:10.1016/0012-365X(85)90051-2[Crossref] 
  14. [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] Zbl1186.05104
  15. [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] Zbl0454.68078

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.