Partitions of Graphs into Cographs

Cographs from the minimal family of graphs containing K₁ which are closed with respect to complements and unions. We discuss vertex partitions of graphs into the smallest number of cographs, where the partition is as small as possible. We shall call the order of such a partition the c-chromatic number of the graph. We begin by axiomatizing several well-known graphical parameters as motivation for this function. We present several bounds on c-chromatic number in terms of well-known expressions. We show that if a graph is triangle-free, then its chromatic number is bounded between the c-chromatic number and twice this number. We show both bounds are sharp, for graphs with arbitrarily high girth. This provides an alternative proof to a result in [3]; there exist triangle-free graphs with arbitrarily large c-chromatic numbers. We show that any planar graph with girth at least 11 has a c-chromatic number of at most two. We close with several remarks on computational complexity. In particular, we show that computing the c-chromatic number is NP-complete for planar graphs.     

Inequalities for the Grundy chromatic number of graphs

The Grundy (or First-Fit) chromatic number of a graph G is the maximum number of colors used by the First-Fit coloring of the graph G. In this paper we give upper bounds for the Grundy number of graphs in terms of vertex degrees, girth, clique partition number and for the line graphs. Next we show that if the Grundy number of a graph is large enough then the graph contains a subgraph of prescribed large girth and Grundy number.     

Chromatic number of sparse colored mixed planar graphs

A colored mixed graph has vertices linked by both colored arcs and colored edges. The chromatic number of such a graph G is defined as the smallest order of a colored mixed graph H such that there exists a (arc-color preserving) homomorphism from G to H. We study in this paper the colored mixed chromatic number of planar graphs, partial 2-trees and outerplanar graphs with given girth.     

Oriented Coloring of Triangle-Free Planar Graphs and 2-Outerplanar Graphs

A graph is planar if it can be embedded on the plane without edge-crossings. A graph is 2-outerplanar if it has a planar embedding such that the subgraph obtained by removing the vertices of the external face is outerplanar (i.e. with all its vertices on the external face). An oriented k-coloring of an oriented graph G is a homomorphism from G to an oriented graph H of order k. We prove that every oriented triangle-free planar graph has an oriented chromatic number at most 40, that improves the previous known bound of 47 [Borodin, O. V. and Ivanova, A. O., An oriented colouring of planar graphs with girth at least 4, Sib. Electron. Math. Reports, vol. 2, 239–249, 2005]. We also prove that every oriented 2-outerplanar graph has an oriented chromatic number at most 40, that improves the previous known bound of 67 [Esperet, L. and Ochem, P. Oriented colouring of 2-outerplanar graphs, Inform. Process. Lett., vol. 101(5), 215–219, 2007].     

Oriented coloring of triangle-free planar graphs and 2-outerplanar graphs

A graph is 2-outerplanar if it has a planar embedding such that the subgraph obtained by removing the vertices of the external face is outerplanar (i.e. with all its vertices on the external face). An oriented k-coloring of an oriented graph G is a homomorphism from G to an oriented graph H of order k. We prove that (1) every oriented triangle-free planar graph has an oriented chromatic number at most 40, and (2) every oriented 2-outerplanar graph has an oriented chromatic number at most 40, that improves the previous known bounds of 47 and 67, respectively.     

A study on oriented relative clique number

An oriented graph is a directed graph with no directed cycle of length one or two. The relative clique number of an oriented graph is the cardinality of a largest subset $X$ of vertices such that each pair of vertices is either adjacent or connected by a directed 2-path. It is known that the oriented relative clique number of a planar graph is at most 80. Here we improve the upper bound to 32. We also prove an upper bound of 14 for oriented relative clique number of triangle-free planar graphs. Furthermore, we determine the exact values of oriented relative clique number for the families of outerplanar graphs with girth at least $g$ and planar graphs with girth at least $g+2$ for all $g\ge 3$. Moreover, we study the relation of oriented relative clique number with oriented chromatic number, oriented absolute clique number and maximum degree of a graph. We also show that oriented relative clique number of a connected subcubic graph is at most seven which weakly supports a conjecture by Sopena (JGT 1997).     

