What does it mean? (Graph theory)

  • Thread starter ff4ever
  • Start date
  • #1
ff4ever
2
0
Hi,

In the paper "A triangle-free circle graph with chromatic number 5" from A.A. Ageev, I don't understand what the author mean with the following definition:

captur10.png


Somebody can explain it to me? (I'm not mathematician).
Thanks !

Link to the whole paper:
http://www.sciencedirect.com/science/article/pii/0012365X95003492
 

Answers and Replies

  • #2
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
4,044
1,621
A graph is a set of spots ('vertices'), some of which are connected to each other by lines ('edges'). The arrangement of the spots and the shape of the connecting lines doesn't matter. All that matters is what spots are connected to each other.

A 'circle graph' is a particular type of graph whose meaning is explained here.

A set of vertices is 'independent' in a graph if, for every pair of vertices in the set, the graph has no edge connecting the two.

For a graph ##H##, we use ##V(H)## to refer to the set of vertices in the graph, and ##E(H)## to refer to the set of edges.

If ##x## and ##v## are vertices in a graph then ##xv## refers to an edge connecting ##x## to ##v##.

What the definition says is that a subset ##X## of vertices of a circle graph ##G## is defined to be parallel iff the graph formed from ##G## by adding a new vertex and adding edges joining the new vertex to every vertex in ##X## is also a circle graph.
 
  • #3
ff4ever
2
0
Okay. Now I understand. Thanks a lot !
 

Suggested for: What does it mean? (Graph theory)

  • Last Post
Replies
5
Views
572
  • Last Post
Replies
4
Views
408
  • Last Post
Replies
2
Views
202
  • Last Post
Replies
3
Views
611
  • Last Post
Replies
9
Views
940
Replies
29
Views
759
Replies
13
Views
440
Top