Neumann-Lara conjectured in 1985 that every planar digraph with digirth at least three is 2-colorable, meaning that the vertices can be 2-colored without creating any monochromatic directed cycles. We prove a relaxed version of this conjecture: every planar digraph of digirth at least four is 2-colorable.

We examine cooperative games where the viability of a coalition is determined by whether or not its members have the ability to communicate amongst themselves independently of non-members. This necessary condition for viability was proposed by Myerson [1977] and is modeled via an interaction graph G=(V,E); a coalition S ⊆ V is then viable if and only if the induced graph G[S] is connected. The non-emptiness of the core of a coalition game can be tested by a well-known covering LP. Moreover, the integrality gap of its dual packing LP defines exactly the multiplicative least-core and the relative cost of stability of the coalition game. This gap is upper bounded by the packing-covering ratio which, for graphical coalition games, is known to be at most the treewidth of the interaction graph plus one [Meir et al. 2013].

An identifying code of a graph is a subset of its vertices such that every vertex of the graph is uniquely identified by the set of its neighbors within the code. We show a dichotomy for the size of the smallest identifying code in classes of graphs closed under induced subgraphs. Our dichotomy is derived from the VC-dimension of the considered class $\mathcal{C}$, that is, the maximum VC-dimension over the hypergraphs formed by the closed neighborhoods of elements of $\mathcal{C}$. We show that hereditary classes with infinite VC-dimension have infinitely many graphs with an identifying code of size logarithmic in the number of vertices, while classes with finite VC-dimension have a polynomial lower bound. We then turn to approximation algorithms. We show that Min Id Code (the problem of finding a smallest identifying code in a given graph from some class $\mathcal{C}$) is log-APX-hard for any hereditary class of infinite VC-dimension. For hereditary classes of finite VC-dimension, the only known previous results show that we can approximate Min Id Code within a constant factor in some particular classes, e.g., line graphs, planar graphs, and unit interval graphs. We prove that Min Id Code can be approximate within a factor 6 for interval graphs. In contrast, we show that Min Id Code on $C_4$-free bipartite graphs (a class of finite VC-dimension) cannot be approximated to within a factor of $c \log(|V|)$ for some $c>0$.

Let $D$ be a digraph. The chromatic number $\chi(D)$ of $D$ is the smallest number of colors needed to color the vertices of $D$ such that every color class induces an acyclic subdigraph. The girth of $D$ is the length of a shortest directed cycle, or $\infty$ if $D$ is acyclic. Let $G(k,n)$ be the maximum possible girth of a digraph on $n$ vertices with $\chi(D) > k$. It is shown that $G(k,n) \ge \left\lfloor n^{1/k}\right\rfloor$ and $G(k,n) \le (3\log_2 n \log_2\log_2 n)^{1-1/k} n^{1/k}$ for $n \ge 3$ and $k \ge 2$.

We study the following graph partitioning problem: Given two positive integers C and $\Delta$, find the least integer $M(C,\Delta)$ such that the edges of any graph with maximum degree at most $\Delta$ can be partitioned into subgraphs with at most C edges and each vertex appears in at most $M(C,\Delta)$ subgraphs. This problem is naturally motivated by traffic grooming, which is a major issue in optical networks. Namely, we introduce a new pseudodynamic model of traffic grooming in unidirectional rings, in which the aim is to design a network able to support any request graph with a given bounded degree. We show that optimizing the equipment cost under this model is essentially equivalent to determining the parameter $M(C,\Delta)$. We establish the value of $M(C,\Delta)$ for almost all values of C and $\Delta$, leaving open only the case where $\Delta \geq 5$ is odd, $\Delta \pmod{2C}$ is between 3 and $C-1$, $C\geq 4$, and the request graph does not contain a perfect matching. For these open cases, we provide upper bounds that differ from the optimal value by at most one.

A totally odd K4-subdivision is a subdivision of K4 where each subdivided edge has odd length. The recognition of a totally odd K4-subdivision plays an important role in both graph theory and combinatorial optimization. Sewell and Trotter [53], Zang [63] and Thomassen [60] independently conjectured the existence of a polynomial time recognition algorithm. In this paper, we give the first polynomial time algorithm for solving this problem. We also study the the parity two disjoint rooted paths problem where we determine if there exists two vertex disjoint paths of a specified parity between two pairs of terminals. Using a similar technique, we give an O(|E(G)||V(G)|α(|E(G)|,|V(G)|)) algorithm for the parity two disjoint rooted paths problem on an input graph G, where α(|E(G)|,|V(G)|) is the inverse of the Ackermann function. We note that this clearly gives an algorithm for the well-known non-parity version of the two disjoint rooted paths problem [19, 50, 52, 55, 58]. We then extend our approach to give a polynomial time algorithm which determines, for any fixed k, whether there exists a cycle of a given parity through k independent input edges. This generalizes the non-parity version of the algorithm in [22]. Thomassen [61] gave a polynomial algorithm for the case k = 2 and hoped to use this algorithm to recognize a totally odd K4-subdivision. Our algorithm runs in O(|E(G)||V(G)|α(|E(G)|, |V(G)|)) for any fixed k. Finally, we give an O(|V(G)|2 + |E(G)|α(|E(G)|,|V(G)|log|V(G)|)) algorithm to decide whether a graph contains k disjoint paths from A to B (with |A| = |B| = k) that are not all of the same parity. This answers a conjecture of Thomassen [60]. This problem arises from the study of totally odd-K4-subdivisions in 3-connected graphs [60].

To overcome the problems of traditional delay models, this paper uses a circuit simulator to calculate gate delay in static timing analysis. We analyzed the effect of multiple inputs simultaneous switching(MISS) on gate delay and proposed a MISS model to calculate the worst case gate delay. Based on this model, we developed the test waveform generation algorithms for complementary CMOS logic and pass transistor logic. By combining gate delay simulation with functional model extraction techniques of transistor circuits, we implemented a transistor level static timing analysis tool called SpiceTime. Results on ten IS-CAS85 benchmark circuits indicated that modules of significant size can be verified by SpiceTime with high precisions.