Star chromatic numbers of graphs

We investigate the relation between the star-chromatic number (G) and the chromatic number (G) of a graphG. First we give a sufficient condition for graphs under which their starchromatic numbers are equal to their ordinary chromatic numbers. As a corollary we show that for any two positive integersk, g, there exists ak-chromatic graph of girth at leastg whose star-chromatic number is alsok. The special case of this corollary withg=4 answers a question of Abbott and Zhou. We also present an infinite family of triangle-free planar graphs whose star-chromatic number equals their chromatic number. We then study the star-chromatic number of An infinite family of graphs is constructed to show that for each >0 and eachm2 there is anm-connected (m+1)-critical graph with star chromatic number at mostm+. This answers another question asked by Abbott and Zhou.     

Circumference, chromatic number and online coloring

Erd?s conjectured that if G is a triangle free graph of chromatic number at least k≥3, then it contains an odd cycle of length at least k ^2?o(1) [13,15]. Nothing better than a linear bound ([3], Problem 5.1.55 in [16]) was so far known. We make progress on this conjecture by showing that G contains an odd cycle of length at least Ω(k log logk). Erd?s’ conjecture is known to hold for graphs with girth at least five. We show that if a graph with girth four is C ₅ free, then Erd?s’ conjecture holds. When the number of vertices is not too large we can prove better bounds on χ. We also give bounds on the chromatic number of graphs with at most r cycles of length 1 mod k, or at most s cycles of length 2 mod k, or no cycles of length 3 mod k. Our techniques essentially consist of using a depth first search tree to decompose the graph into ordered paths, which are then fed to an online coloring algorithm. Using this technique we give simple proofs of some old results, and also obtain several other results. We also obtain a lower bound on the number of colors which an online coloring algorithm needs to use to color triangle free graphs.     

Ollivier’s Ricci curvature and the coloring of graphs

We obtain lower bounds on the clique number and chromatic number for finite simple graphs using Ollivier’s Ricci curvature. Also we study the relations between girth and curvature. From these, we obtain curvature conditions for 3-colorability of a planar graph.     

Triangle-free graphs whose independence number equals the degree

In a triangle-free graph, the neighbourhood of every vertex is an independent set. We investigate the class S of triangle-free graphs where the neighbourhoods of vertices are maximum independent sets. Such a graph G must be regular of degree d=α(G) and the fractional chromatic number must satisfy χ_f(G)=|G|/α(G). We indicate that S is a rich family of graphs by determining the rational numbers c for which there is a graph G∈S with χ_f(G)=c except for a small gap, where we cannot prove the full statement. The statements for c≥3 are obtained by using, modifying, and re-analysing constructions of Sidorenko, Mycielski, and Bauer, van den Heuvel and Schmeichel, while the case c<3 is settled by a recent result of Brandt and Thomassé. We will also investigate the relation between other parameters of certain graphs in S like chromatic number and toughness.     

Improved bounds on linear coloring of plane graphs

A proper vertex coloring of a graph G is linear if the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number lc(G) of the graph G is the smallest number of colors in a linear coloring of G. In this paper, we give some upper bounds on linear chromatic number for plane graphs with respect to their girth, that improve some results of Raspaud and Wang (2009).     

Bounds for the b-chromatic number of some families of graphs

In this paper we obtain some upper bounds for the b-chromatic number of K_1,s-free graphs, graphs with given minimum clique partition and bipartite graphs. These bounds are given in terms of either the clique number or the chromatic number of a graph or the biclique number for a bipartite graph. We show that all the bounds are tight.     

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 Class of Edge Critical 4-Chromatic Graphs

We consider several constructions of edge critical 4-chromatic graphs which can be written as the union of a bipartite graph and a matching. In particular we construct such a graph G with each of the following properties: G can be contracted to a given critical 4-chromatic graph; for each n ≥ 7, G has n vertices and three matching edges (it is also shown that such graphs must have at least \({{8n} \over 5}\) edges); G has arbitrary large girth.     

On the well-coveredness of Cartesian products of graphs

