On circle graphs with girth at least five

Circle graphs with girth at least five are known to be 2-degenerate (Ageev, 1999). In this paper, we prove that circle graphs with girth at least g ⩾ 5 contain a vertex of degree at most one, or a chain of g− 4 vertices of degree two, which implies Ageev's result in the case g = 5. We then use this structural property to give an upper bound on the circular chromatic number of circle graphs with girth at least g ⩾ 5 as well as a precise estimate of their maximum average degree.     

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.     

Linear coloring of planar graphs with large girth

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 of the graph G is the smallest number of colors in a linear coloring of G. In this paper we prove that every planar graph G with girth g and maximum degree Δ has if G satisfies one of the following four conditions: (1) g≥13 and Δ≥3; (2) g≥11 and Δ≥5; (3) g≥9 and Δ≥7; (4) g≥7 and Δ≥13. Moreover, we give better upper bounds of linear chromatic number for planar graphs with girth 5 or 6.     

Finding small regular graphs of girths 6, 8 and 12 as subgraphs of cages

Small k-regular graphs of girth g where g=6,8,12 are obtained as subgraphs of minimal cages. More precisely, we obtain (k,6)-graphs on 2(kq−1) vertices, (k,8)-graphs on 2k(q²−1) vertices and (k,12)-graphs on 2kq²(q²−1), where q is a prime power and k is a positive integer such that q≥k≥3. Some of these graphs have the smallest number of vertices known so far among the regular graphs with girth g=6,8,12.     

The parameterized complexity of the induced matching problem

Given a graph G and an integer k≥0, the NP-complete Induced Matching problem asks whether there exists an edge subset M of size at least k such that M is a matching and no two edges of M are joined by an edge of G. The complexity of this problem on general graphs, as well as on many restricted graph classes has been studied intensively. However, other than the fact that the problem is W[1]-hard on general graphs, little is known about the parameterized complexity of the problem in restricted graph classes. In this work, we provide first-time fixed-parameter tractability results for planar graphs, bounded-degree graphs, graphs with girth at least six, bipartite graphs, line graphs, and graphs of bounded treewidth. In particular, we give a linear-size problem kernel for planar graphs.     

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.     

On the girth of extremal graphs without shortest cycles

Let EX(ν;{C₃,…,C_n}) denote the set of graphs G of order ν that contain no cycles of length less than or equal to n which have maximum number of edges. In this paper we consider a problem posed by several authors: does G contain an n+1 cycle? We prove that the diameter of G is at most n−1, and present several results concerning the above question: the girth of G is g=n+1 if (i) ν≥n+5, diameter equal to n−1 and minimum degree at least 3; (ii) ν≥12, ν∉{15,80,170} and n=6. Moreover, if ν=15 we find an extremal graph of girth 8 obtained from a 3-regular complete bipartite graph subdividing its edges. (iii) We prove that if ν≥2n−3 and n≥7 the girth is at most 2n−5. We also show that the answer to the question is negative for ν≤n+1+⌊(n−2)/2⌋.     

Improved bounds on acyclic edge colouring

We prove that the acyclic chromatic index a^′(G)?6Δ for all graphs with girth at least 9. We extend the same method to obtain a bound of 4.52Δ with the girth requirement g?220. We also obtain a relationship between g and a^′(G).     

Forest embeddings in regular graphs of large girth

This paper deals with the enumeration of distinct embeddings (both induced and partial) of arbitrary graphs in regular graphs of large girth. A simple explicit recurrence formula is presented for the number of embeddings of an arbitrary forest F in an arbitrary regular graph G of sufficiently large girth. This formula (and hence the number of embeddings) depends only on the order and degree of regularity of G, and the degree sequence and component structure (multiset of component orders) of F. A concept called c-subgraph regularity is introduced which generalizes the familiar notion of regularity in graphs. (Informally, a graph is c-subgraph regular if its vertices cannot be distinguished on the basis of embeddings of graphs of order less than or equal to c.) A central result of this paper is that if G is regular and has girth g, then G is (g ? 1)-subgraph regular.     

