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
    0 references
    0 references
    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
    0 references
    0 references
    0 references
    0 references
    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