Loading...
Please wait, while we are loading the content...
Similar Documents
Coloring graphs with fixed genus and girth (1997)
| Content Provider | CiteSeerX |
|---|---|
| Author | Gimbel, John Thomassen, Carsten |
| Abstract | 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 g1/3 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. 1. |
| File Format | |
| Journal | Trans. Am. Math. Soc |
| Language | English |
| Publisher Date | 1997-01-01 |
| Access Restriction | Open |
| Subject Keyword | Chromatic Number Fixed Genus Triangle-free Graph Similar Result Positive Constant C1 C1 G1 Double Torus Specific Surface Triangle-free Projective Graph Maximum Chromatic Number Orientable Surface Sg Restricted Clique Number |
| Content Type | Text |
| Resource Type | Article |
