Neighbor sum distinguishing total coloring of triangle free IC-planar graphs (Q1987570)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Neighbor sum distinguishing total coloring of triangle free IC-planar graphs |
scientific article |
Statements
Neighbor sum distinguishing total coloring of triangle free IC-planar graphs (English)
0 references
15 April 2020
0 references
A graph $G=(V,E)$ is called IC-planar if it admits a drawing on the plane such that each edge is crossed at most once and two crossed edges share no common end-vertex. For a positive integer $k$, let $c: V\cup E \rightarrow \{1,2, \dots, k\}$ be a proper total $k$-coloring of $G$. Denote by $\sum_c(v)$ the sum of the color of a vertex $v$ and the colors of all edges incident with $v$. A proper total $k$-coloring $c$ of $G$ is said to be neighbor-sum distinguishing if $\sum_c(u)= \sum_c(v)$ for every edge $uv$ of $G$. The smallest number $k$ of colors needed for a neighbor-sum distinguishing total coloring of $G$, denoted by $\chi^{\prime\prime}_{\Sigma}(G)$, is defined as the neighbor-sum distinguishing total chromatic number. \textit{M. Pilśniak} and \textit{M. Woźniak} [Graphs Comb. 31, No. 3, 771--782 (2015; Zbl 1312.05054)] conjectured that $\chi^{\prime\prime}_{\Sigma}(G) \leq \Delta (G) +3$ for any simple graph $G$ with maximum degree $\Delta (G)$. Using the so-called combinatorial Nullstellensatz, the authors show that the conjecture is true for any triangle-free IC-planar graph with $\Delta (G) \geq 7$, and it is also true for any triangle-free planar graph with $\Delta (G) \geq 6$.
0 references
neighbor sum distinguishing total coloring
0 references
combinatorial Nullstellensatz
0 references
triangle free IC-planar graph
0 references
maximum degree
0 references
0 references
0 references