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.
@article{bwmeta1.element.doi-10_7151_dmgt_1894,
author = {Lorenzo Traldi},
title = {Splitting Cubic Circle Graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {36},
year = {2016},
pages = {723-741},
zbl = {1339.05327},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1894}
}
Lorenzo Traldi. Splitting Cubic Circle Graphs. Discussiones Mathematicae Graph Theory, Tome 36 (2016) pp. 723-741. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1894/
[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] | Zbl 1228.05243
[2] A. Bouchet, Caractérisation des symboles croisés de genre nul , C.R. Acad. Sci. Paris Śer. A-B 274 (1972) A724-A727. | Zbl 0228.05104
[3] A. Bouchet, Reducing prime graphs and recognizing circle graphs, Combinatorica 7 (1987) 243-254. doi:10.1007/BF02579301[Crossref] | Zbl 0666.05037
[4] A. Bouchet, Circle graph obstructions, J. Combin. Theory Ser. B 60 (1994) 107-144. doi:10.1006/jctb.1994.1008[Crossref] | Zbl 0793.05116
[5] H.R. Brahana, Systems of circuits on two-dimensional manifolds, Ann. of Math. 23 (1921) 144-168. doi:10.2307/1968030[Crossref] | Zbl 48.0661.02
[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] | Zbl 0314.05005
[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] | Zbl 1149.03011
[8] W.H. Cunningham, Decomposition of directed graphs, SIAM J. Alg. Disc. Meth. 3 (1982) 214-228. doi:10.1137/0603021[Crossref] | Zbl 0497.05031
[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] | Zbl 1222.05033
[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] L. Ghier, Double occurrence words with the same alternance graph, Ars Combin. 36 (1993) 57-64. | Zbl 0793.05124
[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] | Zbl 1303.05190
[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] | Zbl 1303.05191
[14] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Academic Press, New York, 1980). | Zbl 0541.05054
[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] W. Naji, Reconnaissance des graphes de cordes, Discrete Math. 54 (1985) 329-337. doi:10.1016/0012-365X(85)90117-7[Crossref] | Zbl 0567.05033
[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] J. Spinrad, Recognition of circle graphs, J. Algorithms 16 (1994) 264-282. doi:10.1006/jagm.1994.1012[Crossref] | Zbl 0797.68130
[19] B. Zelinka, The graph of the system of chords of a given circle, Mat.-Fyz. Časopis Sloven. Akad. Vied 15 (1965) 273-279. | Zbl 0142.41601