A proper vertex coloring of a graph $G$ is acyclic if there is no bicolored cycle in $G$. In other words, each cycle of $G$ must be colored with at least three colors. Given a list assignment $L=\left\{L\right(v):v\in V\}$, if there exists an acyclic coloring $\pi$ of $G$ such that $\pi \left(v\right)\in L\left(v\right)$ for all $v\in V$, then we say that $G$ is acyclically $L$-colorable. If $G$ is acyclically $L$-colorable for any list assignment $L$ with $\left|L\right(v\left)\right|\ge k$ for all $v\in V$, then $G$ is acyclically $k$-choosable. In 2006, Montassier, Raspaud and Wang conjectured that every planar graph without 4-cycles...

A k-colouring of a graph G is a mapping c from the set of vertices of G to the set {1, . . . , k} of colours such that adjacent vertices receive distinct colours. Such a k-colouring is called acyclic, if for every two distinct colours i and j, the subgraph induced by all the edges linking a vertex coloured with i and a vertex coloured with j is acyclic. In other words, every cycle in G has at least three distinct colours. Acyclic colourings were introduced by Gr¨unbaum in 1973, and since then have...

Within geometric topology of 3-manifolds (with or without boundary), a representation theory exists, which makes use of 4-coloured graphs. Aim of this paper is to translate the homeomorphism problem for the represented manifolds into an equivalence problem for 4-coloured graphs, by means of a finite number of graph-moves, called dipole moves. Moreover, interesting consequences are obtained, which are related with the same problem in the n-dimensional setting.

Let $e_{ij}$ be the number of edges in a convex 3-polytope joining the vertices of degree i with the vertices of degree j. We prove that for every convex 3-polytope there is $20e_{3,3}+25e_{3,4}+16e_{3,5}+10e_{3,6}+6[2/3]e_{3,7}+5e_{3,8}+2[1/2]e_{3,9}+2e_{3,10}+16[2/3]e_{4,4}+11e_{4,5}+5e_{4,6}+1[2/3]e_{4,7}+5[1/3]e_{5,5}+2e_{5,6}\ge 120$; moreover, each coefficient is the best possible. This result brings a final answer to the conjecture raised by B. Grünbaum in 1973.

The basis number of a graph $G$ is defined by Schmeichel to be the least integer $h$ such that $G$ has an $h$-fold basis for its cycle space. MacLane showed that a graph is planar if and only if its basis number is $\le 2$. Schmeichel proved that the basis number of the complete graph $K_n$ is at most $3$. We generalize the result of Schmeichel by showing that the basis number of the $d$-th power of $K_n$ is at most $2d+1$.