A graph G is well-covered if every maximal independent set has the same cardinality. This paper investigates when the Cartesian product of two graphs is well-covered. We prove that if G and H both belong to a large class of graphs that includes all non-well-covered triangle-free graphs and most well-covered triangle-free graphs, then G×H is not well-covered. We also show that if G is not well-covered, then neither is G×G. Finally, we show that G×G is not well-covered for all graphs of girth at least 5 by introducing super well-covered graphs and classifying all such graphs of girth at least 5.     

Injective colorings of planar graphs with few colors

An injective coloring of a graph is a vertex coloring where two vertices have distinct colors if a path of length two exists between them. In this paper some results on injective colorings of planar graphs with few colors are presented. We show that all planar graphs of girth ≥ 19 and maximum degree Δ are injectively Δ-colorable. We also show that all planar graphs of girth ≥ 10 are injectively (Δ+1)-colorable, that Δ+4 colors are sufficient for planar graphs of girth ≥ 5 if Δ is large enough, and that subcubic planar graphs of girth ≥ 7 are injectively 5-colorable.     

Circular-imperfection of triangle-free graphs

Circular-perfect graphs form a natural superclass of the well-known perfect graphs by means of a more general coloring concept.For perfect graphs, a characterization by means of forbidden subgraphs was recently settled by Chudnovsky et al. [Chudnovsky, M., N. Robertson, P. Seymour, and R. Thomas, The Strong Perfect Graph Theorem, Annals of Mathematics 164 (2006) 51–229]. It is, therefore, natural to ask for an analogous characterization for circular-perfect graphs or, equivalently, for a characterization of all minimally circular-imperfect graphs.Our focus is the circular-(im)perfection of triangle-free graphs. We exhibit several different new infinite families of minimally circular-imperfect triangle-free graphs. This shows that a characterization of circular-perfect graphs by means of forbidden subgraphs is a difficult task, even if restricted to the class of triangle-free graphs. This is in contrary to the perfect case where it is long-time known that the only minimally imperfect triangle-free graphs are the odd holes [Tucker, A., Critical Perfect Graphs and Perfect 3-chromatic Graphs, J. Combin. Theory (B) 23 (1977) 143–149].     

On minimal triangle-free 6-chromatic graphs

A graph with chromatic number $k$ is called $k$-chromatic. Using computational methods, we show that the smallest triangle-free 6-chromatic graphs have at least 32 and at most 40 vertices. We also determine the complete set of all triangle-free 5-chromatic graphs up to 24 vertices. This implies that Reed's conjecture holds for triangle-free graphs up to at least this order. We also establish that a smallest regular triangle-free 5-chromatic graph has 24 vertices. Finally, we show that the smallest 5-chromatic graphs of girth at least 5 have at least 29 vertices and that the smallest 4-chromatic graphs of girth at least 6 have at least 25 vertices.     

Graphs of given genus and arbitrarily large maximum genus

The maximum genus of a connected graph G is the maximum among the genera of all compact orientable 2-manifolds upon which G has 2-cell embeddings. In the theorems that follow the use of an edge-adding technique is combined with the well-known Edmonds' technique to produce the desired results. Planar graphs of arbitrarily large maximum genus are displayed in Theorem 1. Theorem 2 shows that the possibility for arbitrarily large difference between genus and maximum genus is not limited to planar graphs. In particular, we show that the wheel graph, the standard maximal planar graph, and the prism graph are upper embeddable. We then show that given m and n, there is a graph of genus n and maximum genus larger than mn.     

Asymmetric directed graph coloring games

This note generalizes the (a,b)-coloring game and the (a,b)-marking game which were introduced by Kierstead [H.A. Kierstead, Asymmetric graph coloring games, J. Graph Theory 48 (2005) 169-185] for undirected graphs to directed graphs. We prove that the (a,b)-chromatic and (a,b)-coloring number for the class of orientations of forests is b+2 if b≤a, and infinity otherwise. From these results we deduce upper bounds for the (a,b)-coloring number of oriented outerplanar graphs and of orientations of graphs embeddable in a surface with bounded girth.