Spatial graphs and their chromatic number

  • Thread starter jk22
  • Start date
  • #1
648
20

Main Question or Discussion Point

Suppose a generalization of planar graph is considered into 3D space :

a graph is said "spatial" if it can be constructed in Euclidean 3D space in such a way that no edge intersects a face.

The questions are the following :

-as for plane graphs their chromatic number is 4, can we show that the chromatic number for spatial graphs is 5 since K5 is spatial but not K6. (Kn is the complete n-vertices graph)

-If we consider a further generalization, can it be shown that Kn is "constructible" in a n-2 dimensional space such that no edge intersects any n-1-hyperface, but not K(n+1) ?
 
Last edited:

Answers and Replies

  • #2
160
21
What exactly do you mean by a "face"?

Consider, for example, a 4-cycle where the vertices do not lie in a plane. What does it mean for an edge to intersect that face?
 
  • #3
chiro
Science Advisor
4,790
131
Is a face just the equivalent of a subset of the surface formed in n-dimensions?
 
  • #4
648
20
For the 4-cycle, it's any surface whose boundary is that cycle.
The edges involved in defining the boundary can of course not intersect the surface, it would have been edges from other vertices.

I think I can add that : every cycle which has no sub-cycle spans such a surface which is called a face.
 
Last edited:
  • #5
160
21
For the 4-cycle, it's any surface whose boundary is that cycle.
The edges involved in defining the boundary can of course not intersect the surface, it would have been edges from other vertices.

I think I can add that : every cycle which has no sub-cycle spans such a surface which is called a face.
OK, in that case, please explain why you think K6 can't be embedded in 3-space in this way.
 
  • #6
648
20
Simply because else you should have an edge that interesect one of the faces :

It simple to construct K5 in that way : take a tetrahedron and put a vertice in the center of it, then link to every vertex of the tetrahedron.

Note now that the interior of the tetrahedron is divided by the faces into 4 smaller tetrahedron.

If you try to build K6 either you put your vertex in one of these smaller tetrahedron, which makes the opposite vertex inaccessible (since a face cannot intersect with an edge), if you put your 6th vertice exterior to the bigger tetrahedron, then the inner 5th point can't be reached.
 
  • #7
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
3,750
99
What is your precise definition of a face if your graph isn't planar to begin with?
 
  • #8
160
21
Simply because else you should have an edge that interesect one of the faces :

It simple to construct K5 in that way : take a tetrahedron and put a vertice in the center of it, then link to every vertex of the tetrahedron.

Note now that the interior of the tetrahedron is divided by the faces into 4 smaller tetrahedron.

If you try to build K6 either you put your vertex in one of these smaller tetrahedron, which makes the opposite vertex inaccessible (since a face cannot intersect with an edge), if you put your 6th vertice exterior to the bigger tetrahedron, then the inner 5th point can't be reached.
OK, so you have discovered a way to construct K6 that does not meet the requirements. But you have not proved that there is no way to construct K6 that meets the requirements.

EDIT: I should explain what problem you will encounter. If you try to formalize this argument into a proof, there will come a time when you have to say that if you take 4 vertices, connect them with edges, and then for every cycle, put a surface whose boundary is that cycle, then the resulting object has an inside and an outside. That is not clear to me.

In fact, I don't believe it is true.
 
Last edited:
  • #9
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
3,750
99
OK, so you have discovered a way to construct K6 that does not meet the requirements. But you have not proved that there is no way to construct K6 that meets the requirements.

EDIT: I should explain what problem you will encounter. If you try to formalize this argument into a proof, there will come a time when you have to say that if you take 4 vertices, connect them with edges, and then for every cycle, put a surface whose boundary is that cycle, then the resulting object has an inside and an outside. That is not clear to me.

In fact, I don't believe it is true.
There's only four vertices, if it isn't true you should be able to construct a counterexample :tongue:. The inside is the convex hull of those vertices - they form a tetrahedron (unless they're coplanar).
 
  • #10
160
21
Only if the surfaces are flat.

If two of the surfaces are cross-caps then you have a Klein bottle, and there is no longer an inside or outside.

The real question is whether this difficulty can be dismissed by insisting that the surfaces be non-self-intersecting.
 
  • #11
648
20
I don't see really good in space what you mean, but Klein bottle has no boundary, however the cycle has to be the boundary of the surface.

If we take non minimal surfaces they shall not intersect edges, i think it's a sufficient condition in order to see topologically that one vertex in K5 is "locked in" ?

I don't think to add the condition the surfaces cannot intersect another surface is necessary if you ask they already don't intersect with edges, in order to see that K6 is not makeable.

But one thing is sure, I don't have the skills to formalize that. Already the definition of a spatial graph is not clear (maybe you have litterature advice on this)
 
Last edited:
  • #12
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
3,750
99
I'm still not sure what the definition of a face is supposed to be if you have a cycle of more than three vertices which are not coplanar.
 
  • #13
648
20
Mathematically I supposed this can be any smooth surface which has the edges as boundary (the edges can be curves), but there I'm maybe missing some points.

Physically one can imagine a soap film hanging at the edges, hence a minimal surface.

I think the problem arise because we are used to see faces as plane, but we could imagine any smooth deformation of them, as long as they don't intersect other edges.
 

Related Threads on Spatial graphs and their chromatic number

  • Last Post
Replies
3
Views
5K
Replies
3
Views
1K
  • Last Post
Replies
5
Views
627
Replies
1
Views
839
Replies
11
Views
468
  • Last Post
Replies
13
Views
3K
  • Last Post
Replies
10
Views
4K
Replies
6
Views
1K
Top