Eulerian subgraphs in 3‐edge‐connected graphs and Hamiltonian line graphs

In this paper, we show that if G is a 3‐edge‐connected graph with and , then either G has an Eulerian subgraph H such that , or G can be contracted to the Petersen graph in such a way that the preimage of each vertex of the Petersen graph contains at least one vertex in S. If G is a 3‐edge‐connected planar graph, then for any , G has an Eulerian subgraph H such that . As an application, we obtain a new result on Hamiltonian line graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 308–319, 2003     

2‐connected 7‐coverings of 3‐connected graphs on surfaces

An m‐covering of a graph G is a spanning subgraph of G with maximum degree at most m. In this paper, we shall show that every 3‐connected graph on a surface with Euler genus k ≥ 2 with sufficiently large representativity has a 2‐connected 7‐covering with at most 6k ? 12 vertices of degree 7. We also construct, for every surface F² with Euler genus k ≥ 2, a 3‐connected graph G on F² with arbitrarily large representativity each of whose 2‐connected 7‐coverings contains at least 6k ? 12 vertices of degree 7. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 26–36, 2003     

Exponentially many 4‐list‐colorings of triangle‐free graphs on surfaces

Thomassen proved that every planar graph G on n vertices has at least distinct L‐colorings if L is a 5‐list‐assignment for G and at least distinct L‐colorings if L is a 3‐list‐assignment for G and G has girth at least five. Postle and Thomas proved that if G is a graph on n vertices embedded on a surface Σ of genus g, then there exist constants such that if G has an L‐coloring, then G has at least distinct L‐colorings if L is a 5‐list‐assignment for G or if L is a 3‐list‐assignment for G and G has girth at least five. More generally, they proved that there exist constants such that if G is a graph on n vertices embedded in a surface Σ of fixed genus g, H is a proper subgraph of G, and ϕ is an L‐coloring of H that extends to an L‐coloring of G, then ϕ extends to at least distinct L‐colorings of G if L is a 5‐list‐assignment or if L is a 3‐list‐assignment and G has girth at least five. We prove the same result if G is triangle‐free and L is a 4‐list‐assignment of G, where , and .     

Claw‐free 3‐connected P11‐free graphs are hamiltonian

We show that every 3‐connected claw‐free graph which contains no induced copy of P₁₁ is hamiltonian. Since there exist non‐hamiltonian 3‐connected claw‐free graphs without induced copies of P₁₂ this result is, in a way, best possible. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 111–121, 2004     

Independent sets and 2‐factors in edge‐chromatic‐critical graphs

In 1968, Vizing made the following two conjectures for graphs which are critical with respect to the chromatic index: (1) every critical graph has a 2‐factor, and (2) every independent vertex set in a critical graph contains at most half of the vertices. We prove both conjectures for critical graphs with many edges, and determine upper bounds for the size of independent vertex sets in those graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 113–118, 2004     

Critical graphs for subpancyclicity of 3‐connected claw‐free graphs

Let be the family of graphs G such that all sufficiently large k ‐connected claw‐free graphs which contain no induced copies of G are subpancyclic. We show that for every k≥3 the family is infinite and make the first step toward the complete characterization of the family . © 2009 Wiley Periodicals, Inc. J Graph Theory 62, 263–278, 2009     

Every 3‐connected claw‐free Z8‐free graph is Hamiltonian

A biclique of a graph G is a maximal induced complete bipartite subgraph of G. Given a graph G, the biclique matrix of G is a {0,1,?1} matrix having one row for each biclique and one column for each vertex of G, and such that a pair of 1, ?1 entries in a same row corresponds exactly to adjacent vertices in the corresponding biclique. We describe a characterization of biclique matrices, in similar terms as those employed in Gilmore's characterization of clique matrices. On the other hand, the biclique graph of a graph is the intersection graph of the bicliques of G. Using the concept of biclique matrices, we describe a Krausz‐type characterization of biclique graphs. Finally, we show that every induced P₃ of a biclique graph must be included in a diamond or in a 3‐fan and we also characterize biclique graphs of bipartite graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 1–16, 2010     

Archimedean ϕ ‐tolerance graphs

Let ? be a symmetric binary function, positive valued on positive arguments. A graph G = (V,E) is a ?‐tolerance graph if each vertex υ ∈ V can be assigned a closed interval I_υ and a positive tolerance t_υ so that xy ∈ E ? | I_x ∩ I_y|≥ ? (t_x,t_y). An Archimedean function has the property of tending to infinity whenever one of its arguments tends to infinity. Generalizing a known result of [15] for trees, we prove that every graph in a large class (which includes all chordless suns and cacti and the complete bipartite graphs K_2,k) is a ?‐tolerance graph for all Archimedean functions ?. This property does not hold for most graphs. Next, we present the result that every graph G can be represented as a ?_G‐tolerance graph for some Archimedean polynomial ?_G. Finally, we prove that there is a ?universal”? Archimedean function ? ^* such that every graph G is a ?^*‐tolerance graph. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 179–194, 2002     

Maximal K3's and Hamiltonicity of 4‐connected claw‐free graphs

Let cl(G) denote Ryjá?ek's closure of a claw‐free graph G. In this article, we prove the following result. Let G be a 4‐connected claw‐free graph. Assume that G[N_G(T)] is cyclically 3‐connected if T is a maximal K₃ in G which is also maximal in cl(G). Then G is hamiltonian. This result is a common generalization of Kaiser et al.'s theorem [J Graph Theory 48(4) (2005), 267–276] and Pfender's theorem [J Graph Theory 49(4) (2005), 262–272]. © 2011 Wiley Periodicals, Inc. J Graph Theory     