Minors in graphs of large girth

We show that for every odd integer g ≥ 5 there exists a constant c such that every graph of minimum degree r and girth at least g contains a minor of minimum degree at least cr^(g+1)/4. This is best possible up to the value of the constant c for g = 5, 7, and 11. More generally, a well‐known conjecture about the minimal order of graphs of given minimum degree and large girth would imply that our result gives the correct order of magnitude for all odd values of g. The case g = 5 of our result implies Hadwiger's conjecture for C₄‐free graphs of sufficiently large chromatic number. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 22: 213–225, 2003     

Coloring graphs from random lists of size 2

Let G=G(n) be a graph on n vertices with girth at least g and maximum degree bounded by some absolute constant Δ. Assign to each vertex v of G a list L(v) of colors by choosing each list independently and uniformly at random from all 2-subsets of a color set C of size σ(n). In this paper we determine, for each fixed g and growing n, the asymptotic probability of the existence of a proper coloring φ such that φ(v)∈L(v) for all v∈V(G). In particular, we show that if g is odd and σ(n)=ω(n^1/(2g−2)), then the probability that G has a proper coloring from such a random list assignment tends to 1 as n→∞. Furthermore, we show that this is best possible in the sense that for each fixed odd g and each n≥g, there is a graph H=H(n,g) with bounded maximum degree and girth g, such that if σ(n)=o(n^1/(2g−2)), then the probability that H has a proper coloring from such a random list assignment tends to 0 as n→∞. A corresponding result for graphs with bounded maximum degree and even girth is also given. Finally, by contrast, we show that for a complete graph on n vertices, the property of being colorable from random lists of size 2, where the lists are chosen uniformly at random from a color set of size σ(n), exhibits a sharp threshold at σ(n)=2n.     

A lower bound on the order of regular graphs with given girth pair

The girth pair of a graph gives the length of a shortest odd and a shortest even cycle. The existence of regular graphs with given degree and girth pair was proved by Harary and Kovács [Regular graphs with given girth pair, J Graph Theory 7 ( 1 ), 209–218]. A (δ, g)‐cage is a smallest δ‐regular graph with girth g. For all δ ≥ 3 and odd girth g ≥ 5, Harary and Kovács conjectured the existence of a (δ,g)‐cage that contains a cycle of length g + 1. In the main theorem of this article we present a lower bound on the order of a δ‐regular graph with odd girth g ≥ 5 and even girth h ≥ g + 3. We use this bound to show that every (δ,g)‐cage with δ ≥ 3 and g ∈ {5,7} contains a cycle of length g + 1, a result that can be seen as an extension of the aforementioned conjecture by Harary and Kovács for these values of δ, g. Moreover, for every odd g ≥ 5, we prove that the even girth of all (δ,g)‐cages with δ large enough is at most (3g ? 3)/2. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 153–163, 2007     

Graphs with maximum size and lower bounded girth

For integers n≥4 and ν≥n+1, let ex(ν;{C₃,…,C_n}) denote the maximum number of edges in a graph of order ν and girth at least n+1. The {C₃,…,C_n}-free graphs with order ν and size ex(ν;{C₃,…,C_n}) are called extremal graphs and denoted by EX(ν;{C₃,…,C_n}). We prove that given an integer k≥0, for each n≥2log₂(k+2) there exist extremal graphs with ν vertices, ν+k edges and minimum degree 1 or 2. Considering this idea we construct four infinite families of extremal graphs. We also see that minimal (r;g)-cages are the exclusive elements in EX(ν₀(r,g);{C₃,…,C_g−1}).     

Super cyclically edge-connected vertex-transitive graphs of girth at least 5

