Forbidden induced subgraph characterization of circle graphs within split graphs

DOI10.1016/J.DAM.2020.12.021MaRDI QIDQ2091783zbMATH OpenOpenAlexFDO

Authors Guillermo Durán, Nina Pardal, Martín D. Safe, Flavia Bonomo

Publication date 2 November 2022

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

circle graphsforbidden induced subgraphssplit graphsstructural characterization

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: A graph is circle if its vertices are in correspondence with a family of chords in a circle in such a way that every two distinct vertices are adjacent if and only if the corresponding chords have nonempty intersection. Even though there are diverse characterizations of circle graphs, a structural characterization by minimal forbidden induced subgraphs for the entire class of circle graphs is not known, not even restricted to split graphs (which are the graphs whose vertex set can be partitioned into a clique and a stable set). In this work, we give a characterization by minimal forbidden induced subgraphs of circle graphs, restricted to split graphs.

Recommendations

• Partial characterizations of circle graphs
• Publication:4724662
• Partial Characterizations of Circular-Arc Graphs
• Partial characterizations of circular-arc graphs
• Circle graph obstructions under pivoting

Cites work

• A structure theorem for the consecutive 1's property
• Algorithmic graph theory and perfect graphs
• Bipartite graphs that are not circle graphs
• Circle graph obstructions
• Circle graph obstructions under pivoting
• Diamond-free circle graphs are Helly circle
• scientific article; zbMATH DE number 3420624 (Why is no real title available?)
• Partial characterizations of circle graphs
• Permutation Graphs and Transitive Graphs
• Practical and efficient circle graph recognition
• Reconnaissance des graphes de cordes
• Reducing prime graphs and recognizing circle graphs
• Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
• Transitiv orientierbare Graphen

Cited in

(6)

• 2-nested matrices: towards understanding the structure of circle graphs
• Forbidden induced subgraphs of double-split graphs
• scientific article; zbMATH DE number 3898942 (Why is no real title available?)
• Partial characterizations of circle graphs
• Exactly hittable interval graphs
• Characterization of word-representable split graphs with an independent set of fixed size

This page was built for publication: Forbidden induced subgraph characterization of circle graphs within split graphs

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