Narrow Results

We present efficient algorithms for three coloring problems on subcubic graphs. (A subcubic graph has maximum degree at most three.) The first algorithm is for 4-edge coloring, or more generally, 4-list-edge coloring. Our algorithm runs in linear time, and appears to be simpler than previous ones. The second algorithm is the first randomized EREW PRAM algorithm for the same problem. It uses O(n/log n) processors and runs in O(log n) time with high probability, where n is the number of vertices of the graph. The third algorithm is the first linear-time algorithm to 5-total-color subcubic graphs. The fourth algorithm generalizes this to get the first linear-time algorithm to 5-list-total-color subcubic graphs. Our sequential algorithms are based on a method of ordering the vertices and edges by traversing a spanning tree of a graph in a bottom-up fashion. Our parallel algorithm is based on a simple decomposition principle for subcubic graphs.

A total coloring of a graph G is a coloring of all elements of G, i.e. vertices and edges, in such a way that no two adjacent or incident elements receive the same color. Many combinatorial problems can be efficiently solved for partial k-trees, that is, graphs of treewidth bounded by a constant k. However, no polynomial-time algorithm has been known for the problem of finding a total coloring of a given partial k-tree with the minimum number of colors. This paper gives such a first polynomial-time algorithm.

A total coloring of a graph $G$ is an assignment of colors to the elements of the graph $G$ such that no adjacent vertices and edges receive the same color. The total chromatic number of a graph $G$, denoted by ${\chi }^{″}(G)$, is the minimum number of colors that suffice in a total coloring. Behzad and Vizing conjectured that for any simple graph $G$, $\mathrm{\Delta }(G)+1\le {\chi }^{″}(G)\le \mathrm{\Delta }(G)+2$, where $\mathrm{\Delta }(G)$ is the maximum degree of $G$. In this paper, we prove the tight bound of the total coloring conjecture for the three types of corona products (vertex, edge and neighborhood) of graphs.

A total coloring of a graph is an assignment of colors to all the elements of the graph such that no two adjacent or incident elements receive the same color. A graph $G$ is prismatic, if for every triangle $T$, every vertex not in $T$ has exactly one neighbor in $T$. In this paper, we prove the total coloring conjecture (TCC) for prismatic graphs and the tight bound of the TCC for some classes of prismatic graphs.

The total chromatic number ${\chi }^{″}(G)$ is the least number of colors needed to color the vertices and edges of a graph $G$ such that no incident or adjacent elements (vertices or edges) receive the same color. Behzad and Vizing proposed a well-known total coloring conjecture (TCC): ${\chi }^{″}(G)\le \mathrm{\Delta }(G)+2$, where $\mathrm{\Delta }(G)$ is the maximum degree of $G$. For the powers of cycles, Campos and de Mello proposed the following conjecture: Let $G=C_n^k$ denote the graphs of powers of cycles of order $n$ and length $k$ with $2\le k<\lfloor \frac{n}{2}\rfloor$. Then,

A total coloring of a graph is an assignment of colors to all the elements (vertices and edges) of the graph such that no two adjacent or incident elements receive the same color. A claw-free graph is a graph that does not have $K_{1,3}$ as an induced subgraph. Quasi-line and inflated graphs are two well-known classes of claw-free graphs. In this paper, we prove that the quasi-line and inflated graphs are totally colorable. In particular, we prove the tight bound of the total chromatic number of some classes of quasi-line graphs and inflated graphs.

A total coloring of a graph G is an assignment of colors to all the elements (vertices and edges) of the graph in such a way that no two adjacent or incident elements receive the same color. The Total Chromatic Number, ${\chi }^{″}(G)$ is the minimum number of colors which need to be assigned to obtain a total coloring of the graph $G$. The Total Coloring Conjecture made independently by Behzad and Vizing claims that, $\mathrm{\Delta }(G)+1\le {\chi }^{″}(G)\le \mathrm{\Delta }(G)+2$, where $\mathrm{\Delta }(G)$ represents the maximum degree of $G$. The lower bound is sharp, the upper bound remains to be proved. In this paper, we prove the Total Coloring Conjecture for certain classes of lexicographic product and deleted lexicographic product of graphs.

Total coloring is a function that assigns colors to the vertices and edges of the graph such that the adjacent and the incident elements receive different colors. The minimum number of colors required for a proper total coloring of a graph $G$ is called the total chromatic number of $G$ and is denoted by ${\chi }^{″}(G)$. Behzad–Vizing conjecture (Total Coloring Conjecture) states that for any graph $G$, ${\chi }^{″}(G)\le \mathrm{\Delta }(G)+2$, where $\mathrm{\Delta }(G)$ is the maximum degree of $G$. In this paper, we verify the Behzad–Vizing conjecture for some product graphs.