Decomposing C4-free graphs under degree constraints

A celebrated theorem of Stiebitz 13 asserts that any graph with minimum degree at least can be partitioned into two parts that induce two subgraphs with minimum degree at least s and t, respectively. This resolved a conjecture of Thomassen. In this article, we prove that for , if a graph G contains no cycle of length four and has minimum degree at least , then G can be partitioned into two parts that induce two subgraphs with minimum degree at least s and t, respectively. This improves the result of Diwan in 5, where he proved the same statement for graphs of girth at least five. Our proof also works for the case of variable functions, in which the bounds are sharp as showing by some polarity graphs.     

Embedding graphs with bounded degree in sparse pseudorandom graphs

In this paper, we show the equivalence of somequasi-random properties for sparse graphs, that is, graphsG with edge densityp=|E(G)|/( ₂ ⁿ )=o(1), whereo(1)→0 asn=|V(G)|→∞. Our main result (Theorem 16) is the following embedding result. For a graphJ, writeN _J(x) for the neighborhood of the vertexx inJ, and letδ(J) andΔ(J) be the minimum and the maximum degree inJ. LetH be atriangle-free graph and setd _H=max{δ(J):J⊆H}. Moreover, putD _H=min{2d _H,Δ(H)}. LetC>1 be a fixed constant and supposep=p(n)≫n ⁻¹ D _H. We show that ifG is such that

Backbone colorings of graphs with bounded degree

We study backbone colorings, a variation on classical vertex colorings: Given a graph G and a subgraph H of G (the backbone of G), a backbone coloring for G and H is a proper vertex k-coloring of G in which the colors assigned to adjacent vertices in H differ by at least 2. The minimal k∈N for which such a coloring exists is called the backbone chromatic number of G. We show that for a graph G of maximum degree Δ where the backbone graph is a d-degenerated subgraph of G, the backbone chromatic number is at most Δ+d+1 and moreover, in the case when the backbone graph being a matching we prove that the backbone chromatic number is at most Δ+1. We also present examples where these bounds are attained.Finally, the asymptotic behavior of the backbone chromatic number is studied regarding the degrees of G and H. We prove for any sparse graph G that if the maximum degree of a backbone graph is small compared to the maximum degree of G, then the backbone chromatic number is at most .     

Large 2P3-free graphs with bounded degree

Let ex^* (D;H) be the maximum number of edges in a connected graph with maximum degree D and no induced subgraph H; this is finite if and only if H is a disjoint union of paths. If the largest component of such an H has order m, then ex^*(D; H) = O(D²ex^*(D; P_m)). Constructively, ex^*(D;qP_m) = Θ(gD²ex^*(D;P_m)) if q>1 and m> 2(Θ(gD²) if m = 2). For H = 2P₃ (and D 8), the maximum number of edges is if D is even and

Full-size image

if D is odd, achieved by a unique extremal graph.     

Acyclic colorings of graphs with bounded degree

