EUDML

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 = {L (v) : v \in V}$ , if there exists an acyclic coloring $π$ of $G$ such that $π (v) \in L (v)$ 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 $| L (v) | \geq 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...

Partitioning planar graph of girth 5 into two forests with maximum degree 4

Min Chen; André Raspaud; Weifan Wang; Weiqiang Yu — 2024

Czechoslovak Mathematical Journal

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 $Δ (G [V_{1}]) \leq d_{1}$ and $Δ (G [V_{2}]) \leq d_{2}$ , then we say $G$ has a $(Δ_{d_{1}}, Δ_{d_{2}})$ -partition. And we say $G$ admits an $(F_{d_{1}}, F_{d_{2}})$ -partition if $G [V_{1}]$ and $G [V_{2}]$ 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.

Page 1

Download Results (CSV)

Advanced Search

Formula preview

Currently displaying 1 – 9 of 9

A fundamental domain for the modular group of Riemann surfaces of type $(0, n)$ .

Differentiability and rigidity theorems.

Steady-state bifurcations of the three-dimensional Kolmogorov problem.

Discriminant analysis of zero recovery for China's NPL.

Bifurcations of finite difference schemes and their approximate inertial forms

Incremental unknowns for solving partial differential equations.

Nonlinear Galerkin method in the finite difference case and wavelet-like incremental unknowns.

Acyclic 4-choosability of planar graphs without 4-cycles

Partitioning planar graph of girth 5 into two forests with maximum degree 4