Splitting cubic circle graphs

DOI10.7151/DMGT.1894MaRDI QIDQ726651zbMATH OpenOpenAlexFDO

Authors L. Traldi

Publication date 13 July 2016

Published in Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/1504.01143

zbMATH Keywords

circle graphregular graphsplit decomposition

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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, K_4 and K_{3,3} are the only 3-connected, 3-regular circle graphs.

Recommendations

• Splits of circuits
• Decomposition of 3-connected graphs
• Decomposition of 3-connected cubic graphs
• Splitter Theorems for Cubic Graphs
• Decomposing planar cubic graphs

Cites work

• Circle graph obstructions
• Circle graphs and monadic second-order logic
• Cycle decomposition by disjoint transpositions
• Decomposition of Directed Graphs
• Diamond-free circle graphs are Helly circle
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3606473 (Why is no real title available?)
• scientific article; zbMATH DE number 554160 (Why is no real title available?)
• scientific article; zbMATH DE number 3230035 (Why is no real title available?)
• scientific article; zbMATH DE number 3257167 (Why is no real title available?)
• scientific article; zbMATH DE number 3361902 (Why is no real title available?)
• Partial characterizations of circle graphs
• Practical and efficient circle graph recognition
• Practical and efficient split decomposition via graph-labelled trees
• Recognition of Circle Graphs
• Reconnaissance des graphes de cordes
• Reducing prime graphs and recognizing circle graphs

Cited in

(3)

• 2-nested matrices: towards understanding the structure of circle graphs
• scientific article; zbMATH DE number 1750097 (Why is no real title available?)
• Isotropic matroids. II: Circle graphs

This page was built for publication: Splitting cubic circle graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q726651)