Title | : | Adjacent vertex distinguishing total coloring of 3-degenerate graphs |
Speaker | : | Sreejith K. Pallathumadam (IIT Madras) |
Details | : | Tue, 30 Sep, 2025 3:30 PM @ CSB 34 |
Abstract: | : | A total coloring of a simple undirected graph $G$ is an assignment of colors to its vertices and edges such that the colors assigned to the vertices form a proper vertex coloring, the colors assigned to the edges form a proper edge coloring, and the color of every edge is different from that of its ends. It is easy to verify that $G$ needs at least $Delta + 1$ colors for any total coloring of $G$ where $Delta$ is the maximum degree of $G$. Surprisingly, Behzad (emph{PhD Thesis, Michigan State University, 1965}) and Vizing (emph{Russian Mathematical Surveys, 1968}) independently conjectured that $Delta + 2$ colors are sufficient. Note that a triangle needs only $Delta + 1$ (i.e. three) colors for a total coloring while a 4-cycle requires $Delta + 2$ (i.e. four) colors. Interestingly, the conjecture is still open. Given a total coloring of a graph $G$, for each vertex $u$, let $colors(u)$ denote the set comprising the color assigned to $u$ and the colors assigned to the edges incident with $u$. A total coloring of a graph $G$ is emph{Adjacent Vertex Distinguishing (AVD)} if for each $uv in E(G)$, $colors(u) neq colors(v)$. The emph{AVD Total Coloring Conjecture} of Zhang, Chen, Li, Yao, Lu and Wang (emph{Science in China Series A: Mathematics, 2005}) states that every graph $G$ admits an AVD total coloring using at most $Delta + 3$ colors. It is easy to verify that a triangle requires $Delta + 3$ (i.e. five) colors for an AVD total coloring. For $s in mathbb{N}$, a graph $G$ is $s$-degenerate if every subgraph of $G$ has a vertex of degree at most $s$. For example, forests are 1-degenerate (what about the converse?), outerplanar graphs are 2-degenerate, triangle-free planar graphs are 3-degenerate and planar graphs are 5-degenerate. Miao, Shi, Hu and Luo (emph{Discrete Mathematics, 2016}) proved the AVD Total Coloring Conjecture for 2-degenerate graphs. We recently proved the conjecture for 3-degenerate graphs; in this talk, we shall discuss this result. |