Thomassen's conjecture implies polynomiality of 1‐Hamilton‐connectedness in line graphs

A graph G is 1‐Hamilton‐connected if G?x is Hamilton‐connected for every x∈V(G), and G is 2‐edge‐Hamilton‐connected if the graph G+ X has a hamiltonian cycle containing all edges of X for any X?E⁺(G) = {xy| x, y∈V(G)} with 1≤|X|≤2. We prove that Thomassen's conjecture (every 4‐connected line graph is hamiltonian, or, equivalently, every snark has a dominating cycle) is equivalent to the statements that every 4‐connected line graph is 1‐Hamilton‐connected and/or 2‐edge‐Hamilton‐connected. As a corollary, we obtain that Thomassen's conjecture implies polynomiality of both 1‐Hamilton‐connectedness and 2‐edge‐Hamilton‐connectedness in line graphs. Consequently, proving that 1‐Hamilton‐connectedness is NP‐complete in line graphs would disprove Thomassen's conjecture, unless P = NP. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 241–250, 2012     

3‐Factor‐Criticality of Vertex‐Transitive Graphs

A graph of order n is p ‐factor‐critical, where p is an integer of the same parity as n, if the removal of any set of p vertices results in a graph with a perfect matching. 1‐factor‐critical graphs and 2‐factor‐critical graphs are factor‐critical graphs and bicritical graphs, respectively. It is well known that every connected vertex‐transitive graph of odd order is factor‐critical and every connected nonbipartite vertex‐transitive graph of even order is bicritical. In this article, we show that a simple connected vertex‐transitive graph of odd order at least five is 3‐factor‐critical if and only if it is not a cycle.     

Some 3‐connected 4‐edge‐critical non‐Hamiltonian graphs

Let γ(G) be the domination number of graph G, thus a graph G is k‐edge‐critical if γ (G) = k, and for every nonadjacent pair of vertices u and υ, γ(G + uυ) = k?1. In Chapter 16 of the book “Domination in Graphs—Advanced Topics,” D. Sumner cites a conjecture of E. Wojcicka under the form “3‐connected 4‐critical graphs are Hamiltonian and perhaps, in general (i.e., for any k ≥ 4), (k?1)‐connected, k‐edge‐critical graphs are Hamiltonian.” In this paper, we prove that the conjecture is not true for k = 4 by constructing a class of 3‐connected 4‐edge‐critical non‐Hamiltonian graphs. © 2005 Wiley Periodicals, Inc.     

Even and odd holes in cap‐free graphs

It is an old problem in graph theory to test whether a graph contains a chordless cycle of length greater than three (hole) with a specific parity (even, odd). Studying the structure of graphs without odd holes has obvious implications for Berge's strong perfect graph conjecture that states that a graph G is perfect if and only if neither G nor its complement contain an odd hole. Markossian, Gasparian, and Reed have proven that if neither G nor its complement contain an even hole, then G is β‐perfect. In this article, we extend the problem of testing whether G(V, E) contains a hole of a given parity to the case where each edge of G has a label odd or even. A subset of E is odd (resp. even) if it contains an odd (resp. even) number of odd edges. Graphs for which there exists a signing (i.e., a partition of E into odd and even edges) that makes every triangle odd and every hole even are called even‐signable. Graphs that can be signed so that every triangle is odd and every triangle is odd and every hole is odd are called odd‐signable. We derive from a theorem due to Truemper co‐NP characterizations of even‐signable and odd‐signable graphs. A graph is strongly even‐signable if it can be signed so that every cycle of length ≥ 4 with at most one chord is even and every triangle is odd. Clearly a strongly even‐signable graph is even‐signable as well. Graphs that can be signed so that cycles of length four with one chord are even and all other cycles with at most one chord are odd are called strongly odd‐signable. Every strongly odd‐signable graph is odd‐signable. We give co‐NP characterizations for both strongly even‐signable and strongly odd‐signable graphs. A cap is a hole together with a node, which is adjacent to exactly two adjacent nodes on the hole. We derive a decomposition theorem for graphs that contain no cap as induced subgraph (cap‐free graphs). Our theorem is analogous to the decomposition theorem of Burlet and Fonlupt for Meyniel graphs, a well‐studied subclass of cap‐free graphs. If a graph is strongly even‐signable or strongly odd‐signable, then it is cap‐free. In fact, strongly even‐signable graphs are those cap‐free graphs that are even‐signable. From our decomposition theorem, we derive decomposition results for strongly odd‐signable and strongly even‐signable graphs. These results lead to polynomial recognition algorithms for testing whether a graph belongs to one of these classes. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 289–308, 1999     

