Outerplanar and Planar Oriented Cliques

The clique number of an undirected graph G is the maximum order of a complete subgraph of G and is a well‐known lower bound for the chromatic number of G. Every proper k‐coloring of G may be viewed as a homomorphism (an edge‐preserving vertex mapping) of G to the complete graph of order k. By considering homomorphisms of oriented graphs (digraphs without cycles of length at most 2), we get a natural notion of (oriented) colorings and oriented chromatic number of oriented graphs. An oriented clique is then an oriented graph whose number of vertices and oriented chromatic number coincide. However, the structure of oriented cliques is much less understood than in the undirected case. In this article, we study the structure of outerplanar and planar oriented cliques. We first provide a list of 11 graphs and prove that an outerplanar graph can be oriented as an oriented clique if and only if it contains one of these graphs as a spanning subgraph. Klostermeyer and MacGillivray conjectured that the order of a planar oriented clique is at most 15, which was later proved by Sen. We show that any planar oriented clique on 15 vertices must contain a particular oriented graph as a spanning subgraph, thus reproving the above conjecture. We also provide tight upper bounds for the order of planar oriented cliques of girth k for all .     

The Erdös–Hajnal Conjecture—A Survey

The Erdös–Hajnal conjecture states that for every graph H, there exists a constant such that every graph G with no induced subgraph isomorphic to H has either a clique or a stable set of size at least . This article is a survey of some of the known results on this conjecture.     

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.     

Induced subgraphs of graphs with large chromatic number. XII. Distant stars

The Gyárfás-Sumner conjecture asserts that if is a tree then every graph with bounded clique number and very large chromatic number contains as an induced subgraph. This is still open, although it has been proved for a few simple families of trees, including trees of radius two, some special trees of radius three, and subdivided stars. These trees all have the property that their vertices of degree more than two are clustered quite closely together. In this paper, we prove the conjecture for two families of trees which do not have this restriction. As special cases, these families contain all double-ended brooms and two-legged caterpillars.     

Coloring (gem, co‐gem)‐free graphs

A gem is a graph that consists of a path on four vertices plus a vertex adjacent to all four vertices of the path. A co‐gem is the complement of a gem. We prove that every (gem, co‐gem)‐free graph G satisfies the inequality (a special case of a conjecture of Gyárfás) and the inequality (a special case of a conjecture of Reed). Moreover, we give an ‐time algorithm that computes the chromatic number of any (gem, co‐gem)‐free graph with n vertices, while the existing algorithm in the literature takes .     

Large Subgraphs in Rainbow‐Triangle Free Colorings

Fox–Grinshpun–Pach showed that every 3‐coloring of the complete graph on n vertices without a rainbow triangle contains a clique of size that uses at most two colors, and this bound is tight up to the constant factor. We show that if instead of looking for large cliques one only tries to find subgraphs of large chromatic number, one can do much better. We show that every such coloring contains a 2‐colored subgraph with chromatic number at least , and this is best possible. We further show that for fixed positive integers with , every r‐coloring of the edges of the complete graph on n vertices without a rainbow triangle contains a subgraph that uses at most s colors and has chromatic number at least , and this is best possible. Fox–Grinshpun–Pach previously showed a clique version of this result. As a direct corollary of our result we obtain a generalization of the celebrated theorem of Erd?s‐Szekeres, which states that any sequence of n numbers contains a monotone subsequence of length at least . We prove that if an r‐coloring of the edges of an n‐vertex tournament does not contain a rainbow triangle then there is an s‐colored directed path on vertices, which is best possible. This gives a partial answer to a question of Loh.     

Perfect Graphs with No Balanced Skew‐Partition are 2‐Clique‐Colorable

