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.     

The circular chromatic number of a digraph

We introduce the circular chromatic number χ_c of a digraph and establish various basic results. They show that the coloring theory for digraphs is similar to the coloring theory for undirected graphs when independent sets of vertices are replaced by acyclic sets. Since the directed k‐cycle has circular chromatic number k/(k – 1), for k ≥ 2, values of χ_c between 1 and 2 are possible. We show that in fact, χ_c takes on all rational values greater than 1. Furthermore, there exist digraphs of arbitrarily large digirth and circular chromatic number. It is NP‐complete to decide if a given digraph has χ_c at most 2. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 227–240, 2004     

On directed local chromatic number,shift graphs,and Borsuk‐like graphs

We investigate the local chromatic number of shift graphs and prove that it is close to their chromatic number. This implies that the gap between the directed local chromatic number of an oriented graph and the local chromatic number of the underlying undirected graph can be arbitrarily large. We also investigate the minimum possible directed local chromatic number of oriented versions of “topologically t‐chromatic” graphs. We show that this minimum for large enough t‐chromatic Schrijver graphs and t‐chromatic generalized Mycielski graphs of appropriate parameters is ?t/4?+1. © 2010 Wiley Periodicals, Inc. J Graph Theory 66: 65‐82, 2010     

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 .     

A Characterization of b‐Perfect Graphs

A b‐coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbor in all other color classes, and 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 of G. We prove that a graph is b‐perfect if and only if it does not contain as an induced subgraph a member of a certain list of 22 graphs. This entails the existence of a polynomial‐time recognition algorithm and of a polynomial‐time algorithm for coloring exactly the vertices of every b‐perfect graph. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:95–122, 2012     

Weak Borel chromatic numbers

Given a graph G whose set of vertices is a Polish space X, the weak Borel chromatic number of G is the least size of a family of pairwise disjoint G ‐independent Borel sets that covers all of X. Here a set of vertices of a graph G is independent if no two vertices in the set are connected by an edge. We show that it is consistent with an arbitrarily large size of the continuum that every closed graph on a Polish space either has a perfect clique or has a weak Borel chromatic number of at most ?₁. We observe that some weak version of Todorcevic's Open Coloring Axiom for closed colorings follows from MA. Slightly weaker results hold for F_σ‐graphs. In particular, it is consistent with an arbitrarily large size of the continuum that every locally countable F_σ‐graph has a Borel chromatic number of at most ?₁. We refute various reasonable generalizations of these results to hypergraphs (© 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

The circular chromatic numbers of planar digraphs

The circular chromatic number is a refinement of the chromatic number of a graph. It has been established in [3,6,7] that there exists planar graphs with circular chromatic number r if and only if r is a rational in the set {1} ∪ [2,4]. Recently, Mohar, in [1,2] has extended the concept of the circular chromatic number to digraphs and it is interesting to ask what the corresponding result is for digraphs. In this article, we shall prove the new result that there exist planar digraphs with circular chromatic number r if and only if r is a rational in the interval [1,4]. © 2006 Wiley Periodicals, Inc. J Graph Theory 55: 14–26, 2007     

Relations between the Local Chromatic Number and Its Directed Version

The local chromatic number is a coloring parameter defined as the minimum number of colors that should appear in the most colorful closed neighborhood of a vertex under any proper coloring of the graph. Its directed version is the same when we consider only outneighborhoods in a directed graph. For digraphs with all arcs being present in both directions the two values are obviously equal. Here, we consider oriented graphs. We show the existence of a graph where the directed local chromatic number of all oriented versions of the graph is strictly less than the local chromatic number of the underlying undirected graph. We show that for fractional versions the analogous problem has a different answer: there always exists an orientation for which the directed and undirected values coincide. We also determine the supremum of the possible ratios of these fractional parameters, which turns out to be e, the basis of the natural logarithm.     

χ‐bounded families of oriented graphs

A famous conjecture of Gyárfás and Sumner states for any tree T and integer k, if the chromatic number of a graph is large enough, either the graph contains a clique of size k or it contains T as an induced subgraph. We discuss some results and open problems about extensions of this conjecture to oriented graphs. We conjecture that for every oriented star S and integer k, if the chromatic number of a digraph is large enough, either the digraph contains a clique of size k or it contains S as an induced subgraph. As an evidence, we prove that for any oriented star S, every oriented graph with sufficiently large chromatic number contains either a transitive tournament of order 3 or S as an induced subdigraph. We then study for which sets of orientations of P₄ (the path on four vertices) similar statements hold. We establish some positive and negative results.     

On Beck’s coloring of posets

We study Beck-like coloring of partially ordered sets (posets) with a least element 0. To any poset P with 0 we assign a graph (called a zero-divisor graph) whose vertices are labelled by the elements of P with two vertices x,y adjacent if 0 is the only element lying below x and y. We prove that for such graphs, the chromatic number and the clique number coincide. Also, we give a condition under which posets are not finitely colorable.     

The Zerodivisor Graph of a Qoset

We study colorings of quasiordered sets (qosets) with a least element 0. To any qoset Q with 0 we assign a graph (called a zerodivisor graph) whose vertices are labelled by the elements of Q with two vertices x,y adjacent if the only elements lying below x and y are those lying below 0. We prove that for such graphs, the chromatic number and the clique number coincide.     

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 chromatic‐choosable graphs

