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 parity of crossing numbers

For an integer n ? 1, a graph G has an n-constant crossing number if, for any two good drawings ? and ?′ of G in the plane, μ(?) ≡ μ(?′) (mod n), where μ(?) is the number of crossings in ?. We prove that, except for trivial cases, a graph G has n-constant crossing number if and only if n = 2 and G is either K_p or K_q,r, where p, q, and r are odd.     

Induced matching extendable graphs

We say that a simple graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. The main results of this paper are as follows: (1) For every connected IM-extendable graph G with |V(G)| ≥ 4, the girth g(G) ≤ 4. (2) If G is a connected IM-extendable graph, then |E(G)| ≥ ${3\over 2}|V(G)| - 2$; the equality holds if and only if G ≅ T × K₂, where T is a tree. (3) The only 3-regular connected IM-extendable graphs are C_n × K₂, for n ≥ 3, and C_2n(1, n), for n ≥ 2, where C_2n(1, n) is the graph with 2n vertices x₀, x₁, …, x_2n−1, such that x_ix_j is an edge of C_2n(1, n) if either |i − j| ≡ 1 (mod 2n) or |i − j| ≡ n (mod 2n). © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 203–213, 1998     

A degree condition for the existence of regular factors in K1, n-free graphs

A graph is called K_{1, n}-free if it contains no K_{1, n} as an induced subgraph. Let n(≥3), r be integers (if r is odd, r ≥ n − 1). We prove that every K_{1, n}-free connected graph G with r|V(G)| even has an r-factor if its minimum degree is at least. $ \left(n+{{n-1}\over{r}}\right) \left\lceil {n\over{2(n-1)}}r \right\rceil - {{n-1}\over{r}}\left(\left\lceil {n\over{2(n-1)}}r \right\rceil \right)^2+n-3. $ This degree condition is sharp. © 1996 John Wiley & Sons, Inc.     

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.     

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.     

Generalized Ramsey theory for multiple colors

In this paper, we study the generalized Ramsey number r(G₁,…, G_k) where the graphs G₁,…, G_k consist of complete graphs, complete bipartite graphs, paths, and cycles. Our main theorem gives the Ramsey number for the case where G₂,…, G_k are fixed and G₁ C_n or P_n with n sufficiently large. If among G₂,…, G_k there are both complete graphs and odd cycles, the main theorem requires an additional hypothesis concerning the size of the odd cycles relative to their number. If among G₂,…, G_k there are odd cycles but no complete graphs, then no additional hypothesis is necessary and complete results can be expressed in terms of a new type of Ramsey number which is introduced in this paper. For k = 3 and k = 4 we determine all necessary values of the new Ramsey number and so obtain, in particular, explicit and complete results for the cycle Ramsey numbers r(C_n, C_l, C_k) and r(C_n, C_l, C_k, C_m) when n is large.     

On the Pósa-Seymour conjecture

Paul Seymour conjectured that any graph G of order n and minimum degree at least contains the k^th power of a Hamilton cycle. We prove the following approximate version. For any ϵ ≥ 0 and positive integer k, there is an n₀ such that, if G has order n ≥ n₀ and minimum degree at least $(\frac{k}{k+1} + \epsilon )n$, then G contains the k^th power of a Hamilton cycle. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 167–176, 1998     

Vertex-Disjoint Triangles in Claw-Free Graphs with Minimum Degree at Least Three

. Our main result is as follows: For any integer , if G is a claw-free graph of order at least and with minimum degree at least 3, then G contains k vertex-disjoint triangles unless G is of order and G belongs to a known class of graphs. We also construct a claw-free graph with minimum degree 3 on n vertices for each such that it does not contain k vertex-disjoint triangles. We put forward a conjecture on vertex-disjoint triangles in -free graphs. Received: November 21, 1996/Revised: Revised February 19, 1998     

The early evolution of the H-free process

