Bicolorable Graph
المؤلف:
Harary, F
المصدر:
Graph Theory. Reading, MA: Addison-Wesley, 1994.
الجزء والصفحة:
...
24-3-2022
2460
Bicolorable Graph
A bicolorable graph 
is a graph with chromatic number 
. A graph is bicolorable iff it has no odd graph cycles (König 1950, p. 170; Skiena 1990, p. 213; Harary 1994, p. 127). Bicolorable graphs are equivalent to bipartite graphs (Skiena 1990, p. 213). The numbers of bipartite graphs on 
, 2, ... nodes are 1, 2, 3, 7, 13, 35, 88, 303, ... (OEIS A033995). A graph can be tested for being bicolorable using BipartiteGraphQ[g], and one of its two bipartite sets of vertices can be found using FindIndependentVertexSet[g][[1]].
The following table lists some named bicolorable graphs.
graph  |
 |
| singleton graph |
1 |
| square graph |
4 |
| claw graph |
4 |
| utility graph |
6 |
| cubical graph |
8 |
| Herschel graph |
11 |
| Franklin graph |
12 |
| Heawood graph |
14 |
| tesseract graph |
16 |
| Möbius-Kantor graph |
16 |
| Hoffman graph |
16 |
| Pappus graph |
18 |
| Folkman graph |
20 |
| Desargues graph |
20 |
| truncated octahedral graph |
24 |
| Walther graph |
25 |
| Levi graph |
30 |
| Dyck graph |
32 |
| great rhombicuboctahedral graph |
48 |
| gray graph |
54 |
| Balaban 10-cage |
70 |
| Foster graph |
90 |
| great rhombicosidodecahedral graph |
120 |
| Tutte 12-cage |
126 |
REFERENCES
Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.
König, D. Theorie der endlichen und unendlichen Graphen. New York: Chelsea, 1950.
Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990.Sloane, N. J. A. Sequence A033995 in "The On-Line Encyclopedia of Integer Sequences."
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
