What does it mean? (Graph theory)

  • Thread starter ff4ever
  • Start date
  • #1
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
3,912
1,471
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
2
0
Okay. Now I understand. Thanks a lot !
 

Related Threads on What does it mean? (Graph theory)

  • Last Post
Replies
5
Views
3K
  • Last Post
Replies
4
Views
6K
  • Last Post
Replies
19
Views
4K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
1
Views
7K
Replies
2
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
5
Views
739
Top