Loading...
Please wait, while we are loading the content...
Similar Documents
Coloring Graphs with Fixed Genus and Girth
| Content Provider | Semantic Scholar |
|---|---|
| Author | Gimbel, John Thomassen, Carsten |
| Copyright Year | 1997 |
| Abstract | It is well known that the maximum chromatic number of a graph on the orientable surface Sg is θ(g1/2). We prove that there are positive constants c1, c2 such that every triangle-free graph on Sg has chromatic number less than c2(g/ log(g))1/3 and that some triangle-free graph on Sg has chromatic number at least c1 g log(g) . We obtain similar results for graphs with restricted clique number or girth on Sg or Nk. As an application, we prove that an Sg-polytope has chromatic number at most O(g3/7). For specific surfaces we prove that every graph on the double torus and of girth at least six is 3-colorable and we characterize completely those triangle-free projective graphs that are not 3-colorable. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.ams.org/journals/tran/1997-349-11/S0002-9947-97-01926-0/S0002-9947-97-01926-0.pdf |
| Alternate Webpage(s) | http://www.ams.org/tran/1997-349-11/S0002-9947-97-01926-0/S0002-9947-97-01926-0.pdf |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Clique (graph theory) Genus (mathematics) Girth (graph theory) Graph - visual representation Graph coloring |
| Content Type | Text |
| Resource Type | Article |
