Orientations with forbidden out-degree and total-coloring extensions

Abstract

This thesis studies two topics in graph theory: graph orientations with forbidden out-degrees and extensions of total-colorings.

An orientation of a graph assigns a direction to each edge, thereby prescribing for each vertex the number of edges directed away from it, called its out-degree. A natural question is to determine when it is possible to orient a graph so that each vertex avoids a prescribed set of forbidden out-degrees. More formally, given a graph $G$ and a function $F:V(G)\to 2^{\mathbb{N}}$, an $F$-avoiding orientation is one in which no vertex $v$ has out-degree in its forbidden set $F(v)$. Akbari et al.\ conjectured that when $|F(v)|< \frac{1}{2}\deg_G(v)$ for all $v$, then $G$ admits an $F$-avoiding orientation. This conjecture remains open even when $G$ is regular and all vertices share the same forbidden list. We extend known results on this problem by verifying the conjecture when $G$ is $5$- and $6$-regular, as well as confirming the general conjecture in several additional cases, including for sparse graph classes and structured families of forbidden sets.

The second part of the thesis focuses on coloring extension problems, which ask whether a given partial coloring can be extended to a coloring of the entire graph without introducing new colors. A total-coloring of a graph assigns colors to both its vertices and edges so that no adjacent or incident elements receive the same color. A central open problem in this area, the Total Coloring Conjecture, asserts that every graph admits a total-coloring using at most $\Delta+2$ colors, where $\Delta$ is the maximum degree.

We initiate a systematic study of total-coloring extensions by formulating new conjectures inspired by the literature on vertex- and edge-coloring extensions. Our conjectures strengthen the Total-Coloring Conjecture, and thus natural candidate graph classes for their study are those for which the Total-Coloring Conjecture is known to hold. To this end, we establish extension results for planar graphs with large maximum degree. We also prove total-coloring extension results for several other families of graphs.