Splitting Cubic Circle Graphs

• Autorzy: Lorenzo Traldi
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

circle graph; split decomposition; regular graph

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2016
• Tom: 36
• Numer: 3
• Strony: 723-741

Daty

wydano

2016-08-01

otrzymano

2015-04-15

poprawiono

2015-09-29

zaakceptowano

2015-11-02

online

2016-07-06

Twórcy

autor

Lorenzo Traldi

• Lafayette College Easton, Pennsylvania 18042

Bibliografia

• [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]
• [2] A. Bouchet, Caractérisation des symboles croisés de genre nul , C.R. Acad. Sci. Paris Śer. A-B 274 (1972) A724-A727.
• [3] A. Bouchet, Reducing prime graphs and recognizing circle graphs, Combinatorica 7 (1987) 243-254. doi:10.1007/BF02579301[Crossref]
• [4] A. Bouchet, Circle graph obstructions, J. Combin. Theory Ser. B 60 (1994) 107-144. doi:10.1006/jctb.1994.1008[Crossref]
• [5] H.R. Brahana, Systems of circuits on two-dimensional manifolds, Ann. of Math. 23 (1921) 144-168. doi:10.2307/1968030[Crossref]
• [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]
• [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]
• [8] W.H. Cunningham, Decomposition of directed graphs, SIAM J. Alg. Disc. Meth. 3 (1982) 214-228. doi:10.1137/0603021[Crossref]
• [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]
• [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.
• [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]
• [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]
• [14] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Academic Press, New York, 1980).
• [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]
• [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]
• [19] B. Zelinka, The graph of the system of chords of a given circle, Mat.-Fyz. Časopis Sloven. Akad. Vied 15 (1965) 273-279.

Identyfikatory

DOI

10.7151/dmgt.1894