Infinite paths in planar graphs IV,dividing cycles

Nash‐Williams conjectured that a 4‐connected infinite planar graph contains a spanning 2‐way infinite path if, and only if, the deletion of any finite set of vertices results in at most two infinite components. In this article, we prove this conjecture for graphs with no dividing cycles and for graphs with infinitely many vertex disjoint dividing cycles. A cycle in an infinite plane graph is called dividing if both regions of the plane bounded by this cycle contain infinitely many vertices of the graph. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 173–195, 2006     

Strongly Even‐Cycle Decomposable Graphs

A graph is strongly even‐cycle decomposable if the edge set of every subdivision with an even number of edges can be partitioned into cycles of even length. We prove that several fundamental composition operations that preserve the property of being Eulerian also yield strongly even‐cycle decomposable graphs. As an easy application of our theorems, we give an exact characterization of the set of strongly even‐cycle decomposable cographs.     

Hourglasses and Hamilton cycles in 4‐connected claw‐free graphs

We show that if G is a 4‐connected claw‐free graph in which every induced hourglass subgraph S contains two non‐adjacent vertices with a common neighbor outside S, then G is hamiltonian. This extends the fact that 4‐connected claw‐free, hourglass‐free graphs are hamiltonian, thus proving a broader special case of a conjecture by Matthews and Sumner. © 2005 Wiley Periodicals, Inc. J Graph Theory 48: 267–276, 2005     

Hamilton cycle and Hamilton path extendability of Cayley graphs on abelian groups

In this paper the concepts of Hamilton cycle (HC) and Hamilton path (HP) extendability are introduced. A connected graph Γ is n‐HC‐extendable if it contains a path of length n and if every such path is contained in some Hamilton cycle of Γ. Similarly, Γ is weakly n‐HP‐extendable if it contains a path of length n and if every such path is contained in some Hamilton path of Γ. Moreover, Γ is strongly n‐HP‐extendable if it contains a path of length n and if for every such path P there is a Hamilton path of Γ starting with P. These concepts are then studied for the class of connected Cayley graphs on abelian groups. It is proved that every connected Cayley graph on an abelian group of order at least three is 2‐HC‐extendable and a complete classification of 3‐HC‐extendable connected Cayley graphs of abelian groups is obtained. Moreover, it is proved that every connected Cayley graph on an abelian group of order at least five is weakly 4‐HP‐extendable. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory     

Hadwiger's conjecture for quasi‐line graphs

A graph G is a quasi‐line graph if for every vertex v ∈ V(G), the set of neighbors of v in G 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. Hadwiger's conjecture states that if a graph G is not t‐colorable then it contains K_{t + 1} as a minor. This conjecture has been proved for line graphs by Reed and Seymour. We extend their result to all quasi‐line graphs. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 17–33, 2008     

Claw‐free graphs and 2‐factors that separate independent vertices

In this article, we prove that a line graph with minimum degree δ≥7 has a spanning subgraph in which every component is a clique of order at least three. This implies that if G is a line graph with δ≥7, then for any independent set S there is a 2‐factor of G such that each cycle contains at most one vertex of S. This supports the conjecture that δ≥5 is sufficient to imply the existence of such a 2‐factor in the larger class of claw‐free graphs. It is also shown that if G is a claw‐free graph of order n and independence number α with δ≥2n/α?2 and n≥3α³/2, then for any maximum independent set S, G has a 2‐factor with α cycles such that each cycle contains one vertex of S. This is in support of a conjecture that δ≥n/α≥5 is sufficient to imply the existence of a 2‐factor with α cycles, each containing one vertex of a maximum independent set. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 251–263, 2012     

On Toughness and Hamiltonicity of 2K2‐Free Graphs

The toughness of a (noncomplete) graph G is the minimum value of t for which there is a vertex cut A whose removal yields components. Determining toughness is an NP‐hard problem for general input graphs. The toughness conjecture of Chvátal, which states that there exists a constant t such that every graph on at least three vertices with toughness at least t is hamiltonian, is still open for general graphs. We extend some known toughness results for split graphs to the more general class of 2K₂‐free graphs, that is, graphs that do not contain two vertex‐disjoint edges as an induced subgraph. We prove that the problem of determining toughness is polynomially solvable and that Chvátal's toughness conjecture is true for 2K₂‐free graphs.     

