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?
$\begingroup$
$\endgroup$
4
-
3$\begingroup$ Can you explain your terminology? What is "star-cutset-free" and what is "circle graph"? $\endgroup$– Yuval FilmusJun 27, 2013 at 3:16
-
1$\begingroup$ Sure. =) A circle graph is a graph (undirected) whose vertices can be associated with chords in a circle such that two vertices are adjacent iff the corresponding chords cross each other. Here is an image as example (from Wikipedia): en.wikipedia.org/wiki/File:Circle_graph.svg And we can say a graph has a star-cutset when you have a vertex v such that removing v and its neighbours (N[v]) from the graph turns it disconnected. $\endgroup$– Rafael Oliveira LopesJun 27, 2013 at 3:45
-
1$\begingroup$ ISGCI has definitions of triangle-free and circle graph. A star-cutset is a subset $S$ of vertices that separates the graph, such that one vertex in $S$ is adjacent to every other vertex in $S$. $\endgroup$– JeffεJun 27, 2013 at 3:45
-
$\begingroup$ This paper may be relevant. $\endgroup$– JeffεJun 27, 2013 at 3:49
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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.
-
$\begingroup$ I don't think propety 1 is true. Consider chords forming the sides of a regular $n$-gon, with the circle slightly bigger so that it contains the $n$-gon but does not contain any other crossings of those sides. $\endgroup$ Jun 27, 2013 at 4:37
-
$\begingroup$ Ok, as corrected I think this works, and is simpler than my proof. $\endgroup$ Jun 27, 2013 at 5:03
$\begingroup$
$\endgroup$
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.
answered Jun 27, 2013 at 4:26