The H-free process, for some fixed graph H, is the random graph process defined by starting with an empty graph on n vertices and then adding edges one at a time, chosen uniformly at random subject to the constraint that no H subgraph is formed. Let G be the random maximal H-free graph obtained at the end of the process. When H is strictly 2-balanced, we show that for some c>0, with high probability as n→∞, the minimum degree in G is at least cn^{1-(v_H-2)/(e_H-1)}(logn)^1/(e_H-1)cn^{1-(v_{H}-2)/(e_{H}-1)}(\log n)^{1/(e_{H}-1)}. This gives new lower bounds for the Turán numbers of certain bipartite graphs, such as the complete bipartite graphs K _r,r with r≥5. When H is a complete graph K _s with s≥5 we show that for some C>0, with high probability the independence number of G is at most Cn^2/(s+1)(logn)^1-1/(e_H-1)Cn^{2/(s+1)}(\log n)^{1-1/(e_{H}-1)}. This gives new lower bounds for Ramsey numbers R(s,t) for fixed s≥5 and t large. We also obtain new bounds for the independence number of G for other graphs H, including the case when H is a cycle. Our proofs use the differential equations method for random graph processes to analyse the evolution of the process, and give further information about the structure of the graphs obtained, including asymptotic formulae for a broad class of subgraph extension variables.     

On the odd harmonious graphs with applications

The necessary conditions for the existence of odd harmonious labelling of graph are obtained. A cycle C _n is odd harmonious if and only if n≡0 (mod 4). A complete graph K _n is odd harmonious if and only if n=2. A complete k-partite graph K(n ₁,n ₂,…,n _k ) is odd harmonious if and only if k=2. A windmill graph K _n ^t is odd harmonious if and only if n=2. The construction ways of odd harmonious graph are given. We prove that the graph ∨ _i=1 ⁿ G _i , the graph G(+r ₁,+r ₂,…,+r _p ), the graph $\bar{K_{m}}+_{0}P_{n}+_{e}\bar{K_{t}}$ , the graph G∪(X+∪ _k=1 ⁿ Y _k ), some trees and the product graph P _m ×P _n etc. are odd harmonious. The odd harmoniousness of graph can be used to solve undetermined equation.     

On tricyclic graphs of a given diameter with minimal energy

The energy of a graph is defined as the sum of the absolute values of all the eigenvalues of the graph. Let G(n,d) be the class of tricyclic graphs G on n vertices with diameter d and containing no vertex disjoint odd cycles C_p,C_q of lengths p and q with p+q≡2(mod4). In this paper, we characterize the graphs with minimal energy in G(n,d).     

Retracts of box products with odd‐angulated factors

Let G be a connected graph with odd girth 2κ+1. Then G is a (2κ+1)‐angulated graph if every two vertices of G are connected by a path such that each edge of the path is in some (2κ+1)‐cycle. We prove that if G is (2κ+1)‐angulated, and H is connected with odd girth at least 2κ+3, then any retract of the box (or Cartesian) product G□ H is S□T where S is a retract of G and T is a connected subgraph of H. A graph G is strongly (2κ+1)‐angulated if any two vertices of G are connected by a sequence of (2κ+1)‐cycles with consecutive cycles sharing at least one edge. We prove that if G is strongly (2κ+1)‐angulated, and H is connected with odd girth at least 2κ+1, then any retract of G□ H is S□T where S is a retract of G and T is a connected subgraph of H or |V(S)|=1 and T is a retract of H. These two results improve theorems on weakly and strongly triangulated graphs by Nowakowski and Rival [Disc Math 70 ( 13 ), 169–184]. As a corollary, we get that the core of the box product of two strongly (2κ+1)‐angulated cores must be either one of the factors or the box product itself. Furthermore, if G is a strongly (2κ+1)‐angulated core, then either Gⁿ is a core for all positive integers n, or the core of Gⁿ is G for all positive integers n. In the latter case, G is homomorphically equivalent to a normal Cayley graph [Larose, Laviolette, Tardiff, European J Combin 19 ( 12 ), 867–881]. In particular, let G be a strongly (2κ+1)‐angulated core such that either G is not vertex‐transitive, or G is vertex‐transitive and any two maximum independent sets have non‐empty intersection. Then Gⁿ is a core for any positive integer n. On the other hand, let G_i be a (2κ_i+1)‐angulated core for 1 ≤ i≤ n where κ₁ < κ₂ < … < κ_n. If G_i has a vertex that is fixed under any automorphism for 1 ≤ i ≤ n‐1, or G_i is vertex‐transitive such that any two maximum independent sets have non‐empty intersection for 1 ≤ i ≤ n‐1, then □_i=1ⁿ G_i is a core. We then apply the results to construct cores that are box products with Mycielski construction factors or with odd graph factors. We also show that K(r,2r+1) □ C_2l+1 is a core for any integers l ≥ r ≥ 2. It is open whether K(r,2r+1) □ C_2l+1 is a core for r > l ≥ 2. © 2006 Wiley Periodicals, Inc. J Graph Theory     

