Splitting Cubic Circle Graphs

Lorenzo Traldi

Discussiones Mathematicae Graph Theory (2016)

  • Volume: 36, Issue: 3, page 723-741
  • ISSN: 2083-5892

Abstract

top
We show that every 3-regular circle graph has at least two pairs of twin vertices; consequently no such graph is prime with respect to the split decomposition. We also deduce that up to isomorphism, K4 and K3,3 are the only 3-connected, 3-regular circle graphs.

How to cite

top

Lorenzo Traldi. "Splitting Cubic Circle Graphs." Discussiones Mathematicae Graph Theory 36.3 (2016): 723-741. <http://eudml.org/doc/285467>.

@article{LorenzoTraldi2016,
abstract = {We show that every 3-regular circle graph has at least two pairs of twin vertices; consequently no such graph is prime with respect to the split decomposition. We also deduce that up to isomorphism, K4 and K3,3 are the only 3-connected, 3-regular circle graphs.},
author = {Lorenzo Traldi},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {circle graph; split decomposition; regular graph},
language = {eng},
number = {3},
pages = {723-741},
title = {Splitting Cubic Circle Graphs},
url = {http://eudml.org/doc/285467},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Lorenzo Traldi
TI - Splitting Cubic Circle Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 3
SP - 723
EP - 741
AB - We show that every 3-regular circle graph has at least two pairs of twin vertices; consequently no such graph is prime with respect to the split decomposition. We also deduce that up to isomorphism, K4 and K3,3 are the only 3-connected, 3-regular circle graphs.
LA - eng
KW - circle graph; split decomposition; regular graph
UR - http://eudml.org/doc/285467
ER -

References

top
  1. [1] F. Bonomo, G. Durán, L.N. Grippo and M.D. Safe, Partial characterizations of circle graphs, Discrete Appl. Math. 159 (2011) 1699-1706. doi:10.1016/j.dam.2010.06.020[Crossref][WoS] Zbl1228.05243
  2. [2] A. Bouchet, Caractérisation des symboles croisés de genre nul , C.R. Acad. Sci. Paris Śer. A-B 274 (1972) A724-A727. Zbl0228.05104
  3. [3] A. Bouchet, Reducing prime graphs and recognizing circle graphs, Combinatorica 7 (1987) 243-254. doi:10.1007/BF02579301[Crossref] Zbl0666.05037
  4. [4] A. Bouchet, Circle graph obstructions, J. Combin. Theory Ser. B 60 (1994) 107-144. doi:10.1006/jctb.1994.1008[Crossref] Zbl0793.05116
  5. [5] H.R. Brahana, Systems of circuits on two-dimensional manifolds, Ann. of Math. 23 (1921) 144-168. doi:10.2307/1968030[Crossref] Zbl48.0661.02
  6. [6] M. Cohn and A. Lempel, Cycle decomposition by disjoint transpositions, J. Combin. Theory Ser. A 13 (1972) 83-89. doi:10.1016/0097-3165(72)90010-6[Crossref] Zbl0314.05005
  7. [7] B. Courcelle, Circle graphs and monadic second-order logic, J. Appl. Log. 6 (2008) 416-442. doi:10.1016/j.jal.2007.05.001[Crossref] Zbl1149.03011
  8. [8] W.H. Cunningham, Decomposition of directed graphs, SIAM J. Alg. Disc. Meth. 3 (1982) 214-228. doi:10.1137/0603021[Crossref] Zbl0497.05031
  9. [9] J. Daligault, D. Gonçalves and M. Rao, Diamond-free circle graphs are Helly circle, Discrete Math. 310 (2010) 845-849. doi:10.1016/j.disc.2009.09.022[WoS][Crossref] Zbl1222.05033
  10. [10] S. Even and A. Itai, Queues, stacks, and graphs, in: Theory of Machines and Computations, Proc. Internat. Sympos., Technion, Haifa, 1971, Z. Kohavi and A. Paz (Ed(s)), (Academic Press, New York, 1971) 71-86. doi:10.1016/b978-0-12-417750-5.50011-7[Crossref] 
  11. [11] L. Ghier, Double occurrence words with the same alternance graph, Ars Combin. 36 (1993) 57-64. Zbl0793.05124
  12. [12] E. Gioan, C. Paul, M. Tedder and D. Corneil, Practical and efficient circle graph recognition, Algorithmica 69 (2014) 759-788. doi:10.1007/s00453-013-9745-8[WoS][Crossref] Zbl1303.05190
  13. [13] E. Gioan, C. Paul, M. Tedder and D. Corneil, Practical and efficient split decompo- sition via graph-labelled trees, Algorithmica 69 (2014) 789-843. doi:10.1007/s00453-013-9752-9[WoS][Crossref] Zbl1303.05191
  14. [14] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Academic Press, New York, 1980). Zbl0541.05054
  15. [15] A. Kotzig, Eulerian lines in finite 4-valent graphs and their transformations, in: Theory of Graphs, Proc. Colloq., Tihany, 1966, P. Erdős and G. Katona (Ed(s)), (Academic Press, New York, 1968) 219-230. 
  16. [16] W. Naji, Reconnaissance des graphes de cordes, Discrete Math. 54 (1985) 329-337. doi:10.1016/0012-365X(85)90117-7[Crossref] Zbl0567.05033
  17. [17] R.C. Read and P. Rosenstiehl, On the Gauss crossing problem, in: Combina- torics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. II, Colloq. Math. Soc. János Bolyai, 18, A. Hajnal and V.T. Śos (Ed(s)), (North-Holland Publishing Co., Amsterdam-New York, 1978) 843-876. 
  18. [18] J. Spinrad, Recognition of circle graphs, J. Algorithms 16 (1994) 264-282. doi:10.1006/jagm.1994.1012[Crossref] Zbl0797.68130
  19. [19] B. Zelinka, The graph of the system of chords of a given circle, Mat.-Fyz. Časopis Sloven. Akad. Vied 15 (1965) 273-279. Zbl0142.41601

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.