An equitable coloring of a graph G is a proper vertex coloring of G such that the sizes of any two color classes differ by at most one. In the paper, we pose a conjecture that offers a gap-one bound for the smallest number of colors needed to equitably color every block graph. In other words, the difference between the upper and the lower bounds of our conjecture is at most one. Thus, in some sense, the situation is similar to that of chromatic index, where we have the classical theorem of Vizing and the Andersen–Goldberg–Seymour conjecture for multigraphs. The results obtained in the paper support our conjecture. More precisely, we verify it in the class of block graphs in which each vertex belongs to a maximum independent set. We also show that the conjecture is true for block graphs which contain a vertex that does not lie in an independent set of size larger than two. Finally, we verify the conjecture for some symmetric-like block graphs. In order to derive our results we obtain structural characterizations of block graphs from these classes.

An adjacent vertex distinguishing total k-coloring f of a graph G is a proper total k-coloring of G such that no pair of adjacent vertices has the same color sets. In 2005 Zhang et al. posted the conjecture (AVDTCC) that every simple graph G has adjacent vertex distinguishing total (∆(G) + 3)-coloring. In this paper we confirm the conjecture for many coronas, in particular for generalized, simple and l-coronas of graphs, not relating the results to particular graph classes.

The problem of scheduling jobs on parallel machines under an incompatibility relation is considered in this paper. In this model, a binary relation between jobs is given and no two jobs that are in the relation can be scheduled on the same machine. We consider job scheduling under the incompatibility relation modeled by a bipartite graph, under the makespan optimality criterion, on uniform and unrelated machines. Unrelated machines are considered first. An FPTAS for$R2\vert G=bipartite\vert C_{\max}$is provided. We also show that for any$\epsilon > 0, b > 0$and$m\geq 3$, there is no polynomial-time algorithm of approximation ratio$\mathrm{O}(n^{b}p_{\max}^{1-\epsilon})$for$Rm\vert G$= bipartite$\vert C_{\max}$, unless P = NP. Uniform machines are considered as second. For any$\epsilon > 0$, we show that under P = NP assumption there is no polynomial-time$\mathrm{O}(n^{1/2-\epsilon}$)-approximation algorithm, even in the case of unit time jobs. We also provide a polynomial-time$\sqrt{\Sigma p_{j}}$-approximation algorithm for the case of jobs of arbitrary lengths$p_{j}$, matching the established bound. To enrich the analysis, bipartite graphs generated randomly according to Gilbert's model$\mathbb{G}_{n,n,p(n)}$are considered. We show that there exists an algorithm producing a schedule with makespan almost surely at most twice the optimum for a broad class of$p(n)$functions. To the best of our knowledge, this is the first study of randomly generated graphs in the context of scheduling in the considered model.