Advanced Search

An adjacent vertex distinguishing edge-coloring of a graph G is a proper edge-coloring o G such that any pair of adjacent vertices are incident to distinct sets of colors. The minimum number of colors required for an adjacent vertex distinguishing edge-coloring of G is denoted by χ'ₐ(G). We prove that χ'ₐ(G) is at most the maximum degree plus 2 if G is a planar graph without isolated edges whose girth is at least 6. This gives new evidence to a conjecture proposed in [Z. Zhang, L. Liu, and J. Wang,...

Given a graph $G=(V,E)$, if we can partition the vertex set $V$ into two nonempty subsets $V_1$ and $V_2$ which satisfy $\Delta \left(G\left[V_1\right]\right)\le d_1$ and $\Delta \left(G\left[V_2\right]\right)\le d_2$, then we say $G$ has a $({\Delta }_{d_1},{\Delta }_{d_2})$-partition. And we say $G$ admits an $(F_{d_1},F_{d_2})$-partition if $G\left[V_1\right]$ and $G\left[V_2\right]$ are both forests whose maximum degree is at most $d_1$ and $d_2$, respectively. We show that every planar graph with girth at least 5 has an $(F_4,F_4)$-partition.

It was known that the vertex set of every planar graph can be partitioned into three forests. We prove that the vertex set of a planar graph without chordal 5-cycles can be partitioned into two forests. This extends a result obtained by Raspaud and Wang in 2008.