Golomb graph: Difference between revisions
m →References: cite repair; |
|||
(5 intermediate revisions by 5 users not shown) | |||
Line 1: | Line 1: | ||
{{short description|Undirected unit-distance graph requiring four colors}} |
|||
{{infobox graph |
{{infobox graph |
||
| name = Golomb graph |
| name = Golomb graph |
||
Line 6: | Line 7: | ||
| edges = 18 |
| edges = 18 |
||
| chromatic_number = 4 |
| chromatic_number = 4 |
||
| automorphisms = 6 |
|||
| properties = {{plainlist|1= |
| properties = {{plainlist|1= |
||
*[[Polyhedral graph|polyhedral]] |
*[[Polyhedral graph|polyhedral]] |
||
Line 37: | Line 39: | ||
| title = The fractional chromatic number of the plane |
| title = The fractional chromatic number of the plane |
||
| volume = 37 |
| volume = 37 |
||
| year = 2017 |
| year = 2017| s2cid = 4687673 |
||
}}</ref> |
|||
<ref name=pegg>{{citation|url=http://demonstrations.wolfram.com/MoserSpindlesGolombGraphsAndRoot33/|title=Moser Spindles, Golomb Graphs and Root 33|work=Wolfram Demonstrations Project|date=December 21, 2017|first=Ed |
<ref name=pegg>{{citation|url=http://demonstrations.wolfram.com/MoserSpindlesGolombGraphsAndRoot33/|title=Moser Spindles, Golomb Graphs and Root 33|work=Wolfram Demonstrations Project|date=December 21, 2017|first=Ed Jr.|last=Pegg|author-link=Ed Pegg Jr.}}</ref> |
||
<ref name=soifer>{{Citation |
<ref name=soifer>{{Citation |
||
|last=Soifer | first = Alexander | |
|last=Soifer | first = Alexander | author-link = Alexander Soifer |
||
|year=2008 |
|year=2008 |
||
|title=The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators |
|title=The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators |
||
Line 62: | Line 65: | ||
| title = All generalized Petersen graphs are unit-distance graphs |
| title = All generalized Petersen graphs are unit-distance graphs |
||
| volume = 49 |
| volume = 49 |
||
| year = 2012 |
| year = 2012| doi-access = free |
||
}}</ref> |
|||
}} |
}} |
Latest revision as of 22:02, 3 November 2023
Golomb graph | |
---|---|
![]() | |
Named after | Solomon W. Golomb |
Vertices | 10 |
Edges | 18 |
Automorphisms | 6 |
Chromatic number | 4 |
Properties | |
Table of graphs and parameters |
In graph theory, the Golomb graph is a polyhedral graph with 10 vertices and 18 edges. It is named after Solomon W. Golomb, who constructed it (with a non-planar embedding) as a unit distance graph that requires four colors in any graph coloring. Thus, like the simpler Moser spindle, it provides a lower bound for the Hadwiger–Nelson problem: coloring the points of the Euclidean plane so that each unit line segment has differently-colored endpoints requires at least four colors.[1]
Bauwesen
[edit]![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/fd/GolombGraphProperties.svg/220px-GolombGraphProperties.svg.png)
The method of construction of the Golomb graph as a unit distance graph, by drawing an outer regular polygon connected to an inner twisted polygon or star polygon, has also been used for unit distance representations of the Petersen graph and of generalized Petersen graphs.[2] As with the Moser spindle, the coordinates of the unit-distance embedding of the Golomb graph can be represented in the quadratic field .[3]
Fractional coloring
[edit]The fractional chromatic number of the Golomb graph is 10/3. The fact that this number is at least this large follows from the fact that the graph has 10 vertices, at most three of which can be in any independent set. The fact that the number is at most this large follows from the fact that one can find 10 three-vertex independent sets, such that each vertex is in exactly three of these sets. This fractional chromatic number is less than the number 7/2 for the Moser spindle and less than the fractional chromatic number of the unit distance graph of the plane, which is bounded between 3.6190 and 4.3599.[4]
References
[edit]- ^ Soifer, Alexander (2008), The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators, New York: Springer, p. 19, ISBN 978-0-387-74640-1
- ^ Žitnik, Arjana; Horvat, Boris; Pisanski, Tomaž (2012), "All generalized Petersen graphs are unit-distance graphs", Journal of the Korean Mathematical Society, 49 (3): 475–491, doi:10.4134/JKMS.2012.49.3.475, MR 2953031
- ^ Pegg, Ed Jr. (December 21, 2017), "Moser Spindles, Golomb Graphs and Root 33", Wolfram Demonstrations Project
- ^ Cranston, Daniel W.; Rabern, Landon (2017), "The fractional chromatic number of the plane", Combinatorica, 37 (5): 837–861, arXiv:1501.01647, doi:10.1007/s00493-016-3380-3, MR 3737371, S2CID 4687673