Unavoidable cycle lengths in graphs

An old conjecture of Erd?s states that there exists an absolute constant c and a set S of density zero such that every graph of average degree at least c contains a cycle of length in S. In this paper, we prove this conjecture by showing that every graph of average degree at least ten contains a cycle of length in a prescribed set S satisfying . © 2005 Wiley Periodicals, Inc. J Graph Theory     

Equistarable Graphs and Counterexamples to Three Conjectures on Equistable Graphs

Equistable graphs are graphs admitting positive weights on vertices such that a subset of vertices is a maximal stable set if and only if it is of total weight 1. Strongly equistable graphs are graphs such that for every and every nonempty subset T of vertices that is not a maximal stable set, there exist positive vertex weights assigning weight 1 to every maximal stable set such that the total weight of T does not equal c . General partition graphs are the intersection graphs of set systems over a finite ground set U such that every maximal stable set of the graph corresponds to a partition of U . General partition graphs are exactly the graphs every edge of which is contained in a strong clique. In 1994, Mahadev, Peled, and Sun proved that every strongly equistable graph is equistable, and conjectured that the converse holds as well. In 2009, Orlin proved that every general partition graph is equistable, and conjectured that the converse holds as well. Orlin's conjecture, if true, would imply the conjecture due to Mahadev, Peled, and Sun. An “intermediate” conjecture, posed by Miklavi? and Milani? in 2011, states that every equistable graph has a strong clique. The above conjectures have been verified for several graph classes. We introduce the notion of equistarable graphs and based on it construct counterexamples to all three conjectures within the class of complements of line graphs of triangle‐free graphs. We also show that not all strongly equistable graphs are general partition.     

Acyclic 5‐choosability of planar graphs without adjacent short cycles

The conjecture on acyclic 5‐choosability of planar graphs [Borodin et al., 2002] as yet has been verified only for several restricted classes of graphs. None of these classes allows 4‐cycles. We prove that a planar graph is acyclically 5‐choosable if it does not contain an i‐cycle adjacent to a j‐cycle where 3?j?5 if i = 3 and 4?j?6 if i = 4. This result absorbs most of the previous work in this direction. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:169‐176, 2011     

Semi‐transitive graphs

In this paper, we first consider graphs allowing symmetry groups which act transitively on edges but not on darts (directed edges). We see that there are two ways in which this can happen and we introduce the terms bi‐transitive and semi‐transitive to describe them. We examine the elementary implications of each condition and consider families of examples; primary among these are the semi‐transitive spider‐graphs PS(k,N;r) and MPS(k,N;r). We show how a product operation can be used to produce larger graphs of each type from smaller ones. We introduce the alternet of a directed graph. This links the two conditions, for each alternet of a semi‐transitive graph (if it has more than one) is a bi‐transitive graph. We show how the alternets can be used to understand the structure of a semi‐transitive graph, and that the action of the group on the set of alternets can be an interesting structure in its own right. We use alternets to define the attachment number of the graph, and the important special cases of tightly attached and loosely attached graphs. In the case of tightly attached graphs, we show an addressing scheme to describe the graph with coordinates. Finally, we use the addressing scheme to complete the classification of tightly attached semi‐transitive graphs of degree 4 begun by Marus?ic? and Praeger. This classification shows that nearly all such graphs are spider‐graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 1–27, 2004     

Orientations of graphs with uncountable chromatic number

Motivated by an old conjecture of P. Erdős and V. Neumann‐Lara, our aim is to investigate digraphs with uncountable dichromatic number and orientations of undirected graphs with uncountable chromatic number. A graph has uncountable chromatic number if its vertices cannot be covered by countably many independent sets, and a digraph has uncountable dichromatic number if its vertices cannot be covered by countably many acyclic sets. We prove that, consistently, there are digraphs with uncountable dichromatic number and arbitrarily large digirth; this is in surprising contrast with the undirected case: any graph with uncountable chromatic number contains a 4‐cycle. Next, we prove that several well‐known graphs (uncountable complete graphs, certain comparability graphs, and shift graphs) admit orientations with uncountable dichromatic number in ZFC. However, we show that the statement “every graph G of size and chromatic number ω₁ has an orientation D with uncountable dichromatic number” is independent of ZFC. We end the article with several open problems.     

