Let G → = (V,A) be an oriented graph, G = (V,E) the underlying graph of G → and k be a positive integer. An oriented k-coloring of G → is a partition of V into k subsets, such that there are no two adjacent vertices belonging to the same subset, and all the arcs between a pair of subsets have the same orientation. The oriented chromatic number χ ° (G → ) of G → is the smallest k , such that G → admits an oriented k -coloring. The oriented chromatic number of G, denoted by χ ° (G), is the maximum of χ ° (G → ) for all orientations G → of G . Given two graphs G and H with V(G) n V(H) = θ, we say that G U H is the disjoint union graph of G and H , if V(G U H) = V(G) U V(H) and E(G U H) = E(G) U E(H). A wheel graph W q ,q ≥ 3 has V(W q ) = {v1, v2, ... ,v q ,c} and E(Wq) = {v i -v i+1 : i ε {1,2,...,q- 1}} U { v q v 1 } U { v i c : i ε {1,2,...,q}}. Wheel graphs consist of a important class having many theoretical and algorithmic applications with an ample literature on coloring problems. Bounds for the oriented coloring of wheel graphs were evaluated on the literature, but the exact values were not known. In this paper we determine the exact value of χ o (W q ) as q + 1 when 3 ≤ q ≤ 6, 7 whether q =7 and 8 whether q ≥ 8, producing a linear time algorithm to color any wheel graph. Let K p be the complete graph with p ≥ 1 vertices, when q ≤ 8 we give exact values for χ o (K p U W q ) and for large values of q ≥ 9 we show that χ o (K p U W q ) is either p + 2 or p + 3.

A k-total coloring of a graph G = (V, E) is an assignment of k colors to the elements of G , such that adjacent or incident elements have different colors. Let ∆ be the maximum vertex degree of a graph G , the Total Coloring Conjecture states that every graph G is (∆ + 1), or (∆ + 2)-total colorable. In 1994, McDiarmid and Sánchez-Arroyo proved that the total coloring problem, asking whether a graph G is (∆ + 1)-total colorable, is NP-complete even when G is k -regular, k ≥ 3 and bipartite. In 1988, Chetwynd and Hilton defined conformable vertex coloring in the attempt to characterize the vertex coloring induced by a (∆ + 1)-total coloring. A (∆ + 1)-vertex coloring of a graph G is called conformable if the number of color classes of parity different from that of | V | is at most the deficiency def(G) =∑ v∈V (Δ − dG(v)) of G , where d G ( v) is the degree of a vertex v of V. Recently, it was proved that conformability is polynomial for maximum degree three graphs. However, the general time-complexity of conformability status remains unknown. Not every conformable coloring extends naturally to a (∆ + 1)-total coloring. One might ask when, or what properties a conformable vertex coloring should have to extend to a (∆ + 1)-total coloring. In this paper, we introduce the concept of strong conformable coloring a conformable coloring that extends to a total coloring. A strong conformable coloring is a conformable coloring with two additional properties. We show that each of these two properties is necessary in order to extend a conformable to a total coloring. Furthermore, we prove that a graph G is strong conformable if and only if G has a (∆ + 1)-total coloring. Consequently, we deliver the bad news that strong conformable vertex coloring problem is NP-complete even for bipartite k -regular graphs with k ≥ 3.

Musical arrangements have recently been considered from an algorithmic point of view. Demaine and Moses, in 2017, introduced three decision problems associated with musical arrangements. In these problems, the input is a score H consisting of n staves corresponding to the participating instruments and a parameter p, 0 ≤ p ≤ 1. The goal is to determine whether there is a subset H’ c H satisfying some properties, such that in each time unit p% of the input score H is played. In this paper, we take a step forward in this direction. We define more general versions of two of the original problems, which we call general consonant arrangement (con-arr) and general j -simultaneous notes ( j-notes ) with two additional parameters: s , a lower bound for the number of required staves in the solution, and k , a lower bound for the number of time units in which p% of the input score is played. We state the name of the problem followed by the parameter in parentheses to indicate which parameter is being maximized. We show that con-arr( k ) is MAXSNP-hard and that con-arr( s ) and j-notes(s) are not approximable within n 1_ε , for every ε > 0, unless P=NP. Let ∆ be the maximum number of staves that play simultaneously with any single stave at any moment in the music. If ∆ = 4, then con-arr(s) is MAXSNP-hard, because maximum degree 4 independent set is MAXSNP-complete, and it is polynomial-time 1/5-approximable. The j-notes (s) problem is O((∆ + 1) s .n 2 )-time solvable, i.e., it is in FPT with respect to the parameters ∆ and s. We also introduce two new problems we think are of musical interest: the arrangement for k instruments ( k -arrangement) and the time filling by instruments (fill-inst), which we prove to be hard. In particular, k -arrangement is hard even if each stave has exactly 2 notes. Also, k -arrangement is not polynomially approximable within a n 1 - ε factor, for ε > 0, unless P=NP. Finally, fill-inst is in FPT with respect to parameter τ, the maximum number of staves playing in each time, and in the size k of the solution. We prove that if P≠NP, then the best approximation ratio for fill-inst is Θ(log T) , where T is the number of non-silent times of an input.

