An approach to hedetniemi's conjecture

For a fixed integer n ? ω, a graph G of chromatic number greater than n is called persistent if for all n + 1-chromatic graphs H, the products G × H are n + 1-chromatic graphs. Wheter all graphs of chromatic number greater than n are persistent is a long-standing open problem due to Hedetniemi. We call a graph G strongly persistent if G is persistent and the Hajos sum of G with any other persistent graph H is still persistent. This paper extends the class of known persistent graphs by proving the following results: If G is constructed from copies of K_n+1 by Hajos sums, adding vertices and edges and at most one contraction of nonadjacent vertices, then G is strongly persistent. © 1929 John Wiley & Sons, Inc.     

Small Edge Sets Meeting all Triangles of a Graph

It was conjectured in 1981 by the third author that if a graph G does not contain more than t pairwise edge-disjoint triangles, then there exists a set of at most 2t edges that shares an edge with each triangle of G. In this paper, we prove this conjecture for odd-wheel-free graphs and for ‘triangle-3-colorable’ graphs, where the latter property means that the edges of the graph can be colored with three colors in such a way that each triangle receives three distinct colors on its edges. Among the consequences we obtain that the conjecture holds for every graph with chromatic number at most four. Also, two subclasses of K ₄-free graphs are identified, in which the maximum number of pairwise edge-disjoint triangles is equal to the minimum number of edges covering all triangles. In addition, we prove that the recognition problem of triangle-3-colorable graphs is intractable.     

The six bidecomposable graphs

A graph G is said to be decomposable if G can be decomposed into a cartesian product of two nontrivial graphs. G is bidecomposable if not only G but also its complement G is decomposable. We prove that there are only six bidecomposable graphs; 2K(2), C₄, Q ₃, K(2) ×(K(2) + K(2)) , K(3) × K(3).     

The chromatic number of the product of two 4-chromatic graphs is 4

For any graphG and numbern≧1 two functionsf, g fromV(G) into {1, 2, ...,n} are adjacent if for all edges (a, b) ofG, f(a) ≠g(b). The graph of all such functions is the colouring graph ℒ(G) ofG. We establish first that χ(G)=n+1 implies χ(ℒ(G))=n iff χ(G ×H)=n+1 for all graphsH with χ(H)≧n+1. Then we will prove that indeed for all 4-chromatic graphsG χ(ℒ(G))=3 which establishes Hedetniemi’s [3] conjecture for 4-chromatic graphs. This research was supported by NSERC grant A7213     

A classification of graph capacity functions

Given two graphs G = (V(G), E(G)) and H = (V(H), E(H)), the sum of G and H, G + H, is the disjoint union of G and H. The product of G and H, G × H, is the graph with the vertex set V(G × H) that is the Cartesian product of V(G) and V(H), and two vertices (g₁, h₁), (g₂, h₂) are adjacent if and only if [g₁, g₂] (ELEMENT) E(G) and [h₁, h₂] (ELEMENT) E(H). Let G denote the set of all graphs. Given a graph G, the G-matching function, γ_G, assigns any graph H (ELEMENT) G to the maximum integer k such that kG is a subgraph of H. The graph capacity function for G, P_G: G → (RFRAKTUR), is defined as P_G(H) = lim_n→z[γ_G(Hⁿ)]^1/n, where Hⁿ denotes the n-fold product of H × H × … × H. Different graphs G may have different graph capacity functions, all of which are increasing. In this paper, we classify all graphs whose capacity functions are additive, multiplicative, and increasing; all graphs whose capacity functions are pseudo-additive, pseudo-multiplicative, and increasing; and all graphs whose capacity functions fall under neither of the above cases. © 1996 John Wiley & Sons, Inc.     

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     

A partition approach to Vizing's conjecture

In 1963, Vizing [Vichysl.Sistemy 9 (1963), 30–43] conjectured that γ(G × H) ≥ γ(G)γ(H), where G × H denotes the cartesian product of graphs, and γ(G) is the domination number. In this paper we define the extraction number x(G) and we prove that P₂(G) ≤ x(G), and γ(G × H) ≥ x(G)γ(H), where P₂(G) is the 2-packing number of G. Though the equality x(G) = γ(G) is proven to hold in several classes of graphs, we construct an infinite family of graphs which do not satisfy this condition. Also, we show the following lower bound: γ(G × H) ≥ γ(G)P₂(H) + P₂(G)(γ(H) − P₂(H)). © 1996 John Wiley & Sons, Inc.     