A graph is chromatic‐choosable if its choice number coincides with its chromatic number. It is shown in this article that, for any graph G, if we join a sufficiently large complete graph to G, then we obtain a chromatic‐choosable graph. As a consequence, if the chromatic number of a graph G is close enough to the number of vertices in G, then G is chromatic‐choosable. We also propose a conjecture related to this fact. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 130–135, 2002     

Reinforcement numbers of digraphs

The reinforcement number of a graph G is the minimum cardinality of a set of extra edges whose addition results in a graph with domination number less than the domination number of G. In this paper we consider this parameter for digraphs, investigate the relationship between reinforcement numbers of undirected graphs and digraphs, and obtain further results for regular graphs. We also determine the exact values of the reinforcement numbers of de Bruijn digraphs and Kautz digraphs.     

Game-perfect graphs

A graph coloring game introduced by Bodlaender (Int J Found Comput Sci 2:133–147, 1991) as coloring construction game is the following. Two players, Alice and Bob, alternately color vertices of a given graph G with a color from a given color set C, so that adjacent vertices receive distinct colors. Alice has the first move. The game ends if no move is possible any more. Alice wins if every vertex of G is colored at the end, otherwise Bob wins. We consider two variants of Bodlaender’s graph coloring game: one (A) in which Alice has the right to have the first move and to miss a turn, the other (B) in which Bob has these rights. These games define the A-game chromatic number resp. the B-game chromatic number of a graph. For such a variant g, a graph G is g-perfect if, for every induced subgraph H of G, the clique number of H equals the g-game chromatic number of H. We determine those graphs for which the game chromatic numbers are 2 and prove that the triangle-free B-perfect graphs are exactly the forests of stars, and the triangle-free A-perfect graphs are exactly the graphs each component of which is a complete bipartite graph or a complete bipartite graph minus one edge or a singleton. From these results we may easily derive the set of triangle-free game-perfect graphs with respect to Bodlaender’s original game. We also determine the B-perfect graphs with clique number 3. As a general result we prove that complements of bipartite graphs are A-perfect.      

6‐Star‐Coloring of Subcubic Graphs

A star coloring of an undirected graph G is a proper vertex coloring of G (i.e., no two adjacent vertices are assigned the same color) such that no path on four vertices is 2‐colored. The star chromatic number of G is the smallest integer k for which G admits a star coloring with k colors. In this paper, we prove that every subcubic graph is 6‐star‐colorable. Moreover, the upper bound 6 is best possible, based on the example constructed by Fertin, Raspaud, and Reed (J Graph Theory 47(3) (2004), 140–153).     

A new upper bound for the harmonious chromatic number

A harmonious coloring of a simple graph G is a proper vertex coloring such that each pair of colors appears together on at most one edge. The harmonious chromatic number h(G) is the least number of colors in such a coloring. We obtain a new upper bound for the harmonious chromatic number of general graphs. © 1998 John Wiley & Sons, Inc. J Graph Theory 29: 257–261, 1998     

Counting strongly‐connected,moderately sparse directed graphs

A sharp asymptotic formula for the number of strongly connected digraphs on n labelled vertices with m arcs, under the condition m ‐ n ? n^2/3, m = O(n), is obtained; this provides a partial solution of a problem posed by Wright back in 1977. This formula is a counterpart of a classic asymptotic formula, due to Bender, Canfield and McKay, for the total number of connected undirected graphs on n vertices with m edges. A key ingredient of their proof was a recurrence equation for the connected graphs count due to Wright. No analogue of Wright's recurrence seems to exist for digraphs. In a previous paper with Nick Wormald we rederived the BCM formula by counting first connected graphs among the graphs of minimum degree 2, at least. In this paper, using a similar embedding for directed graphs, we find an asymptotic formula, which includes an explicit error term, for the fraction of strongly‐connected digraphs with parameters m and n among all such digraphs with positive in/out‐degrees. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Enumeration of Full Graphs: Onset of the Asymptotic Region

A full graph on n vertices, as defined by Fulkerson, is a representation of the intersection and containment relations among a system of n sets. It has an undirected edge between vertices representing intersecting sets and a directed edge from a to b if the corresponding set A contains B;. Kleitman, Lasaga, and Cowen gave a unified argument to show that asymptotically, almost all full graphs can be obtained by taking an arbitrary undirected graph on the n vertices, distinguishing a clique in this graph, which need not be maximal, and then adding directed edges going out from each vertex in the clique to all vertices to which there is not already an existing undirected edge. Call graphs of this type members of the dominant class. This article obtains the first upper and lower bounds on how large n has to be, so that the asymptotic behavior is indeed observed. It is shown that when n > 170, the dominant class predominates, while when n < 17, the full graphs in the dominant class compose less than half of the total number of realizable full graphs on n vertices.     

The dichromatic number of a digraph

In this paper the concept of dichromatic number of a digraph which is a generalization of the chromatic number of a graph is introduced. The dichromatic number of a digraph D is defined as the minimum number of colours required to colour the vertices of D in such a way that the chromatic classes induce acyclic subdigraphs in D. Some results relating the dichromatic number of D with the existence of cycles of special lengths in D are presented. Contributions to chromatic theory are also obtained. In particular, we generalize the theorem due to P. Erdös and A. Hajnal (Acta Math. Acad. Sci. Hungar.17 (1966), 61–99) which states the existence of odd cycles of length ≥_χ(G) ? 1 in any graph G.