Reduced graphs of diameter two

A graph H is collapsible if for every subset X ? V(H), H has a spanning connected subgraph whose set of odd-degree vertices is X. In any graph G there is a unique collection of maximal collapsible subgraphs, and when all of them are contracted, the resulting contraction of G is a reduced graph. Interest in reduced graphs arises from the fact [4] that a graph G has a spanning closed trail if and only if its corresponding reduced graph has a spanning closed trail. The concept can also be applied to study hamiltonian line graphs [11] or double cycle covers [8]. In this article, we characterize the reduced graphs of diameter two. As applications, we obtain prior results in [12] and [14], and show that every 2-edge-connected graph with diameter at most two either admits a double cycle cover with three even subgraphs or is isomorphic to the Petersen graph.     

On (4, 2)‐Choosable Graphs

A graph G is called ‐choosable if for any list assignment L that assigns to each vertex v a set of a permissible colors, there is a b‐tuple L‐coloring of G . An (a , 1)‐choosable graph is also called a‐choosable. In the pioneering article on list coloring of graphs by Erd?s et al.  2 , 2‐choosable graphs are characterized. Confirming a special case of a conjecture in  2 , Tuza and Voigt  3 proved that 2‐choosable graphs are ‐choosable for any positive integer m . On the other hand, Voigt 6 proved that if m is an odd integer, then these are the only ‐choosable graphs; however, when m is even, there are ‐choosable graphs that are not 2‐choosable. A graph is called 3‐choosable‐critical if it is not 2‐choosable, but all its proper subgraphs are 2‐choosable. Voigt conjectured that for every positive integer m , all bipartite 3‐choosable‐critical graphs are ‐choosable. In this article, we determine which 3‐choosable‐critical graphs are (4, 2)‐choosable, refuting Voigt's conjecture in the process. Nevertheless, a weaker version of the conjecture is true: we prove that there is an even integer k such that for any positive integer m , every bipartite 3‐choosable‐critical graph is ‐choosable. Moving beyond 3‐choosable‐critical graphs, we present an infinite family of non‐3‐choosable‐critical graphs that have been shown by computer analysis to be (4, 2)‐choosable. This shows that the family of all (4, 2)‐choosable graphs has rich structure.     

On stability of Hamilton‐connectedness under the 2‐closure in claw‐free graphs

It is easy to characterize chordal graphs by every k‐cycle having at least f(k) = k ? 3 chords. I prove new, analogous characterizations of the house‐hole‐domino‐free graphs using f(k) = 2?(k ? 3)/2?, and of the graphs whose blocks are trivially perfect using f(k) = 2k ? 7. These three functions f(k) are optimum in that each class contains graphs in which every k‐cycle has exactly f(k) chords. The functions 3?(k ? 3)/3? and 3k ? 11 also characterize related graph classes, but without being optimum. I consider several other graph classes and their optimum functions, and what happens when k‐cycles are replaced with k‐paths. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:137‐147, 2011     

Rank‐tolerance graph classes

In this article we introduce certain classes of graphs that generalize ?‐tolerance chain graphs. In a rank‐tolerance representation of a graph, each vertex is assigned two parameters: a rank, which represents the size of that vertex, and a tolerance which represents an allowed extent of conflict with other vertices. Two vertices are adjacent if and only if their joint rank exceeds (or equals) their joint tolerance. This article is concerned with investigating the graph classes that arise from a variety of functions, such as min, max, sum, and prod (product), that may be used as the coupling functions ? and ρ to define the joint tolerance and the joint rank. Our goal is to obtain basic properties of the graph classes from basic properties of the coupling functions. We prove a skew symmetry result that when either ? or ρ is continuous and weakly increasing, the (?,ρ)‐representable graphs equal the complements of the (ρ,?)‐representable graphs. In the case where either ? or ρ is Archimedean or dual Archimedean, the class contains all threshold graphs. We also show that, for min, max, sum, prod (product) and, in fact, for any piecewise polynomial ?, there are infinitely many split graphs which fail to be representable. In the reflexive case (where ? = ρ), we show that if ? is nondecreasing, weakly increasing and associative, the class obtained is precisely the threshold graphs. This extends a result of Jacobson, McMorris, and Mulder [10] for the function min to a much wider class, including max, sum, and prod. We also give results for homogeneous functions, powers of sums, and linear combinations of min and max. © 2006 Wiley Periodicals, Inc. J Graph Theory