1-Factorizations of cartesian products of regular graphs

Let G₁, G₂…, G_n be regular graphs and H be the Cartesian product of these graphs (H = G₁ × G₂ × … × G_n). The following will be proved: If the set {G₁, G₂…, G_n} has at leat one of the following properties: (*) for at leat one i ? {1, 2,…, n}, there exists a 1-factorization of G_i or (**) there exists at least two numbers i and j such that 1 ≤ i < j ≤ n and both the Graphs G_i and G_j contain at least one 1-factor, then there exists a 1-factorization of H. Further results: Let F be a cycle of length greater than three and let G be an arbitrary cubic graph. Then there exists a 1-factorization of the 5-regular graph H = F × G. The last result shows that neither (*) nor (**) is a necessary condition for the existence of a 1-factorization of a Cartesian product of regular graphs.     

Special subdivisions ofK 4 and 4-chromatic graphs

In this paper we consider special subdivisions ofK ₄ in which some of the edges are left undivided. A best possible extremal-result for the case where the edges of a Hamiltonian path are left undivided is obtained. Moreover special subdivisions as subgraphs of 4-chromatic graphs are studied. Our main-result on 4-chromatic graphs says that any 4-critical graphG contains an odd cycleC without diagonals such thatG-V (C) is connected.     

Finding a monochromatic subgraph or a rainbow path

For simple graphs G and H, let f(G,H) denote the least integer N such that every coloring of the edges of K_N contains either a monochromatic copy of G or a rainbow copy of H. Here we investigate f(G,H) when H = P_k. We show that even if the number of colors is unrestricted when defining f(G,H), the function f(G,P_k), for k = 4 and 5, equals the (k ? 2)‐ coloring diagonal Ramsey number of G. © 2006 Wiley Periodicals, Inc. J Graph Theory     

On the Hardness of Approximating the Chromatic Number

k -colorable for some fixed . Our main result is that it is NP-hard to find a 4-coloring of a 3-chromatic graph. As an immediate corollary we obtain that it is NP-hard to color a k-chromatic graph with at most colors. We also give simple proofs of two results of Lund and Yannakakis [20]. The first result shows that it is NP-hard to approximate the chromatic number to within for some fixed ε > 0. We point here that this hardness result applies only to graphs with large chromatic numbers. The second result shows that for any positive constant h, there exists an integer , such that it is NP-hard to decide whether a given graph G is -chromatic or any coloring of G requires colors. Received April 11, 1997/Revised June 10, 1999     

Coloring quasi‐line graphs

A graph G is a quasi‐line graph if for every vertex v, the set of neighbors of v can be expressed as the union of two cliques. The class of quasi‐line graphs is a proper superset of the class of line graphs. A theorem of Shannon's implies that if G is a line graph, then it can be properly colored using no more than 3/2 ω(G) colors, where ω(G) is the size of the largest clique in G. In this article, we extend this result to all quasi‐line graphs. We also show that this bound is tight. © 2006 Wiley Periodicals, Inc. J Graph Theory     

Proportional graphs

Let S be a finite set of graphs and t a real number, 0 < t < 1. A (deterministic) graph G is (t, 5)-proportional if for every H ∈ S, the number of induced subgraphs of G isomorphic to H equals the expected number of induced copies of H in the random graph G_{n, t} where n = |V(G)|. Let S_k = {all graphs on k vertices}, in particular S₃ = {K₃, P₂, K₂K_t, D₃}. The notion of proportional graphs stems from the study of random graphs (Barbour, Karoński, and Ruciński, J Combinat. Th. Ser. B, 47 , 125-145, 1989; Janson and Nowicki, Prob. Th. Rel. Fields, to appear, Janson, Random Struct. Alg., 1 , 15-37, 1990) where it is shown that (t, S₃)-proportional graphs play a very special role; we thus call them simply t-proportional. However, only a few ½-proportional graphs on 8 vertices were known and it was an open problem whether there are any f-proportional graphs with t ≠ ½ at all. In this paper, we show that there are infinitely many ½-proportional graphs and that there are t-proportional graphs with t≠. Both results are proved constructively. [We are not able to provide the latter construction for all f∈ Q∩(0,1), but the set of ts for which our construction works is dense in (0,1).] To support a conviction that the existence of (t, S₃)-proportional graphs was not quite obvious, we show that there are no (t, S₄)-proportional graphs.     

Absolutely 3-chromatic graphs

