𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Maximum genus and chromatic number of graphs

✍ Scribed by Yuanqiu Huang

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
157 KB
Volume
271
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Let T be a spanning tree of a connected graph G. Denote by (G; T ) the number of components in G\E(T ) with odd number of edges. The value minT (G; T ) is known as the Betti deΓΏciency of G, denoted by (G), where the minimum is taken over all spanning trees T of G. It is known (N.H. Xuong, J. Combin. Theory 26 (1979) 217-225) that the maximum genus of a graph is mainly determined by its Betti deΓΏciency (G). Let G be a k-edge-connected graph (k 6 3) whose complementary graph has the chromatic number m. In this paper we prove that the Betti deΓΏciency (G) is bounded by a function f k (m) on m, and the bound is the best possible. Thus by Xuong's maximum genus theorem we obtain some new results on the lower bounds of the maximum genus of graphs.

πŸ“œ SIMILAR VOLUMES

The maximum interval number of graphs wi
The maximum interval number of graphs with given genus
✍ Edward R. Scheinerman πŸ“‚ Article πŸ“… 1987 πŸ› John Wiley and Sons 🌐 English βš– 202 KB πŸ‘ 1 views

The interval number of a graph G, denoted i(G), is the least positive integer t such that G is the intersection graph of sets, each of which is the union of t compact real intervals. It is known that every planar graph has interval number at most 3 and that this result is best possible. We investiga

Total chromatic number of planar graphs
Total chromatic number of planar graphs with maximum degree ten
✍ Weifan Wang πŸ“‚ Article πŸ“… 2006 πŸ› John Wiley and Sons 🌐 English βš– 161 KB πŸ‘ 1 views

## Abstract In this article we prove that the total chromatic number of a planar graph with maximum degree 10 is 11. Β© 2006 Wiley Periodicals, Inc. J Graph Theory 54: 91–102, 2007

The total chromatic number of graphs hav
The total chromatic number of graphs having large maximum degree
✍ A.J.W. Hilton; H.R. Hind πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 935 KB

Hilton, A.J.W. and H.R. Hind, The total chromatic number ofgraphs having large maximum degree, Discrete Mathematics 117 (1993) 127-140. The total colouring conjecture is shown to be correct for those graphs G having d(G)>21 V(G)I.

Maximum genus and girth of graphs
Maximum genus and girth of graphs
✍ Yuangqiu Huang πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 302 KB

In this paper, a lower bound on the maximum genus of a graph in terms of its girth is established as follows: let G be a simple graph with minimum degree at least three, and let g be the girth of G. Then ?M(G)~> ~fl(G) + 1 except for G=K4, g-1 where ]~(G) denotes the cycle rank of G and K4 is the co