A graph G is perfect if for all induced subgraphs H of G, . A graph G is Berge if neither G nor its complement contains an induced odd cycle of length at least five. The Strong Perfect Graph Theorem [9] states that a graph is perfect if and only if it is Berge. The Strong Perfect Graph Theorem was obtained as a consequence of a decomposition theorem for Berge graphs [M. Chudnovsky, Berge trigraphs and their applications, PhD thesis, Princeton University, 2003; M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, The strong perfect graph theorem, Ann Math 164 (2006), 51–229.], and one of the decompositions in this decomposition theorem was the “balanced skew‐partition.” A clique‐coloring of a graph G is an assignment of colors to the vertices of G in such a way that no inclusion‐wise maximal clique of G of size at least two is monochromatic, and the clique‐chromatic number of G, denoted by , is the smallest number of colors needed to clique‐color G. There exist graphs of arbitrarily large clique‐chromatic number, but it is not known whether the clique‐chromatic number of perfect graphs is bounded. In this article, we prove that every perfect graph that does not admit a balanced skew‐partition is 2‐clique colorable. The main tool used in the proof is a decomposition theorem for “tame Berge trigraphs” due to Chudnovsky et al. ( http://arxiv.org/abs/1308.6444 ).     

Extremal graphs for the k‐flower

The Turán number of a graph H, , is the maximum number of edges in any graph of order n that does not contain an H as a subgraph. A graph on vertices consisting of k triangles that intersect in exactly one common vertex is called a k‐fan, and a graph consisting of k cycles that intersect in exactly one common vertex is called a k‐flower. In this article, we determine the Turán number of any k‐flower containing at least one odd cycle and characterize all extremal graphs provided n is sufficiently large. Erdős, Füredi, Gould, and Gunderson determined the Turán number for the k‐fan. Our result is a generalization of their result. The addition aim of this article is to draw attention to a powerful tool, the so‐called progressive induction lemma of Simonovits.     

Cycles with two blocks in k‐chromatic digraphs

Let k and ℓ be positive integers. A cycle with two blocks is a digraph obtained by an orientation of an undirected cycle, which consists of two internally (vertex) disjoint paths of lengths at least k and ℓ, respectively, from a vertex to another one. A problem of Addario‐Berry, Havet and Thomassé [J. Combin. Theory Ser. B 97 (2007), 620–626] asked if, given positive integers k and ℓ such that , any strongly connected digraph D containing no has chromatic number at most . In this article, we show that such digraph D has chromatic number at most , improving the previous upper bound of Cohen et al. [Subdivisions of oriented cycles in digraphs with large chromatic number, to appear]. We also show that if in addition D is Hamiltonian, then its underlying simple graph is ‐degenerate and thus the chromatic number of D is at most , which is tight.     

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.     

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.     

Local Clique Covering of Claw‐Free Graphs

A clique covering of a simple graph G is a collection of cliques of G covering all the edges of G such that each vertex is contained in at most k cliques. The smallest k for which G admits a clique covering is called the local clique cover number of G and is denoted by lcc(G). Local clique cover number can be viewed as the local counterpart of the clique cover number that is equal to the minimum total number of cliques covering all edges. In this article, several aspects of the local clique covering problem are studied and its relationships to other well‐known problems are discussed. In particular, it is proved that the local clique cover number of every claw‐free graph is at most , where Δ is the maximum degree of the graph and c is a constant. It is also shown that the bound is tight, up to a constant factor. Moreover, regarding a conjecture by Chen et al. (Clique covering the edges of a locally cobipartite graph, Discrete Math 219(1–3)(2000), 17–26), we prove that the clique cover number of every connected claw‐free graph on n vertices with the minimum degree δ, is at most , where c is a constant.     

On the Roots of σ‐Polynomials

Given a graph G of order n, the σ‐polynomial of G is the generating function where is the number of partitions of the vertex set of G into i nonempty independent sets. Such polynomials arise in a natural way from chromatic polynomials. Brenti (Trans Am Math Soc 332 (1992), 729–756) proved that σ‐polynomials of graphs with chromatic number at least had all real roots, and conjectured the same held for chromatic number . We affirm this conjecture.     

Hadwiger's Conjecture for ℓ‐Link Graphs

In this article, we define and study a new family of graphs that generalizes the notions of line graphs and path graphs. Let G be a graph with no loops but possibly with parallel edges. An ?‐link of G is a walk of G of length in which consecutive edges are different. The ?‐link graph of G is the graph with vertices the ?‐links of G , such that two vertices are joined by edges in if they correspond to two subsequences of each of μ ‐links of G . By revealing a recursive structure, we bound from above the chromatic number of ?‐link graphs. As a corollary, for a given graph G and large enough ?, is 3‐colorable. By investigating the shunting of ?‐links in G , we show that the Hadwiger number of a nonempty is greater or equal to that of G . Hadwiger's conjecture states that the Hadwiger number of a graph is at least the chromatic number of that graph. The conjecture has been proved by Reed and Seymour (Eur J Combin 25(6) (2004), 873–876) for line graphs, and hence 1‐link graphs. We prove the conjecture for a wide class of ?‐link graphs.     

Upper Bounds for Erdös–Hajnal Coefficients of Tournaments

A celebrated unresolved conjecture of Erdös and Hajnal (see Discrete Appl Math 25 (1989), 37–52) states that for every undirected graph H, there exists , such that every graph on n vertices which does not contain H as an induced subgraph contains either a clique or an independent set of size at least . In (Combinatorica (2001), 155–170), Alon et al. proved that this conjecture was equivalent to a similar conjecture about tournaments. In the directed version of the conjecture cliques and stable sets are replaced by transitive subtournaments. For a fixed undirected graph H, define to be the supremum of all ε for which the following holds: for some n₀ and every every undirected graph with vertices not containing H as an induced subgraph has a clique or independent set of size at least . The analogous definition holds if H is a tournament. We call the Erdös–Hajnal coefficient of H. The Erdös–Hajnal conjecture is true if and only if for every H. We prove in this article that:

• the Erdös–Hajnal coefficient of every graph H is at most ,
• there exists such that the Erdös–Hajnal coefficient of almost every tournament T on k vertices is at most , i.e. the proportion of tournaments on k vertices with the coefficient exceeding goes to 0 as k goes to infinity.

     

On Toughness and Hamiltonicity of 2K2‐Free Graphs

The toughness of a (noncomplete) graph G is the minimum value of t for which there is a vertex cut A whose removal yields components. Determining toughness is an NP‐hard problem for general input graphs. The toughness conjecture of Chvátal, which states that there exists a constant t such that every graph on at least three vertices with toughness at least t is hamiltonian, is still open for general graphs. We extend some known toughness results for split graphs to the more general class of 2K₂‐free graphs, that is, graphs that do not contain two vertex‐disjoint edges as an induced subgraph. We prove that the problem of determining toughness is polynomially solvable and that Chvátal's toughness conjecture is true for 2K₂‐free graphs.     

Disjoint 3‐Cycles in Tournaments: A Proof of The Bermond–Thomassen Conjecture for Tournaments

We prove that every tournament with minimum out‐degree at least contains k disjoint 3‐cycles. This provides additional support for the conjecture by Bermond and Thomassen that every digraph D of minimum out‐degree contains k vertex disjoint cycles. We also prove that for every , when k is large enough, every tournament with minimum out‐degree at least contains k disjoint cycles. The linear factor 1.5 is best possible as shown by the regular tournaments.     

On minimally b-imperfect graphs

A b-coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbour in all other color classes. The b-chromatic number of a graph G is the largest integer k such that G admits a b-coloring with k colors. A graph is b-perfect if the b-chromatic number is equal to the chromatic number for every induced subgraph H of G. A graph is minimally b-imperfect if it is not b-perfect and every proper induced subgraph is b-perfect. We give a list of minimally b-imperfect graphs, conjecture that a graph is b-perfect if and only if it does not contain a graph from this list as an induced subgraph, and prove this conjecture for diamond-free graphs, and graphs with chromatic number at most three.     

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.     

Constructing a Family of 4‐Critical Planar Graphs with High Edge Density

A graph is a k‐critical graph if G is not ‐colorable but every proper subgraph of G is ‐colorable. In this article, we construct a family of 4‐critical planar graphs with n vertices and edges. As a consequence, this improves the bound for the maximum edge density attained by Abbott and Zhou. We conjecture that this is the largest edge density for a 4‐critical planar graph.