A theta graph is a graph obtained by joining two vertices by three internally disjoint paths of lengths 2, 1, and 2. A neighbor sum distinguishing (NSD) total coloring of G is a proper total coloring of G such that for each edge , where denotes the set of edges incident with a vertex u. In 2015, Pilśniak and Woźniak introduced this coloring and conjectured that every graph with maximum degree admits an NSD total -coloring. In this paper, we show that the listing version of this conjecture holds for any IC-planar graph with maximum degree but without theta graphs by applying the Combinatorial Nullstellensatz, which improves the result of Song et al.
A proper total k-coloring of G with for each is called a total neighbor sum distinguishing k-coloring, where . Pilśniak and Woźniak conjectured that every graph with maximum degree exists a total neighbor sum distinguishing -coloring. In this paper, we proved that any IC-planar graph with satisfies this conjecture, which improves the result of Song and Xu.
18 August 2021 in Journal of Discrete Mathematical Sciences and Cryptography
A NIC-planar graph is a graph that has a drawing in the plane such that each edge is crossed at most once and any two pairs of crossing edges share at most one common vertex. Let EG (u) denote the set of edges incident with a vertex u. A neighbor sum distinguishing (NSD) total coloring ϕ of G is a proper total coloring of G such that for each edge uυ ∈E(G) . Pilśniak and Woźniak conjectured that any graph with maximum degree Δ admits an NSD total (Δ+ 3) -coloring. In this paper, we prove that the list version of the conjecture holds for any triangle-free NIC-planar graph with Δ ≥ 8 and with each vertex incident with at most two crossing edges by applying the Combinatorial Nullstellensatz.
15 November 2021 in Czechoslovak Mathematical Journal