I'm trying to find a graph with those properties for my studies, but unfortunately I can't find such graph.
Does anyone know if there is that graph, or why is it impossible to exist?
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.Sign up to join this community
Suppose $G$ is a triangle-free star-cutset-free circle graph. I will show that $G$ contains no vertex with degree more than 2. Therefore, $G$ has at most $n$ edges.
Consider a circle representation $C$ of $G$. A set of chords is parallel if no two of them cross but there is a line crossing all the chords.
Property 1: $C$ has no 3 parallel chords.
Proof. Suppose $C$ has 3 parallel chords. Condider the vertex $v$ corresponding to the middle chord. Then, $N[v]$ is a cutset. This proves the property.
For the sake of contradiction, assume $G$ has a vertex $v$ of degree at least 3. Then, the chord corresponding to $v$ intersects 3 other chords. Since these 3 chords intersect one line, they are either parallel or two of them intersect. Due to Property 1, two of them intersect, which means their vertices form a triangle with $v$, which contradicts $G$ being triangle-free.
No, no such graph exists. To see why not, suppose we have a circle graph defined by a triangle-free set of chords. Let $n$ be the number of vertices of the circle graph (or the number of chords), and $m$ be the number of edges of the graph (crossings of two chords). Then an easy induction on the number of chords shows that the arrangement of the chords has exactly $m+n+1$ faces. However, there are at most $2n$ faces that touch the circle (fewer if some faces touch the circle more than once), so if $m>n$ then there must be at least two interior faces of the arrangement. Let $p$ be any shortest path in the dual graph of the arrangement (a squaregraph) from one such face to another, and let $c$ be any chord dual to an edge of $p$. Then the star-cutset induced by $c$ separates some of the chords bounding the face at one end of $p$ from some of the chords bounding the face at the other end.