On greene's theorem for digraphs

Greene's Theorem states that the maximum cardinality of an optimal k-path in a poset is equal to the minimum k-norm of a k-optimal coloring. This result was extended to all acyclic digraphs, and is conjectured to hold for general digraphs. We prove the result for general digraphs in which an optimal k-path contains a path of cardinality one. This implies the validity of the conjecture for all bipartite digraphs. We also extend Greene's Theorem to all split graphs.     

List coloring digraphs

The dichromatic number of a digraph D is the least number k such that the vertex set of D can be partitioned into k parts each of which induces an acyclic subdigraph. Introduced by Neumann‐Lara in 1982, this digraph invariant shares many properties with the usual chromatic number of graphs and can be seen as the natural analog of the graph chromatic number. In this article, we study the list dichromatic number of digraphs, giving evidence that this notion generalizes the list chromatic number of graphs. We first prove that the list dichromatic number and the dichromatic number behave the same in many contexts, such as in small digraphs (by proving a directed version of Ohba's conjecture), tournaments, and random digraphs. We then consider bipartite digraphs, and show that their list dichromatic number can be as large as . We finally give a Brooks‐type upper bound on the list dichromatic number of digon‐free digraphs.     

Disjoint Paths in Decomposable Digraphs

The k‐linkage problem is as follows: given a digraph and a collection of k terminal pairs such that all these vertices are distinct; decide whether D has a collection of vertex disjoint paths such that is from to for . A digraph is k‐linked if it has a k‐linkage for every choice of 2k distinct vertices and every choice of k pairs as above. The k‐linkage problem is NP‐complete already for [11] and there exists no function such that every ‐strong digraph has a k‐linkage for every choice of 2k distinct vertices of D [17]. Recently, Chudnovsky et al. [9] gave a polynomial algorithm for the k‐linkage problem for any fixed k in (a generalization of) semicomplete multipartite digraphs. In this article, we use their result as well as the classical polynomial algorithm for the case of acyclic digraphs by Fortune et al. [11] to develop polynomial algorithms for the k‐linkage problem in locally semicomplete digraphs and several classes of decomposable digraphs, including quasi‐transitive digraphs and directed cographs. We also prove that the necessary condition of being ‐strong is also sufficient for round‐decomposable digraphs to be k‐linked, obtaining thus a best possible bound that improves a previous one of . Finally we settle a conjecture from [3] by proving that every 5‐strong locally semicomplete digraph is 2‐linked. This bound is also best possible (already for tournaments) [1].     

Improved Upper Bounds for Gallai–Ramsey Numbers of Paths and Cycles

Given a graph G and a positive integer k, define the Gallai–Ramsey number to be the minimum number of vertices n such that any k‐edge coloring of contains either a rainbow (all different colored) triangle or a monochromatic copy of G. In this work, we improve upon known upper bounds on the Gallai–Ramsey numbers for paths and cycles. All these upper bounds now have the best possible order of magnitude as functions of k.     

The gallai-younger conjecture for planar graphs

Younger conjectured that for everyk there is ag(k) such that any digraphG withoutk vertex disjoint cycles contains a setX of at mostg(k) vertices such thatG–X has no directed cycles. Gallai had previously conjectured this result fork=1. We prove this conjecture for planar digraphs. Specifically, we show that ifG is a planar digraph withoutk vertex disjoint directed cycles, thenG contains a set of at mostO(klog(k)log(log(k))) vertices whose removal leaves an acyclic digraph. The work also suggests a conjecture concerning an extension of Vizing's Theorem for planar graphs.     

Acyclic Chromatic Indices of Planar Graphs with Girth At Least 4

An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index of G is the smallest integer k such that G has an acyclic edge coloring using k colors. Fiamik (Math. Slovaca 28 (1978), 139–145) and later Alon et al. (J Graph Theory 37 (2001), 157–167) conjectured that for any simple graph G with maximum degree Δ. In this article, we confirm this conjecture for planar graphs of girth at least 4.     

Clique minors in double‐critical graphs

A connected t‐chromatic graph G is double‐critical if is ‐colorable for each edge . A long‐standing conjecture of Erdős and Lovász that the complete graphs are the only double‐critical t‐chromatic graphs remains open for all . Given the difficulty in settling Erdős and Lovász's conjecture and motivated by the well‐known Hadwiger's conjecture, Kawarabayashi, Pedersen, and Toft proposed a weaker conjecture that every double‐critical t‐chromatic graph contains a minor and verified their conjecture for . Albar and Gonçalves recently proved that every double‐critical 8‐chromatic graph contains a K₈ minor, and their proof is computer assisted. In this article, we prove that every double‐critical t‐chromatic graph contains a minor for all . Our proof for is shorter and computer free.     

Completing orientations of partially oriented graphs

We initiate a general study of what we call orientation completion problems. For a fixed class of oriented graphs, the orientation completion problem asks whether a given partially oriented graph P can be completed to an oriented graph in by orienting the (nonoriented) edges in P. Orientation completion problems commonly generalize several existing problems including recognition of certain classes of graphs and digraphs as well as extending representations of certain geometrically representable graphs. We study orientation completion problems for various classes of oriented graphs, including k‐arc‐strong oriented graphs, k‐strong oriented graphs, quasi‐transitive‐oriented graphs, local tournaments, acyclic local tournaments, locally transitive tournaments, locally transitive local tournaments, in‐tournaments, and oriented graphs that have directed cycle factors. We show that the orientation completion problem for each of these classes is either polynomial time solvable or NP‐complete. We also show that some of the NP‐complete problems become polynomial time solvable when the input‐oriented graphs satisfy certain extra conditions. Our results imply that the representation extension problems for proper interval graphs and for proper circular arc graphs are polynomial time solvable. The latter generalizes a previous result.     

Hadwiger's Conjecture for the Complements of Kneser Graphs

Hadwiger's conjecture asserts that every graph with chromatic number t contains a complete minor of order t. Given integers , the Kneser graph is the graph with vertices the k‐subsets of an n‐set such that two vertices are adjacent if and only if the corresponding k‐subsets are disjoint. We prove that Hadwiger's conjecture is true for the complements of Kneser graphs.     

Decompositions of Graphs into Fans and Single Edges

Given two graphs G and H , an H‐decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms a graph isomorphic to H . Let be the smallest number ? such that any graph G of order n admits an H‐decomposition with at most ? parts. Pikhurko and Sousa conjectured that for and all sufficiently large n , where denotes the maximum number of edges in a graph on n vertices not containing H as a subgraph. Their conjecture has been verified by Özkahya and Person for all edge‐critical graphs H . In this article, the conjecture is verified for the k‐fan graph. The k‐fan graph , denoted by , is the graph on vertices consisting of k triangles that intersect in exactly one common vertex called the center of the k‐fan.     

On a Problem of Judicious k‐Partitions of Graphs

For positive integers and m , let be the smallest integer such that for each graph G with m edges there exists a k‐partition in which each contains at most edges. Bollobás and Scott showed that . Ma and Yu posed the following problem: is it true that the limsup of tends to infinity as m tends to infinity? They showed it holds when k is even, establishing a conjecture of Bollobás and Scott. In this article, we solve the problem completely. We also present a result by showing that every graph with a large k‐cut has a k‐partition in which each vertex class contains relatively few edges, which partly improves a result given by Bollobás and Scott.     

Equitable List Coloring of Graphs with Bounded Degree

A graph G is equitably k‐choosable if for every k‐list assignment L there exists an L‐coloring of G such that every color class has at most vertices. We prove results toward the conjecture that every graph with maximum degree at most r is equitably ‐choosable. In particular, we confirm the conjecture for and show that every graph with maximum degree at most r and at least r³ vertices is equitably ‐choosable. Our proofs yield polynomial algorithms for corresponding equitable list colorings.     

Acyclic List Edge Coloring of Graphs

A proper edge coloring of a graph is said to be acyclic if any cycle is colored with at least three colors. An edge-list L of a graph G is a mapping that assigns a finite set of positive integers to each edge of G. An acyclic edge coloring ? of G such that for any is called an acyclic L-edge coloring of G. A graph G is said to be acyclically k-edge choosable if it has an acyclic L‐edge coloring for any edge‐list L that satisfies for each edge e. The acyclic list chromatic index is the least integer k such that G is acyclically k‐edge choosable. We develop techniques to obtain bounds for the acyclic list chromatic indices of outerplanar graphs, subcubic graphs, and subdivisions of Halin graphs.     

Extensions of Gallai–Ramsey results

Consider the graph consisting of a triangle with a pendant edge. We describe the structure of rainbow ‐free edge colorings of a complete graph and provide some corresponding Gallai–Ramsey results. In particular, we extend a result of Gallai to find a partition of the vertices of a rainbow ‐free colored complete graph with a limited number of colors between the parts. We also extend some Gallai–Ramsey results of Chung and Graham, Faudree et al. and Gyárfás et al. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory     

On the Density of Transitive Tournaments

We prove that for every fixed k, the number of occurrences of the transitive tournament Tr_k of order k in a tournament  on n vertices is asymptotically minimized when  is random. In the opposite direction, we show that any sequence of tournaments  achieving this minimum for any fixed  is necessarily quasirandom. We present several other characterizations of quasirandom tournaments nicely complementing previously known results and relatively easily following from our proof techniques.     

Arc‐Disjoint Directed and Undirected Cycles in Digraphs

The dicycle transversal number of a digraph D is the minimum size of a dicycle transversal of D, that is a set of vertices of D, whose removal from D makes it acyclic. An arc a of a digraph D with at least one cycle is a transversal arc if a is in every directed cycle of D (making acyclic). In [3] and [4], we completely characterized the complexity of following problem: Given a digraph D, decide if there is a dicycle B in D and a cycle C in its underlying undirected graph such that . It turns out that the problem is polynomially solvable for digraphs with a constantly bounded number of transversal vertices (including cases where ). In the remaining case (allowing arbitrarily many transversal vertices) the problem is NP‐complete. In this article, we classify the complexity of the arc‐analog of this problem, where we ask for a dicycle B and a cycle C that are arc‐disjoint, but not necessarily vertex‐disjoint. We prove that the problem is polynomially solvable for strong digraphs and for digraphs with a constantly bounded number of transversal arcs (but possibly an unbounded number of transversal vertices). In the remaining case (allowing arbitrarily many transversal arcs) the problem is NP‐complete.     

Plane Graphs with Maximum Degree Are Entirely ‐Colorable

Let be a plane graph with the sets of vertices, edges, and faces V, E, and F, respectively. If one can color all elements in using k colors so that any two adjacent or incident elements receive distinct colors, then G is said to be entirely k‐colorable. Kronk and Mitchem [Discrete Math 5 (1973) 253‐260] conjectured that every plane graph with maximum degree Δ is entirely ‐colorable. This conjecture has now been settled in Wang and Zhu (J Combin Theory Ser B 101 (2011) 490–501), where the authors asked: is every simple plane graph entirely ‐colorable? In this article, we prove that every simple plane graph with is entirely ‐colorable, and conjecture that every simple plane graph, except the tetrahedron, is entirely ‐colorable.     

On a Conjecture of Erdős,Gallai, and Tuza

Erd?s, Gallai, and Tuza posed the following problem: given an n‐vertex graph G, let denote the smallest size of a set of edges whose deletion makes G triangle‐free, and let denote the largest size of a set of edges containing at most one edge from each triangle of G. Is it always the case that ? We have two main results. We first obtain the upper bound , as a partial result toward the Erd?s–Gallai–Tuza conjecture. We also show that always , where m is the number of edges in G; this bound is sharp in several notable cases.     

Partitioning a Graph into Highly Connected Subgraphs

Given , a k‐proper partition of a graph G is a partition of such that each part P of induces a k‐connected subgraph of G. We prove that if G is a graph of order n such that , then G has a 2‐proper partition with at most parts. The bounds on the number of parts and the minimum degree are both best possible. We then prove that if G is a graph of order n with minimum degree where , then G has a k‐proper partition into at most parts. This improves a result of Ferrara et al. ( Discrete Math 313 (2013), 760–764), and both the degree condition and the number of parts is best possible up to the constant c.     

Perfect Digraphs

The clique number of a digraph D is the size of the largest bidirectionally complete subdigraph of D. D is perfect if, for any induced subdigraph H of D, the dichromatic number defined by Neumann‐Lara (The dichromatic number of a digraph, J. Combin. Theory Ser. B 33 (1982), 265–270) equals the clique number . Using the Strong Perfect Graph Theorem (M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, The strong perfect graph theorem, Ann. Math. 164 (2006), 51–229) we give a characterization of perfect digraphs by a set of forbidden induced subdigraphs. Modifying a recent proof of Bang‐Jensen et al. (Finding an induced subdivision of a digraph, Theoret. Comput. Sci. 443 (2012), 10–24) we show that the recognition of perfect digraphs is co‐‐complete. It turns out that perfect digraphs are exactly the complements of clique‐acyclic superorientations of perfect graphs. Thus, we obtain as a corollary that complements of perfect digraphs have a kernel, using a result of Boros and Gurvich (Perfect graphs are kernel solvable, Discrete Math. 159 (1996), 35–55). Finally, we prove that it is ‐complete to decide whether a perfect digraph has a kernel.