PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2016 | 36 | 3 | 723-741
Tytuł artykułu

Splitting Cubic Circle Graphs

Autorzy
Treść / Zawartość
Warianty tytułu
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
Wydawca
Rocznik
Tom
36
Numer
3
Strony
723-741
Opis fizyczny
Daty
wydano
2016-08-01
otrzymano
2015-04-15
poprawiono
2015-09-29
zaakceptowano
2015-11-02
online
2016-07-06
Twórcy
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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1894
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.