A k-coloring (not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colors i and j the subgraph induced by the edges whose endpoints have colors i and j is acyclic. We consider some generalized acyclic k-colorings, namely, we require that each color class induces an acyclic or bounded degree graph. Mainly we focus on graphs with maximum degree 5. We prove that any such graph has an acyclic 5-coloring such that each color class induces an acyclic graph with maximum degree at most 4. We prove that the problem of deciding whether a graph G has an acyclic 2-coloring in which each color class induces a graph with maximum degree at most 3 is NP-complete, even for graphs with maximum degree 5. We also give a linear-time algorithm for an acyclic t-improper coloring of any graph with maximum degree d assuming that the number of colors is large enough.     

Large faces in 4-critical planar graphs with minimum degree 4

We prove that the size of the largest face of a 4-critical planar graph with 4 is at most one half the number of its vertices. Letf(n) denote the maximum of the sizes of largest faces of all such graphs withn vertices (n sufficiently large). We present an infinite family of graphs that shows .All three authors gratefully acknowledge the support of the National Science and Engineering Research Council of Canada.     

Total interval number for graphs with bounded degree

The total interval number of an n-vertex graph with maximum degree Δ is at most (Δ + 1/Δ)n/2, with equality if and only if every component of the graph is K_Δ,Δ. If the graph is also required to be connected, then the maximum is Δn/2 + 1 when Δ is even, but when Δ is odd it exceeds [Δ + 1/(2.5Δ + 7.7)]n/2 for infinitely many n. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 79–84, 1997     

Path transferability of graphs with bounded minimum degree

We consider a path as an ordered sequence of distinct vertices with a head and a tail. Given a path, a transfer-move is to remove the tail and add a vertex at the head. A graph is n-transferable if any path with length n can be transformed into any other such path by a sequence of transfer-moves. We show that, unless it is complete or a cycle, a connected graph is δ-transferable, where δ≥2 is the minimum degree.     

Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width

The Multicut problem can be defined as: given a graph G and a collection of pairs of distinct vertices {s_i,t_i} of G, find a minimum set of edges of G whose removal disconnects each s_i from the corresponding t_i. Multicut is known to be NP-hard and Max SNP-hard even when the input graph is restricted to being a tree. The main result of the paper is a polynomial-time approximation scheme (PTAS) for Multicut in unweighted graphs with bounded degree and bounded tree-width. That is, for any ε>0, we present a polynomial-time (1+ε)-approximation algorithm. In the particular case when the input is a bounded-degree tree, we have a linear-time implementation of the algorithm. We also provide some hardness results: we prove that Multicut is still NP-hard for binary trees and that it is Max SNP-hard if we drop any of the three conditions (unweighted, bounded-degree, bounded tree-width). Finally we show that some of these results extend to the vertex version of Multicut and to a directed version of Multicut.     

Sparse partition universal graphs for graphs of bounded degree

In 1983, Chvátal, Trotter and the two senior authors proved that for any Δ there exists a constant B such that, for any n, any 2-colouring of the edges of the complete graph KN with N?Bn vertices yields a monochromatic copy of any graph H that has n vertices and maximum degree Δ. We prove that the complete graph may be replaced by a sparser graph G that has N vertices and edges, with N=⌈B^′n⌉ for some constant B^′ that depends only on Δ. Consequently, the so-called size-Ramsey number of any H with n vertices and maximum degree Δ is . Our approach is based on random graphs; in fact, we show that the classical Erd?s–Rényi random graph with the numerical parameters above satisfies a stronger partition property with high probability, namely, that any 2-colouring of its edges contains a monochromatic universal graph for the class of graphs on n vertices and maximum degree Δ.The main tool in our proof is the regularity method, adapted to a suitable sparse setting. The novel ingredient developed here is an embedding strategy that allows one to embed bounded degree graphs of linear order in certain pseudorandom graphs. Crucial to our proof is the fact that regularity is typically inherited at a scale that is much finer than the scale at which it is assumed.     

Dominating cliques in P5-free graphs

All induced connected subgraphs of a graphG contain a dominating set of pair-wise adjacent vertices if and only if there is no induced subgraph isomorphic to a path or a cycle of five vertices inG. Moreover, the problem of finding any given type of connected dominating sets in all members of a classG of graphs can be reduced to the graphsG∈G that have a cut-vertex or do not contain any cutsetS dominated by somes∈S. This research was supported in part by the “AKA” Research Fund of the Hungarian Academy of Sciences.     

Left and right convergence of graphs with bounded degree

The theory of convergent graph sequences has been worked out in two extreme cases, dense graphs and bounded degree graphs. One can define convergence in terms of counting homomorphisms from fixed graphs into members of the sequence (left‐convergence), or counting homomorphisms into fixed graphs (right‐convergence). Under appropriate conditions, these two ways of defining convergence was proved to be equivalent in the dense case by Borgs, Chayes, Lovász, Sós and Vesztergombi. In this paper a similar equivalence is established in the bounded degree case, if the set of graphs in the definition of right‐convergence is appropriately restricted. In terms of statistical physics, the implication that left convergence implies right convergence means that for a left‐convergent sequence, partition functions of a large class of statistical physics models converge. The proof relies on techniques from statistical physics, like cluster expansion and Dobrushin Uniqueness. © 2012 Wiley Periodicals, Inc. Random Struct. 2012     

Generalized degree conditions for graphs with bounded independence number

We consider a generalized degree condition based on the cardinality of the neighborhood union of arbitrary sets of r vertices. We show that a Dirac-type bound on this degree in conjunction with a bound on the independence number of a graph is sufficient to imply certain hamiltonian properties in graphs. For K_1,m-free grphs we obtain generalizations of known results. In particular we show: Theorem. Let r ≥ 1 and m ≥ 3 be integers. Then for each nonnegative function f(r, m) there exists a constant C = C(r, m, f(r, m)) such that if G is a graph of order n (n ≥ r, n > m) with δ_r(G) ≥ (n/3) + C and β (G) ≥ f(r, m), then (a) G is traceable if δ(G) ≥ r and G is connected; (b) G is hamiltonian if δ(G) ≥ r + 1 and G is 2-connected; (c) G is hamiltonian-connected if δ(G) ≥ r + 2 and G is 3-connected. © 1995 John Wiley & Sons, Inc.