Search

A kite is a complete graph on four vertices with one edge removed. It is proved that every planar graph without a kite as subgraph can be partitioned into two induced forests. This resolves a conjecture of Raspaud and Wang in 2008. [ABSTRACT FROM AUTHOR]

A noncomplete graph G $G$ of diameter d $d$ is called an antipodal r $r$‐cover if its vertex set can be partitioned into the subsets (also called fibres) V1,V2,...,Vm ${V}_{1},{V}_{2},\ldots ,{V}_{m}$ of r $r$ vertices each, in such a way that two vertices of G $G$ are at distance d $d$ if and only if they belong to the same fibre. We say that G $G$ is symmetric if for every u∈Vi,v∈Vj $u\in {V}_{i},v\in {V}_{j}$, there exist u′∈Vi $u^{\prime} \in {V}_{i}$ such that d(u,u′)=d(u,v)+d(v,u′) $d(u,u^{\prime})=d(u,v)+d(v,u^{\prime})$, where 1≤i≠j≤m $1\le i\ne j\le m$. In this paper, we prove that, for r≥2 $r\ge 2$, an antipodal r $r$‐cover which is not a cycle, has at least r3d2 $r\unicode{x0230A}\frac{3d}{2}\unicode{x0230B}$ vertices provided d≥3 $d\ge 3$, and at least 2r(d−1) $2r(d-1)$ vertices provided it is symmetric. Our results extend those of Göbel and Veldman. [ABSTRACT FROM AUTHOR]

An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index [ABSTRACT FROM AUTHOR]