标题： 3-稀疏图的相邻顶点区分总着色 显示英文标题

标题： Adjacent vertex distinguishing total coloring of 3-degenerate graphs

摘要： 一个简单无向图$G$的总着色是将其顶点和边分配颜色的一种方式，使得分配给顶点的颜色形成一个正确的顶点着色，分配给边的颜色形成一个正确的边着色，并且每条边的颜色与其两个端点的颜色不同。 也就是说，如果对于所有$uv\in E(G)$，$\phi(u)\neq\phi(v)$且$\phi(uv)\neq\phi(u)$，那么$\phi:V(G)\cup E(G)\rightarrow\mathbb{N}$是$G$的完全着色，对于任何$u \in V(G)$和不同的$v,w \in N(u)$，$\phi(uv)\neq\phi(uw)$（这里，$N(u)$表示$u$的邻接点集合）。 一种图 $G$ 的总着色 $\phi$ 被称为“相邻顶点区分”（简称 AVD），如果对于所有 $uv\in E(G)$，我们有 $\phi(\{u\}\cup\{uw:w\in N(u)\})\neq\phi(\{v\}\cup\{vw\colon w\in N(v)\})$。 AVD全着色猜想由张、陈、李、姚、卢和王（中国科学A辑：数学，48(3):289--299, 2005）提出，该猜想指出每个图$G$至多用$\Delta(G)+3$种颜色进行AVD全着色，其中$\Delta(G)$表示$G$的最大度。 For some $s\in\mathbb{N}$, a graph $G$ is said to be $s$-degenerate if every subgraph of $G$ has minimum degree at most $s$. Miao, Shi, Hu, and Luo (Discrete Mathematics, 339(10):2446--2449, 2016) showed that the AVD Total Coloring Conjecture is true for 2-degenerate graphs. We verify the conjecture for 3-degenerate graphs. 显示英文摘要

摘要： A total coloring of a simple undirected graph $G$ is an assignment of colors to its vertices and edges such that the colors given to the vertices form a proper vertex coloring, the colors given to the edges form a proper edge coloring, and the color of every edge is different from that of its two endpoints. That is, $\phi:V(G)\cup E(G)\rightarrow\mathbb{N}$ is a total coloring of $G$ if $\phi(u)\neq\phi(v)$ and $\phi(uv)\neq\phi(u)$ for all $uv\in E(G)$, and $\phi(uv)\neq\phi(uw)$ for any $u \in V(G)$ and distinct $v,w \in N(u)$ (here, $N(u)$ denotes the set of neighbours of $u$). A total coloring $\phi$ of a graph $G$ is said to be ``Adjacent Vertex Distinguishing'' (or AVD for short) if for all $uv\in E(G)$, we have that $\phi(\{u\}\cup\{uw:w\in N(u)\})\neq\phi(\{v\}\cup\{vw\colon w\in N(v)\})$. The AVD Total Coloring Conjecture of Zhang, Chen, Li, Yao, Lu, and Wang (Science in China Series A: Mathematics, 48(3):289--299, 2005) states that every graph $G$ has an AVD total coloring using at most $\Delta(G)+3$ colors, where $\Delta(G)$ denotes the maximum degree of $G$. For some $s\in\mathbb{N}$, a graph $G$ is said to be $s$-degenerate if every subgraph of $G$ has minimum degree at most $s$. Miao, Shi, Hu, and Luo (Discrete Mathematics, 339(10):2446--2449, 2016) showed that the AVD Total Coloring Conjecture is true for 2-degenerate graphs. We verify the conjecture for 3-degenerate graphs.