| Title | : | Adjacent vertex distinguishing total coloring of 3-degenerate graphs |
| Speaker | : | Sreejith K. Pallathumadam (IIT Madras) |
| Details | : | Tue, Sep 30, 2025 3:30 PM, @ CS34 |
| 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 Δ+1 colors for any total coloring of G where Δ is the maximum
degree of G. Surprisingly, Behzad (PhD Thesis, Michigan State University, 1965) and Vizing (Russian
Mathematical Surveys, 1968) independently conjectured that Δ+2 colors are sufficient.
Note that a triangle needs only Δ+1 (i.e. three) colors for a total coloring while a 4-cycle requires Δ+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 Adjacent Vertex Distinguishing (AVD) if for each uv in E(G), colors(u) ≠ colors(v). The AVD Total Coloring Conjecture of Zhang, Chen, Li, Yao, Lu and Wang (Science in China Series A: Mathematics, 2005) states that every graph G admits an AVD total coloring using at most Δ+3 colors. It is easy to verify that a triangle requires Δ+3 (i.e. five) colors for an AVD total coloring. For some natural number s, 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 (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. Preprint: https://arxiv.org/abs/2508.03549 This is a joint work with Dr. Mathew C. Francis (IIT Palakkad) and Diptimaya Behera (ISI Chennai) |