Abstract
A coloring of graph vertices is called acyclic if the ends of each edge are colored in distinct colors and there are no two-colored cycles. Suppose each face of rank not greater than k, k ≥ 4, on a surface SN is replaced by the clique on the same set of vertices. Then the pseudograph obtained in this way can be colored acyclically in a set of colors whose cardinality depends linearly on N and on k. Results of this kind were known before only for 1 ≤ N ≤ 2 and 3 ≤ k ≤ 4.
Original language | English (US) |
---|---|
Pages (from-to) | 29-35 |
Number of pages | 7 |
Journal | Mathematical Notes |
Volume | 67 |
Issue number | 1 |
DOIs | |
State | Published - 2000 |
Externally published | Yes |
Keywords
- Acyclic coloring
- Acyclic graphs
- Cliques
- Embedded graphs
- Map coloring
ASJC Scopus subject areas
- General Mathematics