Let ⃗G = (V, A) be an oriented graph. An oriented k-coloring of ⃗G is a partition of V into k color classes, such that there is no pair of adjacent vertices belonging to the same class and all the arcs between a pair of color classes have the same orientation. The smallest k such that ⃗G admits an oriented k-coloring is the oriented chromatic number Xo(⃗G) = k of ⃗G. In an oriented coloring of ⃗G every pair of vertices with oriented distance at most 2 in ⃗G have different colors. In 2004, Klostermeyer and MacGillivray defined the concept of an “analogue of clique” for oriented coloring in which a subgraph ⃗H of ⃗G is an oriented clique if every pair of vertices of ⃗H is in an oriented distance of at most 2 in ⃗H. The authors defined the absolute oriented clique number of ⃗G as the number of vertices |V(H)| = ωao(⃗G) of the largest oriented clique ⃗H of ⃗G and satisfies that ωao(⃗G) ≤ Xo(⃗G). Ever since, for almost 20 years, the time complexity status of this parameter remained unknown. The relative oriented clique number ωao(⃗G) of an oriented graph ⃗G is the size of the largest set of vertices R, such that every pair of vertices of R is at a maximum oriented distance of 2 in R. For every oriented graph ⃗G, ωao(⃗G) ≤ ωro(⃗G) ≤ Xo(⃗G). In this paper we classify Absolute Oriented Clique - the Klostermeyer and Mac Gillivray's decision problem - proving that given an oriented graph ⃗G and a positive integer k it is NP-complete to decide whether ωao(⃗G) ≥ k. We prove that for all ε > 0, there is no polynomial-time approximation for Relative Oriented Clique and for Absolute Oriented Clique within a factor of n1_ε, unless P = NP. Finally, we prove that Relative Oriented Clique is W[1]-complete and that Absolute Oriented Clique belongs to W[2] and is W[1]-hard.

A directed hypergraph H = (V, A) is a finite set of vertices V and a set of hyper-arcs A, where each hyper-arc is an ordered pair of nonempty subsets of vertices. A flow hypergraph H = (V, A, s) is a triple, such that (V, A) is a directed hypergraph, s e V is a distinguished vertex such that s reaches every vertex of V. Reducible flow hypergraphs are a generalization of Hecht and Ullman’s reducible flowgraphs. The feedback vertex set (fvs) decision problem has a directed hypergraph H and an integer k ≥ 0 as input and the question is whether there is V'⊆V, |V' |≤k such that H\V' is an acyclic directed hypergraph. It is known that fvs is polynomial time solvable for reducible flowgraphs. In this article we prove that fvs is NP-complete for reducible flow hypergraphs showing a reduction from 3-satisfiability problem with at most 3 occurrences per variable (3sat3-). We exhibit a polynomial-time ∆-approximation for fvs in reducible flow hypergraphs, where ∆ is the maximum number of hyper-arcs adjacent to a vertex of H.

Abstract Scheduling by Edge Reversal provides an order of operation for nodes in a graph, but maximizing or minimizing the resulting concurrency is hard. In this paper, we discuss a series of real‐world applications for this technique and propose algorithms for both problems. For maximum concurrency, we prove its general inapproximability and introduce approximation algorithms for classes of graphs. For minimum concurrency, we use hardness and inapproximability results to establish its relation to longest cycles, while also introducing a novel application for assembling musical phrases.

A fullerene graph is a cubic bridgeless plane graph with all faces of size $5$ and $6$. We show that every fullerene graph on $n$ vertices can be made bipartite by deleting at most $\sqrt{12n/5}$ edges and has an independent set with at least $n/2-\sqrt{3n/5}$ vertices. Both bounds are sharp, and we characterize the extremal graphs. This proves conjectures of Došlić and Vukičević and of Daugherty. We deduce two further conjectures on the independence number of fullerene graphs, as well as a new upper bound on the smallest eigenvalue of a fullerene graph.

H. Eriksson et al. made a breakthrough to the problem of sorting by transpositions by proposing a quotient structure named toric graph, which allowed the reduction of the search space, establishing the transposition diameter $D_t(n)=\lfloor\frac{n+1}{2}\rfloor+1$, for the cases $n=13$ and $n=15$, and invalidating a conjecture by J. Meidanis, M. E. M. T. Walter, and Z. Dias that the transposition diameter would be equal to the transposition distance of the reverse permutation $\lfloor n/2\rfloor+1$. I. Elias and T. Hartman extended the lower bound $D_t(n)\geq\lfloor\frac{n+1}{2}\rfloor+1$, to all odd values of n, $n\geq13$. The value $n=15$ is the largest for which $D_t(n)$ is known. The goal of the present paper is to further study the toric graph, focusing on the case when $n+1$ is prime, providing positive evidence that J. Meidanis, M. E. M. T. Walter, and Z. Dias's conjecture is still valid when n is even. We show that, when $n+1$ is prime, the properties of the reverse permutation are shared by permutations that fall into unitary toric classes; we prove that their reality and desire diagrams have just one cycle, consequently proving that those permutations are separated by at least $n/2$ transpositions among themselves, and we show that there are at least two permutations whose transposition distance is $n/2$ and two permutations, other than the reverse, whose distance is at least $n/2+1$, with respect to the identity.