Currently displaying 1 – 9 of 9

Showing per page

Order by Relevance | Title | Year of publication

Acyclic 4-choosability of planar graphs without 4-cycles

Yingcai SunMin Chen — 2020

Czechoslovak Mathematical Journal

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 V } , if there exists an acyclic coloring π of G such that π ( v ) L ( v ) for all v V , then we say that G is acyclically L -colorable. If G is acyclically L -colorable for any list assignment L with | L ( v ) | k for all v 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 ChenAndré RaspaudWeifan WangWeiqiang 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 ] ) d 1 and Δ ( G [ V 2 ] ) 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)