A cyclic edge-cut of a graph G is an edge set, the removal of which separates two cycles. If G has a cyclic edge-cut, then it is called cyclically separable. We call a cyclically separable graph super cyclically edge-connected, in short, super-λc, if the removal of any minimum cyclic edge-cut results in a component which is a shortest cycle. In [Zhang, Z., Wang, B.: Super cyclically edge-connected transitive graphs. J. Combin. Optim., 22, 549-562 (2011)], it is proved that a connected vertex-transitive graph is super-λc if G has minimum degree at least 4 and girth at least 6, and the authors also presented a class of nonsuper-λc graphs which have degree 4 and girth 5. In this paper, a characterization of k (k≥4)-regular vertex-transitive nonsuper-λc graphs of girth 5 is given. Using this, we classify all k (k≥4)-regular nonsuper-λc Cayley graphs of girth 5, and construct the first infinite family of nonsuper-λc vertex-transitive non-Cayley graphs.     

The ordering of unicyclic graphs with the smallest algebraic connectivity

Fielder [M. Fielder, Algebraic connectivity of graphs, Czechoslovak Math. J. 23 (1973) 298-305] has turned out that G is connected if and only if its algebraic connectivity a(G)>0. In 1998, Fallat and Kirkland [S.M. Fallat, S. Kirkland, Extremizing algebraic connectivity subject to graph theoretic constraints, Electron. J. Linear Algebra 3 (1998) 48-74] posed a conjecture: if G is a connected graph on n vertices with girth g≥3, then a(G)≥a(C_n,g) and that equality holds if and only if G is isomorphic to C_n,g. In 2007, Guo [J.M. Guo, A conjecture on the algebraic connectivity of connected graphs with fixed girth, Discrete Math. 308 (2008) 5702-5711] gave an affirmatively answer for the conjecture. In this paper, we determine the second and the third smallest algebraic connectivity among all unicyclic graphs with vertices.     

Injective coloring of planar graphs

A coloring of a graph G is injective if its restriction to the neighborhood of any vertex is injective. The injective chromatic numberχ_i(G) of a graph G is the least k such that there is an injective k-coloring. In this paper we prove that if G is a planar graph with girth g and maximum degree Δ, then (1) χ_i(G)=Δ if either g≥20 and Δ≥3, or g≥7 and Δ≥71; (2) χ_i(G)≤Δ+1 if g≥11; (3) χ_i(G)≤Δ+2 if g≥8.     

Superconnectivity of regular graphs with small diameter

A graph is superconnected, for short super-κ, if all minimum vertex-cuts consist of the vertices adjacent with one vertex. In this paper we prove for any r-regular graph of diameter D and odd girth g that if D≤g−2, then the graph is super-κ when g≥5 and a complete graph otherwise.     

Properties of Groups for the Cage and Degree/Diameter Problems

A (k, g)-cage is a k-regular graph of girth g of minimum order. While many of the best known constructions of small k-regular graphs of girth g are known to be Cayley graphs, no general theory of the relation between the girth of a Cayley graph and the structure of the underlying group has been developed. We attempt to fill the gap by focusing on the girths of Caley graphs of nilpotent and solvable groups, and present a series of results supporting the intuitive idea that the closer a group is to being abelian, the less suitable it is for constructing Cayley graphs of large girths. Specifically, we establish the existence of upper bounds on the girths of Cayley graphs with respect to the nilpotency class and/or the length of the derived sequence of the underlying groups.     

The structure of even factors in claw-free graphs

Recently, Jackson and Yoshimoto proved that every bridgeless simple graph G with δ(G)≥3 has an even factor in which every component has order at least four, which strengthens a classical result of Petersen. In this paper, we give a strengthening of the above result and show that the above graphs have an even factor in which every component has order at least four that does not contain any given edge. We also extend the above result to the graphs with minimum degree at least three such that all bridges lie in a common path and to the bridgeless graphs that have at most two vertices of degree two respectively. Finally we use this extended result to show that every simple claw-free graph G of order n with δ(G)≥3 has an even factor with at most components. The upper bound is best possible.