9
$\begingroup$

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?

$\endgroup$
4
  • 3
    $\begingroup$ Can you explain your terminology? What is "star-cutset-free" and what is "circle graph"? $\endgroup$ Jun 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$ Jun 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

2 Answers 2

12
$\begingroup$

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.

$\endgroup$
2
  • $\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
9
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.