A regular graph is one where every vertex has the same degree. An irregular graph — where no two adjacent vertices share the same degree — is much harder to achieve. In fact, no connected graph on more than one vertex can be irregular in this simple sense, because the pigeonhole principle forces degree repetitions. The concept needs refinement to become useful.
Baudon et al. (arXiv:2603.13178) study locally irregular total colorings: assign colors to both vertices and edges so that within each color class, no two adjacent vertices have the same total degree (counting incident edges and the vertex itself in that color). The parameter tlir(G) is the minimum number of colors needed.
A 2015 conjecture asserts that tlir(G) ≤ 2 for all graphs — two colors always suffice to partition any graph into locally irregular total subgraphs. The authors confirm this for cacti (graphs where every edge belongs to at most one cycle), subcubic graphs (maximum degree 3), and split graphs (vertex set partitions into a clique and an independent set). For general graphs, they prove bounds depending on the chromatic number, with constant bounds for planar and outerplanar graphs.
The technique connects two seemingly unrelated coloring problems: acyclic vertex coloring (where every two color classes induce a forest) provides the structural decomposition that locally irregular total coloring needs. The acyclic condition prevents cycles within color classes, and cycle-free subgraphs are easier to make locally irregular because the degree constraints don't loop back on themselves.