NP-hardness of the recognition of coordinated graphs

A graph G is coordinated if the minimum number of colors that can be assigned to the cliques of H in such a way that no two cliques with non-empty intersection receive the same color is equal to the maximum number of cliques of H with a common vertex, for every induced subgraph H of G. In previous works, polynomial time algorithms were found for recognizing coordinated graphs within some classes of graphs. In this paper we prove that the recognition problem for coordinated graphs is NP-hard, and it is NP-complete even when restricted to the class of {gem, C ₄, odd hole}-free graphs with maximum degree four, maximum clique size three and at most three cliques sharing a common vertex. F.J. Soulignac is partially supported by UBACyT Grant X184, Argentina and CNPq under PROSUL project Proc. 490333/2004-4, Brazil.     

Fixed Points of Automorphisms of Graphs with 1 – Factorizations

We consider sets of fixed points of finite simple undirected connected graphs with 1 – factorizations. The maximum number of fixed points of complete graphs K_2n (n > 2) is n if n ≡ 0 mod 4, n — 1 if n ≡ 3 mod 4 or n ≡ 5 mod 12, n — 2 if n ≡ 2 mod 4, n — 3 if n ≡ 1 mod 4 and n ≢ 5 (mod 12). The maximum number of fixed points of 1 – factorizations of (non – complete) graphs with 2n vertices is less than or equal to n. If n is a prime number, then there are graphs with 2n vertices whose 1 – factorizations have automorphisms with n fixed points. Moreover, a result on the structure of a group of fixed – point – free automorphisms is presented.     

On the Constant Metric Dimension of Generalized Petersen Graphs P（n, 4）

In this paper,we consider the family of generalized Petersen graphs P(n,4).We prove that the metric dimension of P(n,4) is 3 when n ≡ 0(mod 4),and is 4 when n = 4k + 3(k is even).For n ≡ 1,2(mod 4) and n = 4k + 3(k is odd),we prove that the metric dimension of P(n,4) is bounded above by 4.This shows that each graph of the family of generalized Petersen graphs P(n,4)has constant metric dimension.     

An Anti-Ramsey Theorem on Diamonds

Let G be the diamond (the graph obtained from K ₄ by deleting an edge) and, for every n ≥ 4, let f(n, G) be the minimum integer k such that, for every edge-coloring of the complete graph of order n which uses exactly k colors, there is at least one copy of G all whose edges have different colors. Let ext(n, {C ₃, C ₄}) be the maximum number of edges of a graph on n vertices free of triangles and squares. Here we prove that for every n ≥ 4,

Q5‐factorization of λKn

Q_k is the simple graph whose vertices are the k‐tuples with entries in {0, 1} and edges are the pairs of k‐tuples that differ in exactly one position. In this paper, we proved that there exists a Q₅‐factorization of λK_n if and only if (a) n ≡ 0(mod 32) if λ ≡ 0(mod 5) and (b) n ≡ 96(mod 160) if λ ? 0(mod 5).     

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.     

Sharp bounds for decompositions of graphs into complete r-partite subgraphs

If G is a graph on n vertices and r ≥ 2, we let m_r(G) denote the minimum number of complete multipartite subgraphs, with r or fewer parts, needed to partition the edge set, E(G). In determining m_r(G), we may assume that no two vertices of G have the same neighbor set. For such reducedgraphs G, we prove that m_r(G) ≥ log₂ (n + r − 1)/r. Furthermore, for each k ≥ 0 and r ≥ 2, there is a unique reduced graph G = G(r, k) with m_r(G) = k for which equality holds. We conclude with a short proof of the known eigenvalue bound m_r(G) ≥ max{n₊ (G, n₋(G)/(r − 1)}, and show that equality holds if G = G(r, k). © 1996 John Wiley & Sons, Inc.