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.

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 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.

Abstract A graph G is a grid intersection graph if G is the intersection graph of ℋ︁ ∪ ℐ, where ℋ︁ and ℐ are, respectively, finite families of horizontal and vertical linear segments in the plane such that no two parallel segments intersect. (This definition implies that every grid intersection graph is bipartite.) The family ℋ︁ ∪ ℐ is a representation of G. As a consequence of a characterization of grid intersection graphs by Kratochvíl, we observe that when a bipartite graph G = (U ∪ W, E) with minimum degree at least two is a grid intersection graph, then there exists a normalized representation of G on the (r × s)‐grid for r = |U| and s = |W|, that is, a representation in which all end points of segments have integer‐valued coordinates belonging to {(x, y) ∈ N × N | 1 ≤ y ≤ r, 1 ≤ x ≤ s} and the representative segment of each vertex lies on a distinct horizontal or vertical line. A natural problem, with potential applications to circuit layout, is the following: among all the possible normalized representations of G, find a representation ℛ such that the sum of the lengths of the segments in ℛ is minimum. In this work we introduce this problem and present a mixed integer programming formulation to solve it. © 2004 Wiley Periodicals, Inc. NETWORKS, Vol. 44(3), 187–193 2004

List partitions generalize list colorings and list homomorphisms. (We argue that they may be called list "semihomomorphisms.") Each symmetric matrix M over 0,1,* defines a list partition problem. Different choices of the matrix M lead to many well-known graph theoretic problems, often related to graph perfection, including the problem of recognizing split graphs, finding homogeneous sets, clique cutsets, stable cutsets, and so on. The recent proof of the strong perfect graph theorem employs three kinds of decompositions that can be viewed as list partitions. We develop tools which allow us to classify the complexity of many list partition problems and, in particular, yield the complete classification for small matrices M. Along the way, we obtain a variety of specific results, including generalizations of Lovász's communication bound on the number of clique-versus-stable-set separators, polynomial time algorithms to recognize generalized split graphs, a polynomial algorithm for the list version of the clique cutset problem, and the first subexponential algorithm for the skew cutset problem of Chvátal. We also show that the dichotomy (NP-complete versus polynomial time solvable), conjectured for certain graph homomorphism problems, would, if true, imply a slightly weaker dichotomy (NP-complete versus quasi-polynomial) for our list partition problems.

We introduce a parametrized family of graph problems that includes several well-known graph partition problems as special czses.We develop tools which allow us to classify the complexity of many problems in this family, and in particular lead us to a complete classification for small values of the parameters.Along the way, we obtain a variety of specific results including the following: a generalization of a communication bound on the number of clique-versus-independentset separators; polynomial-time algorithms to recognize generalized split graphs; and, a quasi-polynomial algorithm for the Skew Cutset Problem that essentially resolves an open problem posed by Chv&tal.The last two problems have interesting connections to the Strong Perfect Graph Conjecture of Berge.We also observe that the dichotomy (NPcomplete versus polynomial-time solvable) conjectured for certain graph homomorphism problems, would, if true, imply a slightly weaker dichotomy (NP-complete versus quasipolynomial) for our graph partition problems.