On 2‐factors of a bipartite graph

In this article, we consider the following problem: Given a bipartite graph G and a positive integer k, when does G have a 2‐factor with exactly k components? We will prove that if G = (V₁, V₂, E) is a bipartite graph with |V₁| = |V₂| = n ≥ 2k + 1 and δ (G) ≥ ⌈n/2⌉ + 1, then G contains a 2‐factor with exactly k components. We conjecture that if G = (V₁, V₂; E) is a bipartite graph such that |V₁| = |V₂| = n ≥ 2 and δ (G) ≥ ⌈n/2⌉ + 1, then, for any bipartite graph H = (U₁, U₂; F) with |U₁| ≤ n, |U₂| ≤ n and Δ (H) ≤ 2, G contains a subgraph isomorphic to H. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 101–106, 1999     

On hamiltonian cycles in the prism over the odd graphs

The Kneser graph K(n, k) has as its vertex set all k‐subsets of an n‐set and two k‐subsets are adjacent if they are disjoint. The odd graph O_k is a special case of Kneser graph when n = 2k + 1. A long standing conjecture claims that O_k is hamiltonian for all k>2. We show that the prism over O_k is hamiltonian for all k even. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:177‐188, 2011     

Long cycles in 3‐connected graphs in orientable surfaces

In this article, we apply a cutting theorem of Thomassen to show that there is a function f: N → N such that if G is a 3‐connected graph on n vertices which can be embedded in the orientable surface of genus g with face‐width at least f(g), then G contains a cycle of length at least cn, where c is a constant not dependent on g. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 69–84, 2002     

Finding any given 2‐factor in sparse pseudorandom graphs efficiently

Given an $n$‐vertex pseudorandom graph $G$ and an $n$‐vertex graph $H$ with maximum degree at most two, we wish to find a copy of $H$ in $G$, that is, an embedding $\phi :V\left(H\right)\to V\left(G\right)$ so that $\phi \left(u\right)\phi \left(v\right)\in E\left(G\right)$ for all $uv\in E\left(H\right)$. Particular instances of this problem include finding a triangle‐factor and finding a Hamilton cycle in $G$. Here, we provide a deterministic polynomial time algorithm that finds a given $H$ in any suitably pseudorandom graph $G$. The pseudorandom graphs we consider are $\left(p,\lambda \right)$‐bijumbled graphs of minimum degree which is a constant proportion of the average degree, that is, $\mathrm{\Omega }\left(pn\right)$. A $\left(p,\lambda \right)$‐bijumbled graph is characterised through the discrepancy property: $|e\left(A,B\right)?p|A||B||<\lambda \sqrt{|A||B|}$ for any two sets of vertices $A$ and $B$. Our condition $\lambda =O(p^{2}n/\log n)$ on bijumbledness is within a log factor from being tight and provides a positive answer to a recent question of Nenadov. We combine novel variants of the absorption‐reservoir method, a powerful tool from extremal graph theory and random graphs. Our approach builds on our previous work, incorporating the work of Nenadov, together with additional ideas and simplifications.     

Asymptotic enumeration of sparse 2‐connected graphs

We determine an asymptotic formula for the number of labelled 2‐connected (simple) graphs on n vertices and m edges, provided that m ‐ n →∞ and m = O(nlog n) as n →∞. This is the entire range of m not covered by previous results. The proof involves determining properties of the core and kernel of random graphs with minimum degree at least 2. The case of 2‐edge‐connectedness is treated similarly. We also obtain formulae for the number of 2‐connected graphs with given degree sequence for most (“typical”) sequences. Our main result solves a problem of Wright from 1983. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Hamiltonicity and forbidden subgraphs in 4‐connected graphs

Let T be the line graph of the unique tree F on 8 vertices with degree sequence (3,3,3,1,1,1,1,1), i.e., T is a chain of three triangles. We show that every 4‐connected {T, K_1,3}‐free graph has a hamiltonian cycle. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 262–272, 2005     

Covering 2‐connected 3‐regular graphs with disjoint paths

A path cover of a graph is a set of disjoint paths so that every vertex in the graph is contained in one of the paths. The path cover number of graph G is the cardinality of a path cover with the minimum number of paths. Reed in 1996 conjectured that a 2‐connected 3‐regular graph has path cover number at most . In this article, we confirm this conjecture.     

Minimum vertex‐diameter‐2‐critical graphs

We prove that the minimum number of edges in a vertex‐diameter‐2‐critical graph on n ≥ 23 vertices is (5n ? 17)/2 if n is odd, and is (5n/2) ? 7 if n is even. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Non‐rainbow colorings of 3‐, 4‐ and 5‐connected plane graphs

We study vertex‐colorings of plane graphs that do not contain a rainbow face, i.e., a face with vertices of mutually distinct colors. If G is a 3 ‐connected plane graph with n vertices, then the number of colors in such a coloring does not exceed . If G is 4 ‐connected, then the number of colors is at most , and for n≡3(mod8), it is at most . Finally, if G is 5 ‐connected, then the number of colors is at most . The bounds for 3 ‐connected and 4 ‐connected plane graphs are the best possible as we exhibit constructions of graphs with colorings matching the bounds. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 129–145, 2010