Ramsey‐type results for Gallai colorings

A Gallai‐coloring of a complete graph is an edge coloring such that no triangle is colored with three distinct colors. Gallai‐colorings occur in various contexts such as the theory of partially ordered sets (in Gallai's original paper) or information theory. Gallai‐colorings extend 2‐colorings of the edges of complete graphs. They actually turn out to be close to 2‐colorings—without being trivial extensions. Here, we give a method to extend some results on 2‐colorings to Gallai‐colorings, among them known and new, easy and difficult results. The method works for Gallai‐extendible families that include, for example, double stars and graphs of diameter at most d for 2?d, or complete bipartite graphs. It follows that every Gallai‐colored K_n contains a monochromatic double star with at least 3n+ 1/4 vertices, a monochromatic complete bipartite graph on at least n/2 vertices, monochromatic subgraphs of diameter two with at least 3n/4 vertices, etc. The generalizations are not automatic though, for instance, a Gallai‐colored complete graph does not necessarily contain a monochromatic star on n/2 vertices. It turns out that the extension is possible for graph classes closed under a simple operation called equalization. We also investigate Ramsey numbers of graphs in Gallai‐colorings with a given number of colors. For any graph H let RG(r, H) be the minimum m such that in every Gallai‐coloring of K_m with r colors, there is a monochromatic copy of H. We show that for fixed H, RG (r, H) is exponential in r if H is not bipartite; linear in r if H is bipartite but not a star; constant (does not depend on r) if H is a star (and we determine its value). © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 233–243, 2010     

On the Chromatic Number of H-Free Graphs of Large Minimum Degree

The problem of determining the chromatic number of H-free graphs has been well studied, with particular attention to K _r -free graphs with large minimum degree. Recent progress has been made for triangle-free graphs on n vertices with minimum degree larger than n/3. In this paper, we determine the family of r-colorable graphs H_r{\mathcal{H}_r}, such that if H ? H_r{H \in \mathcal{H}_r}, there exists a constant C < (r − 2)/(r − 1) such that any H-free graph G on n vertices with δ(G) > Cn has chromatic number bounded above by a function dependent only on H and C. A value of C < (r − 2)/(r − 1) is given for every H ? H_r{H \in \mathcal{H}_r}, with particular attention to the case when χ(H) = 3.     

Subgraphs in vertex neighborhoods of Kr‐free graphs

In a K_r‐free graph, the neighborhood of every vertex induces a K_{r ? 1}‐free subgraph. The K_r‐free graphs with the converse property that every induced K_{r ? 1}‐free subgraph is contained in the neighborhood of a vertex are characterized, based on the characterization in the case r ? 3 due to Pach [ 8 ]. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 29–38, 2004     

On Switching to H‐Free Graphs

In this article, we study the problem of deciding if, for a fixed graph H, a given graph is switching equivalent to an H‐free graph. Polynomial‐time algorithms are known for H having at most three vertices or isomorphic to P₄. We show that for H isomorphic to a claw, the problem is polynomial, too. On the other hand, we give infinitely many graphs H such that the problem is NP‐complete, thus solving an open problem [Kratochvíl, Ne?et?il and Zýka, Ann Discrete Math 51 (1992)]. Further, we give a characterization of graphs switching equivalent to a K_{1, 2}‐free graph by ten forbidden‐induced subgraphs, each having five vertices. We also give the forbidden‐induced subgraphs for graphs switching equivalent to a forest of bounded vertex degrees.     

Continuous k‐to‐1 functions between complete graphs whose orders are of a different parity

A function between graphs is k‐to‐1 if each point in the codomain has precisely k pre‐images in the domain. Given two graphs, G and H, and an integer k≥1, and considering G and H as subsets of ?³, there may or may not be a k‐to‐1 continuous function (i.e. a k‐to‐1 map in the usual topological sense) from G onto H. In this paper we consider graphs G and H whose order is of a different parity and determine the even and odd values of k for which there exists a k‐to‐1 map from G onto H. We first consider k‐to‐1 maps from K_2r onto K_2s+1 and prove that for 1≤r≤s, (r, s)≠(1, 1), there is a continuous k‐to‐1 map for k even if and only if k≥2s and for k odd if and only if k≥?s?_o (where ?s?_o indicates the next odd integer greater than or equal to s). We then consider k‐to‐1 maps from K_2s+1 onto K_2s. We show that for 1≤r<s, such a map exists for even values of k if and only if k≥2s. We also prove that whatever the values of r and s are, no such k‐to‐1 map exists for odd values of k. To conclude, we give all triples (n, k, m) for which there is a k‐to‐1 map from K_n onto K_m in the case when n≤m. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 35–60, 2010.     

The circular chromatic number of series‐parallel graphs

In this article, we consider the circular chromatic number χ_c(G) of series‐parallel graphs G. It is well known that series‐parallel graphs have chromatic number at most 3. Hence, their circular chromatic numbers are at most 3. If a series‐parallel graph G contains a triangle, then both the chromatic number and the circular chromatic number of G are indeed equal to 3. We shall show that if a series‐parallel graph G has girth at least 2 ⌊(3k − 1)/2⌋, then χ_c(G) ≤ 4k/(2k − 1). The special case k = 2 of this result implies that a triangle free series‐parallel graph G has circular chromatic number at most 8/3. Therefore, the circular chromatic number of a series‐parallel graph (and of a K₄‐minor free graph) is either 3 or at most 8/3. This is in sharp contrast to recent results of Moser [5] and Zhu [14], which imply that the circular chromatic number of K₅‐minor free graphs are precisely all rational numbers in the interval [2, 4]. We shall also construct examples to demonstrate the sharpness of the bound given in this article. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 14–24, 2000     

The existence of a 2‐factor in K1, n‐free graphs with large connectivity and large edge‐connectivity

In this article, we study the existence of a 2‐factor in a K_{1, n}‐free graph. Sumner [J London Math Soc 13 (1976), 351–359] proved that for n?4, an (n?1)‐connected K_{1, n}‐free graph of even order has a 1‐factor. On the other hand, for every pair of integers m and n with m?n?4, there exist infinitely many (n?2)‐connected K_{1, n}‐free graphs of even order and minimum degree at least m which have no 1‐factor. This implies that the connectivity condition of Sumner's result is sharp, and we cannot guarantee the existence of a 1‐factor by imposing a large minimum degree. On the other hand, Ota and Tokuda [J Graph Theory 22 (1996), 59–64] proved that for n?3, every K_{1, n}‐free graph of minimum degree at least 2n?2 has a 2‐factor, regardless of its connectivity. They also gave examples showing that their minimum degree condition is sharp. But all of them have bridges. These suggest that the effects of connectivity, edge‐connectivity and minimum degree to the existence of a 2‐factor in a K_{1, n}‐free graph are more complicated than those to the existence of a 1‐factor. In this article, we clarify these effects by giving sharp minimum degree conditions for a K_{1, n}‐free graph with a given connectivity or edge‐connectivity to have a 2‐factor. Copyright © 2010 Wiley Periodicals, Inc. J Graph Theory 68:77‐89, 2011     

Every 4‐Colorable Graph With Maximum Degree 4 Has an Equitable 4‐Coloring

Chen et al., conjectured that for r≥3, the only connected graphs with maximum degree at most r that are not equitably r‐colorable are K_{r, r} (for odd r) and K_{r + 1}. If true, this would be a joint strengthening of the Hajnal–Szemerédi theorem and Brooks' theorem. Chen et al., proved that their conjecture holds for r = 3. In this article we study properties of the hypothetical minimum counter‐examples to this conjecture and the structure of “optimal” colorings of such graphs. Using these properties and structure, we show that the Chen–Lih–Wu Conjecture holds for r≤4. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:31–48, 2012     

P4‐decompositions of regular graphs

In this article, we show that every simple r‐regular graph G admits a balanced P₄‐decomposition if r ≡ 0(mod 3) and G has no cut‐edge when r is odd. We also show that a connected 4‐regular graph G admits a P₄‐decomposition if and only if |E(G)| ≡ 0(mod 3) by characterizing graphs of maximum degree 4 that admit a triangle‐free Eulerian tour. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 135–143, 1999     

On the structure of clique‐free graphs

Using a clever inductive counting argument Erd?s, Kleitman and Rothschild showed in 1976 that almost all triangle‐free graphs are bipartite, i.e., that the cardinality of the two graph classes is asymptotically equal. In this paper we investigate the structure of the “few” triangle‐free graphs which are not bipartite. As it turns out, with high probability, these graphs are bipartite up to a few vertices. More precisely, almost all of them can be made bipartite by removing just one vertex. Almost all others can be made bipartite by removing two vertices, and then three vertices and so on. We also show that similar results hold if we replace “triangle‐free” by K_??+1‐free and “bipartite” by ??‐partite. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19, 37–53, 2001     

On triangles in ‐minor free graphs

We study graphs where each edge that is incident to a vertex of small degree (of degree at most 7 and 9, respectively) belongs to many triangles (at least 4 and 5, respectively) and show that these graphs contain a complete graph (K₆ and K₇, respectively) as a minor. The second case settles a problem of Nevo. Moreover, if each edge of a graph belongs to six triangles, then the graph contains a K₈‐minor or contains K_{2, 2, 2, 2, 2} as an induced subgraph. We then show applications of these structural properties to stress freeness and coloring of graphs. In particular, motivated by Hadwiger's conjecture, we prove that every K₇‐minor free graph is 8‐colorable and every K₈‐minor free graph is 10‐colorable.     

A note on Ramsey numbers for books

The book with n pages B_n is the graph consisting of n triangles sharing an edge. The book Ramsey number r(B_m,B_n) is the smallest integer r such that either B_m ? G or B_n ? G for every graph G of order r. We prove that there exists a positive constant c such that r(B_m,B_n) = 2n + 3 for all n ≥ cm. Our proof is based mainly on counting; we also use a result of Andrásfai, Erd?s, and Sós stating that triangle‐free graphs of order n and minimum degree greater than 2n/5 are bipartite. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Two remarks on the Burr–Erdős conjecture

The Ramsey number r(H) of a graph H is the minimum positive integer N such that every two-coloring of the edges of the complete graph K_N on N vertices contains a monochromatic copy of H. A graph H is d-degenerate if every subgraph of H has minimum degree at most d. Burr and Erdős in 1975 conjectured that for each positive integer d there is a constant c_d such that r(H)≤c_dn for every d-degenerate graph H on n vertices. We show that for such graphs , improving on an earlier bound of Kostochka and Sudakov. We also study Ramsey numbers of random graphs, showing that for d fixed, almost surely the random graph G(n,d/n) has Ramsey number linear in n. For random bipartite graphs, our proof gives nearly tight bounds.     

Forbidden induced subgraphs for star-free graphs

Let H be a family of connected graphs. A graph G is said to be H-free if G is H-free for every graph H in H. In Aldred et al. (2010) [1], it was pointed that there is a family of connected graphs H not containing any induced subgraph of the claw having the property that the set of H-free connected graphs containing a claw is finite, provided also that those graphs have minimum degree at least 2 and maximum degree at least 3. In the same work, it was also asked whether there are other families with the same property. In this paper, we answer this question by solving a wider problem. We consider not only claw-free graphs but the more general class of star-free graphs. Concretely, given t≥3, we characterize all the graph families H such that every large enough H-free connected graph is K_1,t-free. Additionally, for the case t=3, we show the families that one gets when adding the condition ∣H∣≤k for each positive integer k.     

Infinite families of crossing‐critical graphs with prescribed average degree and crossing number

?iráň constructed infinite families of k‐crossing‐critical graphs for every k?3 and Kochol constructed such families of simple graphs for every k?2. Richter and Thomassen argued that, for any given k?1 and r?6, there are only finitely many simple k‐crossing‐critical graphs with minimum degree r. Salazar observed that the same argument implies such a conclusion for simple k‐crossing‐critical graphs of prescribed average degree r>6. He established the existence of infinite families of simple k‐crossing‐critical graphs with any prescribed rational average degree r∈[4, 6) for infinitely many k and asked about their existence for r∈(3, 4). The question was partially settled by Pinontoan and Richter, who answered it positively for $r\in(3\frac{1}{2},4)$. The present contribution uses two new constructions of crossing‐critical simple graphs along with the one developed by Pinontoan and Richter to unify these results and to answer Salazar's question by the following statement: there exist infinite families of simple k‐crossing‐critical graphs with any prescribed average degree r∈(3, 6), for any k greater than some lower bound N_r. Moreover, a universal lower bound N_I on k applies for rational numbers in any closed interval I?(3, 6). © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 139–162, 2010     

Clique‐coloring some classes of odd‐hole‐free graphs

We consider the problem of clique‐coloring, that is coloring the vertices of a given graph such that no maximal clique of size at least 2 is monocolored. Whereas we do not know any odd‐hole‐free graph that is not 3‐clique‐colorable, the existence of a constant C such that any perfect graph is C‐clique‐colorable is an open problem. In this paper we solve this problem for some subclasses of odd‐hole‐free graphs: those that are diamond‐free and those that are bull‐free. We also prove the NP‐completeness of 2‐clique‐coloring K₄‐free perfect graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 233–249, 2006     

K4‐free graphs with no odd hole: Even pairs and the circular chromatic number

An odd hole in a graph is an induced cycle of odd length at least five. In this article we show that every imperfect K₄‐free graph with no odd hole either is one of two basic graphs, or has an even pair or a clique cutset. We use this result to show that every K₄‐free graph with no odd hole has circular chromatic number strictly smaller than 4. We also exhibit a sequence {H_n} of such graphs with lim_n→∞χ_c(H_n)=4. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 303–322, 2010     

Acyclic Edge Coloring of Triangle‐Free Planar Graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a′(G). It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a′(G) ? Δ + 2, where Δ = Δ(G) denotes the maximum degree of the graph. If every induced subgraph H of G satisfies the condition |E(H)| ? 2|V(H)|?1, we say that the graph G satisfies Property A. In this article, we prove that if G satisfies Property A, then a′(G) ? Δ + 3. Triangle‐free planar graphs satisfy Property A. We infer that a′(G) ? Δ + 3, if G is a triangle‐free planar graph. Another class of graph which satisfies Property A is 2‐fold graphs (union of two forests). © 2011 Wiley Periodicals, Inc. J Graph Theory     

Equimatchable Regular Graphs

A graph is called equimatchable if all of its maximal matchings have the same size. Kawarabayashi, Plummer, and Saito showed that the only connected equimatchable 3‐regular graphs are K₄ and K_{3, 3}. We extend this result by showing that for an odd positive integer r, if G is a connected equimatchable r‐regular graph, then . Also it is proved that for an even r, a connected triangle‐free equimatchable r‐regular graph is isomorphic to one of the graphs C₅, C₇, and .     

On embeddability and stresses of graphs

Gluck has proven that triangulated 2-spheres are generically 3-rigid. Equivalently, planar graphs are generically 3-stress free. We show that already the K ₅-minor freeness guarantees the stress freeness. More generally, we prove that every K _r+2-minor free graph is generically r-stress free for 1≤r≤4. (This assertion is false for r≥6.) Some further extensions are discussed. Supported by an I.S.F. grant.