A fold is a sequence of simple folds (elementary homomorphisms in which the identified vertices are both adjacent to a common vertex). It was shown in (C. R. Cook and A. B. Evans, Graph folding. Proceedings of the South Eastern Conference on Combinatorics, Graph Theory, and Computing, Boca Raton, 1979, pp. 305–314) that all connected n-chromatic graphs can be folded onto K_n. A connected n-chromatic graph is called absolutely n-chromatic if it can only be folded onto K_m when m = n. Some classes of absolutely n-chromatic graphs were given in Cook and Evans. In this paper, we classify the absolutely 3-chromatic graphs.     

Geodesic subgraphs

Define a geodesic subgraph of a graph to be a subgraph H with the property that any geodesic of two points of H is in H. The trivial geodesic subgraphs are the complete graphs K_n' n ≧ 0, and G itself. We characterize all (finite, simple, connected) graphs with only the trivial geodesic subgraphs, and give an algorithm for their construction. We do this also for triangle-free graphs.     

Asymmetric 2‐colorings of graphs

We show that the edges of every 3‐connected planar graph except K₄ can be colored with two colors in such a way that the graph has no color‐preserving automorphisms. Also, we characterize all graphs that have the property that their edges can be 2‐colored so that no matter how the graph is embedded in any orientable surface, there is no homeomorphism of the surface that induces a nontrivial color‐preserving automorphism of the graph.     

Rainbow faces in edge‐colored plane graphs

A face of an edge‐colored plane graph is called rainbow if the number of colors used on its edges is equal to its size. The maximum number of colors used in an edge coloring of a connected plane graph Gwith no rainbow face is called the edge‐rainbowness of G. In this paper we prove that the edge‐rainbowness of Gequals the maximum number of edges of a connected bridge face factor H of G, where a bridge face factor H of a plane graph Gis a spanning subgraph H of Gin which every face is incident with a bridge and the interior of any one face f∈F(G) is a subset of the interior of some face f′∈F(H). We also show upper and lower bounds on the edge‐rainbowness of graphs based on edge connectivity, girth of the dual graphs, and other basic graph invariants. Moreover, we present infinite classes of graphs where these equalities are attained. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 84–99, 2009     

Friendship Two-Graphs

A friendship graph is a graph in which every two distinct vertices have exactly one common neighbor. All finite friendship graphs are known, each of them consists of triangles having a common vertex. We extend friendship graphs to two-graphs, a two-graph being an ordered pair G = (G ₀, G ₁) of edge-disjoint graphs G ₀ and G ₁ on the same vertex-set V(G ₀) = V(G ₁). One may think that the edges of G are colored with colors 0 and 1. In a friendship two-graph, every unordered pair of distinct vertices u, v is connected by a unique bicolored 2-path. The pairs of adjacency matrices of friendship two-graphs are solutions to the matrix equation AB + BA = J − I, where A and B are n × n symmetric 0 − 1 matrices, J is an n × n matrix with every entry being 1, and I is the identity n × n matrix. We show that there is no finite friendship two-graph with minimum vertex degree at most two. However, we construct an infinite such graph, and this construction can be extended to an infinite (uncountable) family. Also, we find a finite friendship two-graph, conjecture that it is unique, and prove this conjecture for the two-graphs that have a dominating vertex.     

The size Ramsey number of trees with bounded degree

The size Ramsey number r?(G, H) of graphs G and H is the smallest integer r? such that there is a graph F with r? edges and if the edge set of F is red-blue colored, there exists either a red copy of G or a blue copy of H in F. This article shows that r?(T_nd, T_nd) ? c · d² · n and c · n³ ? r?(K_n, T_nd) ? c(d)·n³ log n for every tree T_nd on n vertices. and maximal degree at most d and a complete graph K_n on n vertices. A generalization will be given. Probabilistic method is used throught this paper. © 1993 John Wiley Sons, Inc.     

Constrained Ramsey numbers for rainbow matching

The Ramsey number R_k(G) of a graph G is the minimum number N, such that any edge coloring of K_N with k colors contains a monochromatic copy of G. The constrained Ramsey number f(G, T) of the graphs G and T is the minimum number N, such that any edge coloring of K_N with any number of colors contains a monochromatic copy of G or a rainbow copy of T. We show that these two quantities are closely related when T is a matching. Namely, for almost all graphs G, f(G, tK₂) = R_{t ? 1}(G) for t≥2. © 2010 Wiley Periodicals, Inc. J Graph Theory 67:91‐95, 2011