<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>
A proper $n$-coloring of a graph $G$ is an assignment of colors from $\{1,\ldots,n\}$ to its vertices such that no two adjacent vertices get assigned the same color. The chromatic number of $G$, denoted by $\chi(G)$, refers to the smallest $n$ such that $G$ admits a proper $n$-coloring. This notion naturally extends to edge-colorings (resp. total-colorings) when edges (resp. both vertices and edges) are to be colored, and this provides other parameters of $G$: its chromatic index $\chi'(G)$ and its total chromatic number $\chi''(G)$.These coloring notions are among the most fundamental ones of the graph coloring theory.As such, they gave birth to hundreds of studies dedicated to several of their aspects,including generalizations to more general structures such as oriented graphs.They include notably the notions of oriented $n$-colorings and oriented $n$-arc-colorings,which stand as natural extensions of their undirected counterparts, and which have been receiving increasing attention.Our goal is to introduce a missing piece in this line of work, namely the oriented counterparts of proper $n$-total-colorings and total chromatic number. We first define these notions and show that they share properties and connections with oriented (arc) colorings that are reminiscent of those shared by their undirected counterparts. We then focus on understanding the oriented total chromatic number of particular types of oriented graphs, such as oriented forests, cycles, and some planar graphs.Finally, we establish a full complexity dichotomy for the problem of determining whether an oriented graph is totally $k$-colorable.Throughout this work, each of our results is compared to what is known regarding the oriented chromatic number and oriented chromatic index. We also disseminate some directions for further research on the oriented total chromatic number.
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Total-coloring, Oriented coloring, Oriented arc-coloring, Oriented graph
[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], Total-coloring, Oriented coloring, Oriented arc-coloring, Oriented graph
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |