Maximum Δ‐edge‐colorable subgraphs of class II graphs

A graph G is class II, if its chromatic index is at least Δ + 1. Let H be a maximum Δ‐edge‐colorable subgraph of G. The paper proves best possible lower bounds for |E(H)|/|E(G)|, and structural properties of maximum Δ‐edge‐colorable subgraphs. It is shown that every set of vertex‐disjoint cycles of a class II graph with Δ≥3 can be extended to a maximum Δ‐edge‐colorable subgraph. Simple graphs have a maximum Δ‐edge‐colorable subgraph such that the complement is a matching. Furthermore, a maximum Δ‐edge‐colorable subgraph of a simple graph is always class I. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Characterizing subgraphs of Hamming graphs

Cartesian products of complete graphs are known as Hamming graphs. Using embeddings into Cartesian products of quotient graphs we characterize subgraphs, induced subgraphs, and isometric subgraphs of Hamming graphs. For instance, a graph G is an induced subgraph of a Hamming graph if and only if there exists a labeling of E(G) fulfilling the following two conditions: (i) edges of a triangle receive the same label; (ii) for any vertices u and v at distance at least two, there exist two labels which both appear on any induced u, υ‐path. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 302–312, 2005     

Quadratic Upper Bounds on the Erdős–Pósa Property for a Generalization of Packing and Covering Cycles

According to the classical Erd?s–Pósa theorem, given a positive integer k, every graph G either contains k vertex disjoint cycles or a set of at most vertices that hits all its cycles. Robertson and Seymour (J Comb Theory Ser B 41 (1986), 92–114) generalized this result in the best possible way. More specifically, they showed that if is the class of all graphs that can be contracted to a fixed planar graph H, then every graph G either contains a set of k vertex‐disjoint subgraphs of G, such that each of these subgraphs is isomorphic to some graph in or there exists a set S of at most vertices such that contains no subgraph isomorphic to any graph in . However, the function f is exponential. In this note, we prove that this function becomes quadratic when consists all graphs that can be contracted to a fixed planar graph . For a fixed c, is the graph with two vertices and parallel edges. Observe that for this corresponds to the classical Erd?s–Pósa theorem.     

The Erdős–Pósa Property for Long Circuits

For an integer ? at least 3, we prove that if G is a graph containing no two vertex‐disjoint circuits of length at least ?, then there is a set X of at most vertices that intersects all circuits of length at least ?. Our result improves the bound due to Birmelé, Bondy, and Reed (The Erd?s–Pósa property for long circuits, Combinatorica 27 (2007), 135–145) who conjecture that ? vertices always suffice.     

A Characterization of b‐Perfect Graphs

A b‐coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbor in all other color classes, and the b‐chromatic number of a graph G is the largest integer k such that G admits a b‐coloring with k colors. A graph is b‐perfect if the b‐chromatic number is equal to the chromatic number for every induced subgraph of G. We prove that a graph is b‐perfect if and only if it does not contain as an induced subgraph a member of a certain list of 22 graphs. This entails the existence of a polynomial‐time recognition algorithm and of a polynomial‐time algorithm for coloring exactly the vertices of every b‐perfect graph. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:95–122, 2012     

Partial characterizations of circular‐arc graphs

A circular‐arc graph is the intersection graph of a family of arcs on a circle. A characterization by forbidden induced subgraphs for this class of graphs is not known, and in this work we present a partial result in this direction. We characterize circular‐arc graphs by a list of minimal forbidden induced subgraphs when the graph belongs to any of the following classes: P₄ ‐free graphs, paw‐free graphs, claw‐free chordal graphs and diamond‐free graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 289–306, 2009     

The Erdős‐Sós Conjecture for trees of diameter four

The Erd?s‐Sós Conjecture is that a finite graph G with average degree greater than k ? 2 contains every tree with k vertices. Theorem 1 is a special case: every k‐vertex tree of diameter four can be embedded in G. A more technical result, Theorem 2, is obtained by extending the main ideas in the proof of Theorem 1. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 291–301, 2005     

Large cliques or stable sets in graphs with no four‐edge path and no five‐edge path in the complement

Erd?s and Hajnal [Discrete Math 25 (1989), 37–52] conjectured that, for any graph H, every graph on n vertices that does not have H as an induced subgraph contains a clique or a stable set of size n^?(H) for some ?(H)>0. The Conjecture 1. known to be true for graphs H with |V(H)|≤4. One of the two remaining open cases on five vertices is the case where H is a four‐edge path, the other case being a cycle of length five. In this article we prove that every graph on n vertices that does not contain a four‐edge path or the complement of a five‐edge path as an induced subgraph contains either a clique or a stable set of size at least n^1/6. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Geodesic subgraphs

Define a geodesic subgraph of a graph to be a subgraph H with the property that any geodesic of two points of H is in H. The trivial geodesic subgraphs are the complete graphs K_n' n ≧ 0, and G itself. We characterize all (finite, simple, connected) graphs with only the trivial geodesic subgraphs, and give an algorithm for their construction. We do this also for triangle-free graphs.     

Acyclic edge coloring of 2‐degenerate graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a′(G). A graph is called 2‐degenerate if any of its induced subgraph has a vertex of degree at most 2. The class of 2‐degenerate graphs properly contains series–parallel graphs, outerplanar graphs, non ? regular subcubic graphs, planar graphs of girth at least 6 and circle graphs of girth at least 5 as subclasses. It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a′(G)?Δ + 2, where Δ = Δ(G) denotes the maximum degree of the graph. We prove the conjecture for 2‐degenerate graphs. In fact we prove a stronger bound: we prove that if G is a 2‐degenerate graph with maximum degree Δ, then a′(G)?Δ + 1. © 2010 Wiley Periodicals, Inc. J Graph Theory 69: 1–27, 2012     

Clique‐inverse graphs of K3‐free and K4‐free graphs

The clique graph K(G) of a given graph G is the intersection graph of the collection of maximal cliques of G. Given a family ℱ of graphs, the clique‐inverse graphs of ℱ are the graphs whose clique graphs belong to ℱ. In this work, we describe characterizations for clique‐inverse graphs of K₃‐free and K₄‐free graphs. The characterizations are formulated in terms of forbidden induced subgraphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 257–272, 2000     

Contractible elements in k‐connected graphs not containing some specified graphs

In 15 , Thomassen proved that any triangle‐free k‐connected graph has a contractible edge. Starting with this result, there are several results concerning the existence of contractible elements in k‐connected graphs which do not contain specified subgraphs. These results extend Thomassen's result, cf., 2 , 3 , 9 - 13 . In particular, Kawarabayashi 12 proved that any k‐connected graph without K subgraphs contains either a contractible edge or a contractible triangle. In this article, we further extend these results, and prove the following result. Let k be an integer with k ≥ 6. If G is a k‐connected graph such that G does not contain as a subgraph and G does not contain as an induced subgraph, then G has either a contractible edge which is not contained in any triangle or a contractible triangle. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:97–109, 2008     

Connected subgraphs with small degree sums in 3‐connected planar graphs

It is well‐known that every planar graph has a vertex of degree at most five. Kotzig proved that every 3‐connected planar graph has an edge xy such that deg(x) + deg (y) ≤ 13. In this article, considering a similar problem for the case of three or more vertices that induce a connected subgraph, we show that, for a given positive integer t, every 3‐connected planar graph G with |V(G)| ≥ t has a connected subgraph H of order t such that Σ_x∈V(H) deg_G(x) ≤ 8t − 1. As a tool for proving this result, we consider decompositions of 3‐connected planar graphs into connected subgraphs of order at least t and at most 2t − 1. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 191–203, 1999     

Spanning subgraphs of graphs partitioned into two isomorphic pieces

A graph has the neighbor‐closed‐co‐neighbor, or ncc property, if for each of its vertices x, the subgraph induced by the neighbor set of x is isomorphic to the subgraph induced by the closed non‐neighbor set of x. As proved by Bonato and Nowakowski [ 5 ], graphs with the ncc property are characterized by the existence of perfect matchings satisfying certain local conditions. In the present article, we investigate the spanning subgraphs of ncc graphs, which we name sub‐ncc. Several equivalent characterizations of finite sub‐ncc graphs are given, along with a polynomial time algorithm for their recognition. The infinite sub‐ncc graphs are characterized, and we demonstrate the existence of a countable universal sub‐ncc graph satisfying a strong symmetry condition called pseudo‐homogeneity. © 2005 Wiley Periodicals, Inc. J Graph Theory     

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     

Parity Linkage and the Erdős–Pósa Property of Odd Cycles through Prescribed Vertices in Highly Connected Graphs

We show the following for every sufficiently connected graph G , any vertex subset S of G , and given integer k : there are k disjoint odd cycles in G each containing a vertex of S or there is set X of at most vertices such that does not contain any odd cycle that contains a vertex of S . We prove this via an extension of Kawarabayashi and Reed's result about parity‐k‐linked graphs (Combinatorica 29, 215–225). From this result, it is easy to deduce several other well‐known results about the Erd?s–Pósa property of odd cycles in highly connected graphs. This strengthens results due to Thomassen (Combinatorica 21, 321–333), and Rautenbach and Reed (Combinatorica 21, 267–278), respectively.     

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     

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     

On an anti‐Ramsey problem of Burr,Erdős,Graham, and T. Sós

Given a graph L, in this article we investigate the anti‐Ramsey number χ_S(n,e,L), defined to be the minimum number of colors needed to edge‐color some graph G(n,e) with n vertices and e edges so that in every copy of L in G all edges have different colors. We call such a copy of L totally multicolored (TMC). In 7 among many other interesting results and problems, Burr, Erd?s, Graham, and T. Sós asked the following question: Let L be a connected bipartite graph which is not a star. Is it true then that In this article, we prove a slightly weaker statement, namely we show that the statement is true if L is a connected bipartite graph, which is not a complete bipartite graph. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 147–156, 2006