An edge of a 5-connected graph is said to be 5-removable (resp. 5-contractible) if the removal (resp. the contraction) of the edge results in a 5-connected graph. A 5-connected graph with neither 5-removable edges nor 5-contractible edges is said to be minimally contraction-critically 5-connected. We show the average degree of every minimally contraction-critically 5-connected graph is less than . This bound is sharp in the sense that for any positive real number ε, there is a minimally contraction-critically 5-connected graph whose average degree is greater than .

A graph G is 1-Hamilton-connected if is Hamilton-connected for every vertex . In the article, we introduce a closure concept for 1-Hamilton-connectedness in claw-free graphs. If is a (new) closure of a claw-free graph G, then is 1-Hamilton-connected if and only if G is 1-Hamilton-connected, is the line graph of a multigraph, and for some , is the line graph of a multigraph with at most two triangles or at most one double edge. As applications, we prove that Thomassen's Conjecture (every 4-connected line graph is hamiltonian) is equivalent to the statement that every 4-connected claw-free graph is 1-Hamilton-connected, and we present results showing that every 5-connected claw-free graph with minimum degree at least 6 is 1-Hamilton-connected and that every 4-connected claw-free and hourglass-free graph is 1-Hamilton-connected.

Isaak posed the following problem. Suppose T is a tournament having a minimum feedback arc set, which induces an acyclic digraph with a hamiltonian path. Is it true that the maximum number of arc-disjoint cycles in T equals the cardinality of minimum feedback arc set of T? We prove that the answer to the problem is in the negative.

Let denote Turán's graph—the complete 2-partite graph on n vertices with partition sizes as equal as possible. We show that for all , the graph has more proper vertex colorings in at most 4 colors than any other graph with the same number of vertices and edges.

A 4-wheel is a graph formed by a cycle C and a vertex not in C that has at least four neighbors in C. We prove that a graph G that does not contain a 4-wheel as a subgraph is 4-colorable and we describe some structural properties of such a graph.

In [2], on page 252 the following logical terminal inexactitude was made: “...the existence of a K₄ is the only obstruction. That is, every finite K₄-free graph can be represented by odd-distances in the plane.” In this note we correct this erroneous claim by showing that W₅, the 5-wheel, see Figure 1, is not a subgraph of .

We prove that every tournament with minimum out-degree at least contains k disjoint 3-cycles. This provides additional support for the conjecture by Bermond and Thomassen that every digraph D of minimum out-degree contains k vertex disjoint cycles. We also prove that for every , when k is large enough, every tournament with minimum out-degree at least contains k disjoint cycles. The linear factor 1.5 is best possible as shown by the regular tournaments.

In 1988, Chvátal and Sbihi (J Combin Theory Ser B 44(2) (1988), 154–176) proved a decomposition theorem for claw-free perfect graphs. They showed that claw-free perfect graphs either have a clique-cutset or come from two basic classes of graphs called elementary and peculiar graphs. In 1999, Maffray and Reed (J Combin Theory Ser B 75(1) (1999), 134–156) successfully described how elementary graphs can be built using line-graphs of bipartite graphs using local augmentation. However, gluing two claw-free perfect graphs on a clique does not necessarily produce claw-free graphs. In this article, we give a complete structural description of claw-free perfect graphs. We also give a construction for all perfect circular interval graphs.

We consider the problem of determining the maximum induced density of a graph H in any graph on n vertices. The limit of this density as n tends to infinity is called the inducibility of H. The exact value of this quantity is known only for a handful of small graphs and a specific set of complete multipartite graphs. Answering questions of Brown–Sidorenko and Exoo, we determine the inducibility of K_{1, 1, 2} and the paw graph. The proof is obtained using semidefinite programming techniques based on a modern language of extremal graph theory, which we describe in full detail in an accessible setting.

In 1966, Gallai conjectured that for any simple, connected graph G having n vertices, there is a path-decomposition of G having at most paths. In this article, we show that for any simple graph G having girth , there is a path-decomposition of G having at most paths, where is the number of vertices of odd degree in G and is the number of nonisolated vertices of even degree in G.

Given a configuration of indistinguishable pebbles on the vertices of a connected graph G on n vertices, a pebbling move is defined as the removal of two pebbles from some vertex, and the placement of one pebble on an adjacent vertex. The m-pebbling number of a graph G, , is the smallest integer k such that for each vertex v and each configuration of k pebbles on G there is a sequence of pebbling moves that places at least m pebbles on v. When , it is simply called the pebbling number of a graph. We prove that if G is a graph of diameter d and are integers, then , where denotes the size of the smallest distance k dominating set, that is the smallest subset of vertices such that every vertex is at most distance k from the set, and, . This generalizes the work of Chan and Godbole (Discrete Math 208 (2008), 15–23) who proved this formula for . As a corollary, we prove that . Furthermore, we prove that if d is odd, then , which in the case of answers for odd d, up to a constant additive factor, a question of Bukh (J Graph Theory 52 (2006), 353–357) about the best possible bound on the pebbling number of a graph with respect to its diameter.

We study the degree-diameter problem for claw-free graphs and 2-regular hypergraphs. Let be the largest order of a claw-free graph of maximum degree Δ and diameter D. We show that , where , for any D and any even . So for claw-free graphs, the well-known Moore bound can be strengthened considerably. We further show that for with (mod 4). We also give an upper bound on the order of -free graphs of given maximum degree and diameter for . We prove similar results for the hypergraph version of the degree-diameter problem. The hypergraph Moore bound states that the order of a hypergraph of maximum degree Δ, rank k, and diameter D is at most . For 2-regular hypergraph of rank and any diameter D, we improve this bound to , where . Our construction of claw-free graphs of diameter 2 yields a similar result for hypergraphs of diameter 2, degree 2, and any even rank .

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.

A cograph is a graph that contains no path on four vertices as an induced subgraph. A cograph k-partition of a graph G = (V,E) is a vertex partition of G into k sets V₁, …, V_k ⊂ V so that the graph induced by V_i is a cograph for 1 ≤ i ≤ k. Gimbel and Nešetřil [5] studied the complexity aspects of the cograph k-partitions and raised the following questions: Does there exist a triangle-free planar graph that is not cograph 2-partitionable? If the answer is yes, what is the complexity of the associated decision problem? In this article, we prove that such an example exists and that deciding whether a triangle-free planar graph admits a cograph 2-partition is NP-complete. We also show that every graph with maximum average degree at most ??? admits a cograph 2-partition such that each component is a star on at most three vertices.

In Math Program 55(1992), 129–168, Conforti and Rao conjectured that every balanced bipartite graph contains an edge that is not the unique chord of a cycle. We prove this conjecture for balanced bipartite graphs that do not contain a cycle of length 4 (also known as linear balanced bipartite graphs), and for balanced bipartite graphs whose maximum degree is at most 3. We in fact obtain results for more general classes, namely linear balanceable and subcubic balanceable graphs. Additionally, we prove that cubic balanced graphs contain a pair of twins, a result that was conjectured by Morris, Spiga, and Webb in ( Discrete Math 310(2010), 3228–3235).

For a graph G, let be the maximum number of vertices of G that can be colored whenever each vertex of G is given t permissible colors. Albertson, Grossman, and Haas conjectured that if G is s-choosable and , then . In this article, we consider the online version of this conjecture. Let be the maximum number of vertices of G that can be colored online whenever each vertex of G is given t permissible colors online. An analog of the above conjecture is the following: if G is online s-choosable and then . This article generalizes some results concerning partial list coloring to online partial list coloring. We prove that for any positive integers , . As a consequence, if s is a multiple of t, then . We also prove that if G is online s-choosable and , then and for any , .

Let be nonnegative integers. A graph G is -colorable if its vertex set can be partitioned into sets such that the graph induced by has maximum degree at most d for , while the graph induced by is an edgeless graph for . In this article, we give two real-valued functions and such that any graph with maximum average degree at most is -colorable, and there exist non--colorable graphs with average degree at most . Both these functions converge (from below) to when d tends to infinity. This implies that allowing a color to be d-improper (i.e., of type ) even for a large degree d increases the maximum average degree that guarantees the existence of a valid coloring only by 1. Using a color of type (even with a very large degree d) is somehow less powerful than using two colors of type (two stable sets).

We construct an infinite family of uniquely hamiltonian graphs of minimum degree 4, maximum degree 14, and of arbitrarily high maximum degree.

For every d and k, we determine the smallest order of a vertex-transitive graph of degree d and diameter k, and in each such case we show that this order is achieved by a Cayley graph.

Let denote the hypergraph consisting of two triples on four points. For an integer n, let denote the smallest integer d so that every 3-uniform hypergraph G of order n with minimum pair-degree contains vertex-disjoint copies of . Kühn and Osthus (J Combin Theory, Ser B 96(6) (2006), 767–821) proved that holds for large integers n. Here, we prove the exact counterpart, that for all sufficiently large integers n divisible by 4,

A main ingredient in our proof is the recent “absorption technique” of Rödl, Ruciński, and Szemerédi (J. Combin. Theory Ser. A 116(3) (2009), 613–636).

The total domination number of a graph G is the minimum cardinality of a set S of vertices, so that every vertex of G is adjacent to a vertex in S. In this article, we determine an optimal upper bound on the total domination number of a graph with diameter 2. We show that for every graph G on n vertices with diameter 2, . This bound is optimal in the sense that given any , there exist graphs G with diameter 2 of all sufficiently large even orders n such that .

Given a graph G and a positive integer k, define the Gallai–Ramsey number to be the minimum number of vertices n such that any k-edge coloring of contains either a rainbow (all different colored) triangle or a monochromatic copy of G. In this work, we improve upon known upper bounds on the Gallai–Ramsey numbers for paths and cycles. All these upper bounds now have the best possible order of magnitude as functions of k.

The Erdös–Hajnal conjecture states that for every graph H, there exists a constant such that every graph G with no induced subgraph isomorphic to H has either a clique or a stable set of size at least . This article is a survey of some of the known results on this conjecture.

This article intends to study some functors from the category of graphs to itself such that, for any graph G, the circular chromatic number of is determined by that of G. In this regard, we investigate some coloring properties of graph powers. We show that provided that . As a consequence, we show that if , then . In particular, and has no subgraph with circular chromatic number equal to . This provides a negative answer to a question asked in (X. Zhu, Discrete Math, 229(1–3) (2001), 371–410). Moreover, we investigate the nth multichromatic number of subdivision graphs. Also, we present an upper bound for the fractional chromatic number of subdivision graphs. Precisely, we show that .

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.

Given an undirected graph and an integer , we consider the problem of augmenting G by a minimum set of new edges so that the diameter becomes at most D. It is known that no constant factor approximation algorithms to this problem with an arbitrary graph G can be obtained unless , while the problem with only a few graph classes such as forests is approximable within a constant factor. In this article, we give the first constant factor approximation algorithm to the problem with an outerplanar graph G. We also show that if the target diameter D is even, then the case where G is a partial 2-tree is also approximable within a constant.

Unitary graphs are arc-transitive graphs with vertices the flags of Hermitian unitals and edges defined by certain elements of the underlying finite fields. They played a significant role in a recent classification of a class of arc-transitive graphs that admit an automorphism group acting imprimitively on the vertices. In this article, we prove that all unitary graphs are connected of diameter two and girth three. Based on this, we obtain, for any prime power , a lower bound of order on the maximum number of vertices in an arc-transitive graph of degree and diameter two.

A function between graphs is k-to-1 if each point in the codomain has precisely k preimages in the domain. In this article, we approach the topic of continuous, or finitely discontinuous, k-to-1 functions between graphs from three different points of view. Harrold (Duke Math J 5 (1939), 789–793) showed that there is no 2-to-1 continuous function from a closed interval onto a circle (i.e., from K₂ onto C₃). In the first part of this article, we describe all 3-to-1 continuous functions from an edge onto a cycle. Such a description is just one step away from a description of all 3-to-1 continuous functions from onto , which is in fact our main initial emphasis. Second, given two graphs, G and H, and an integer , and considering G and H as subsets of , Jo Heath gave a simple criterion for the existence of a finitely discontinuous k-to-1 function from G onto H. Such functions often involve a limiting construction which we call a wiggle. In the second part of this article, we give a simple formula (related to Jo Heath's construction) which counts the number of wiggles. The question of whether there is a continuous k-to-1 function (i.e., a k-to-1 map in the usual topological sense) from G onto H is more complicated. In the third part of this article, we consider complete graphs and . In the cases where n and m have the same parity, and , then we determine exactly when there is a k-to-1 continuous function from onto . Other cases are considered elsewhere (J. K. Dugdale, S. Fiorini, A. J. W. Hilton, J. B. Gauci, Discrete Math 310 (2010), 330–346 and J. B. Gauci, A. J. W. Hilton, J Graph Theory 65 (2010), 35–60).

An antimagic labeling of a graph G is a one-to-one correspondence between and such that the sum of the labels assigned to edges incident to distinct vertices are different. If G has an antimagic labeling, then we say G is antimagic. This article proves that cubic graphs are antimagic.

Let M be a map on a closed surface F² and suppose that each country of the map has at most r disjoint connected regions. Such a map is called an r-pire map on F². In 1890, Heawood proved that the countries of M can be properly colored with colors, where ε is the Euler characteristic of F². Also, he conjectured that this is best possible except for the case , and prove for the case (2, 2). In 1959, Ringel proved the conjecture for the case where F² is the torus and . In 1980 and 1981, Taylor proved it for the cases (2, 3), (2, 4), and where F² is the torus. In 1983 and 1984, Jackson and Ringel proved it for the cases where F² are the projective plane and the sphere. The case where F² is the Klein bottle was resolved for by Jackson and Ringel in 1985 and for by Borodin in 1989. We call a graph on F² an even embedding if it has no faces of boundary length odd. In this paper, we consider the r-pire maps whose dual graphs are even embedding on F² and prove that it can be properly colored with colors. Moreover, we conjecture that this is best possible except for the cases . We prove it for the cases with .

For a loopless multigraph G, the fractional arboricity Arb(G) is the maximum of over all subgraphs H with at least two vertices. Generalizing the Nash-Williams Arboricity Theorem, the Nine Dragon Tree Conjecture asserts that if , then G decomposes into forests with one having maximum degree at most d. The conjecture was previously proved for ; we prove it for and when and . For , we can further restrict one forest to have at most two edges in each component.

For general , we prove weaker conclusions. If , then implies that G decomposes into k forests plus a multigraph (not necessarily a forest) with maximum degree at most d. If , then implies that G decomposes into forests, one having maximum degree at most d. Our results generalize earlier results about decomposition of sparse planar graphs.

An -factor of a graph G is defined to be a spanning subgraph F of G such that each vertex has a degree belonging to the set in F, where . In this article, we investigate -factors of graphs by using Lovász's structural descriptions to the degree prescribed subgraph problem. We find some sufficient conditions for the existence of an -factor of a graph. In particular, we make progress on the characterization problem for a special family of graphs proposed by Cui and Kano in 1988.

For an integer s ≥ 0, a graph G is s-hamiltonian if for any vertex subset with |S^′| ≤ s, G - S^′ is hamiltonian. It is well known that if a graph G is s-hamiltonian, then G must be (s+2)-connected. The converse is not true, as there exist arbitrarily highly connected nonhamiltonian graphs. But for line graphs, we prove that when s ≥ 5, a line graph is s-hamiltonian if and only if it is (s+2)-connected.

A classification of connected vertex-transitive cubic graphs of square-free order is provided. It is shown that such graphs are well-characterized metacirculants (including dihedrants, generalized Petersen graphs, Möbius bands), or Tutte's 8-cage, or graphs arisen from simple groups PSL(2, p).

A graph G is equitably k-choosable if for every k-list assignment L there exists an L-coloring of G such that every color class has at most vertices. We prove results toward the conjecture that every graph with maximum degree at most r is equitably -choosable. In particular, we confirm the conjecture for and show that every graph with maximum degree at most r and at least r³ vertices is equitably -choosable. Our proofs yield polynomial algorithms for corresponding equitable list colorings.

Let denote the set of lengths of cycles of a graph G of order n and let denote the complement of G. We show that if , then contains all odd ℓ with and all even ℓ with , where and denote the maximum odd and the maximum even integer in , respectively. From this we deduce that the set contains at least integers, which is sharp.

Two n-vertex hypergraphs G and H pack, if there is a bijection such that for every edge , the set is not an edge in H. Extending a theorem by Bollobás and Eldridge on graph packing to hypergraphs, we show that if and n-vertex hypergraphs G and H with with no edges of size 0, 1, and n do not pack, then either

1. one of G and H contains a spanning graph-star, and each vertex of the other is contained in a graph edge, or
2. one of G and H has edges of size not containing a given vertex, and for every vertex x of the other hypergraph some edge of size does not contain x.

The Caccetta–Häggkvist conjecture developed in 1978 asserts that every oriented graph on n vertices without oriented cycles of length must contain a vertex of outdegree at most . It has a rather elaborate set of (conjectured) extremal configurations. In this paper, we consider the case that received quite a significant attention in the literature. We identify three oriented graphs on four vertices each that are missing as an induced subgraph in all known extremal examples and prove the Caccetta–Häggkvist conjecture for oriented graphs missing as induced subgraphs any of these oriented graphs, along with . Using a standard method, we can also lift the restriction of being induced, though this makes graphs in our list slightly more complicated.

We prove that connected Cayley graphs of valency at least 3 on abelian groups are even edge-pancyclic and have cycles of every possible odd length bigger than or equal to the odd girth.

Projective cubes are obtained by identifying antipodal vertices of hypercubes. We introduce a general problem of mapping planar graphs into projective cubes. This question, surprisingly, captures several well-known theorems and conjectures in the theory of planar graphs. As a special case , we prove that the Clebsch graph, a triangle-free graph on 16 vertices, is the smallest triangle-free graph to which every triangle-free planar graph admits a homomorphism.

We prove that if G is a 5-connected graph embedded on a surface Σ (other than the sphere) with face-width at least 5, then G contains a subdivision of K₅. This is a special case of a conjecture of P. Seymour, that every 5-connected nonplanar graph contains a subdivision of K₅. Moreover, we prove that if G is 6-connected and embedded with face-width at least 5, then for every v ∈ V(G), G contains a subdivision of K₅ whose branch vertices are v and four neighbors of v.

We show that a number of conditions on oriented graphs, all of which are satisfied with high probability by randomly oriented graphs, are equivalent. These equivalences are similar to those given by Chung, Graham, and Wilson [5] in the case of unoriented graphs, and by Chung and Graham [3] in the case of tournaments. Indeed, our main theorem extends to the case of a general underlying graph G, the main result of [3] which corresponds to the case that G is complete. One interesting aspect of these results is that exactly two of the four orientations of a four cycle can be used for a quasi-randomness condition, i.e., if the number of appearances they make in D is close to the expected number in a random orientation of the same underlying graph, then the same is true for every small oriented graph H.

A graph G is called -vertex stable if G contains a subgraph isomorphic to H even after removing any k of its vertices. By stab we denote the minimum size among the sizes of all -vertex stable graphs. Given an integer , we prove that, apart of some small values of k, stab. This confirms in the affirmative the conjecture of Dudek et al. [Discuss Math Graph Theory 28(1) (2008), 137–149]. Furthermore, we characterize the extremal graphs.

An -coloring of a cubic graph G is an edge coloring of G by points of a Steiner triple system such that the colors of any three edges meeting at a vertex form a block of . A Steiner triple system that colors every simple cubic graph is said to be universal. It is known that every nontrivial point-transitive Steiner triple system that is neither projective nor affine is universal. In this article, we present the following results.

1. We give a sufficient condition for a Steiner triple system to be universal.
2. With the help of this condition we identify an infinite family of universal point-intransitive Steiner triple systems that contain no proper universal subsystem. Only one such system was previously known.
3. We construct an infinite family of non-universal Steiner triple systems none of which is either projective or affine, disproving a conjecture made by Holroyd and Škoviera (J Combin Theory Ser B 91 (2004), 57–66).

It is proved that a graph does not contain an octahedron minor if and only if it is constructed from and five other internally 4-connected graphs by 0-, 1-, 2-, and 3-sums.

We construct (resp. ) index one current graphs with current group such that the current graphs have different underlying graphs and generate nonisomorphic orientable (resp. nonorientable) quadrangular embeddings of the complete graph , (resp. ).

A sequence is a repetition. A sequence S is nonrepetitive, if no subsequence of consecutive terms of S is a repetition. Let G be a plane graph. That is, a planar graph with a fixed embedding in the plane. A facial path consists of consecutive vertices on the boundary of a face. A facial nonrepetitive vertex coloring of a plane graph G is a vertex coloring such that the colors assigned to the vertices of any facial path form a nonrepetitive sequence. Let denote the minimum number of colors of a facial nonrepetitive vertex coloring of G. Harant and Jendrol’ conjectured that can be bounded from above by a constant. We prove that for any plane graph G.

Gallai-colorings of complete graphs—edge colorings such that no triangle is colored with three distinct colors—occur in various contexts such as the theory of partially ordered sets (in Gallai's original paper), information theory and the theory of perfect graphs. A basic property of Gallai-colorings with at least three colors is that at least one of the color classes must span a disconnected graph. We are interested here in whether this or a similar property remains true if we consider colorings that do not contain a rainbow copy of a fixed graph F. We show that such graphs F are very close to bipartite graphs, namely, they can be made bipartite by the removal of at most one edge. We also extend Gallai's property for two infinite families and show that it also holds when F is a path with at most six vertices. © 2012 Wiley Periodicals, Inc. J. Graph Theory 00: 1-11, 2012

In this article, we study problems where one has to prove that certain graph parameter attains its maximum at the star and its minimum at the path among the trees on a fixed number of vertices. We give many applications of the so-called generalized tree shift which seems to be a powerful tool to attack the problems of the above-mentioned kind. We show that the generalized tree shift increases the largest eigenvalue of the adjacency matrix and Laplacian matrix, decreases the coefficients of the characteristic polynomials of these matrices in absolute value. We will prove similar theorems for the independence polynomial and the edge cover polynomial. The generalized tree shift induces a partially ordered set on trees having fixed number of vertices. The smallest element of this poset is the path, largest element is the star. Hence, the above-mentioned results imply the extremality of the path and the star for these parameters. © 2012 Wiley Periodicals, Inc. J. Graph Theory 00: 1-23, 2012

If is a subclass of the class of claw-free graphs, then is said to be stable if, for any , the local completion of G at any vertex is also in . If is a closure operation that turns a claw-free graph into a line graph by a series of local completions and is stable, then for any . In this article, we study stability of hereditary classes of claw-free graphs defined in terms of a family of connected closed forbidden subgraphs. We characterize line graph preimages of graphs in families that yield stable classes, we identify minimal families that yield stable classes in the finite case, and we also give a general background for techniques for handling unstable classes by proving that their closure may be included into another (possibly stable) class.

We prove that a regular tournament with n vertices has more than pairwise arc-disjoint directed triangles. On the other hand, we construct regular tournaments with a feedback arc set of size less than , so these tournaments do not have pairwise arc-disjoint triangles.

The total embedding polynomial of a graph G is the bivariate polynomial

where is the number of embeddings, for into the orientable surface , and is the number of embeddings, for into the nonorientable surface . The sequence is called the total embedding distribution of the graph G; it is known for relatively few classes of graphs, compared to the genus distribution . The circular ladder graph is the Cartesian product of the complete graph on two vertices and the cycle graph on n vertices. In this article, we derive a closed formula for the total embedding distribution of circular ladders.

The bull is a graph consisting of a triangle and two vertex-disjoint pendant edges. A graph is called bull-free if no induced subgraph of it is a bull. A graph G is perfect if for every induced subgraph H of G, the chromatic number of H equals the size of the largest complete subgraph of H. This article describes the structure of all bull-free perfect graphs.

An identifying code of a graph is a subset of its vertices such that every vertex of the graph is uniquely identified by the set of its neighbors within the code. We study the edge-identifying code problem, i.e. the identifying code problem in line graphs. If denotes the size of a minimum identifying code of an identifiable graph G, we show that the usual bound , where n denotes the order of G, can be improved to in the class of line graphs. Moreover, this bound is tight. We also prove that the upper bound , where is the line graph of G, holds (with two exceptions). This implies that a conjecture of R. Klasing, A. Kosowski, A. Raspaud, and the first author holds for a subclass of line graphs. Finally, we show that the edge-identifying code problem is NP-complete, even for the class of planar bipartite graphs of maximum degree 3 and arbitrarily large girth.

Let denote the maximum number of edges in a graph having n vertices and exactly p perfect matchings. For fixed p, Dudek and Schmitt showed that for some constant when n is at least some constant . For , they also determined and . For fixed p, we show that the extremal graphs for all n are determined by those with vertices. As a corollary, a computer search determines and for . We also present lower bounds on proving that for (as conjectured by Dudek and Schmitt), and we conjecture an upper bound on . Our structural results are based on Lovász's Cathedral Theorem.

In this article, we consider Vizing's 2-Factor Conjecture which claims that any Δ-critical graph has a 2-factor, and show that if G is a Δ-critical graph with n vertices satisfying , then G is Hamiltonian and thus G has a 2-factor. Meanwhile in this article, we also consider long cycles of overfull critical graphs and obtain that if G is an overfull Δ-critical graph with n vertices, then the circumference of G is at least min.© 2012 Wiley Periodicals, Inc. J. Graph Theory 00: 1-14, 2012

An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index of G is the smallest integer k such that G has an acyclic edge coloring using k colors. Fiamik (Math. Slovaca 28 (1978), 139–145) and later Alon et al. (J Graph Theory 37 (2001), 157–167) conjectured that for any simple graph G with maximum degree Δ. In this article, we confirm this conjecture for planar graphs of girth at least 4.© 2012 Wiley Periodicals, Inc. J. Graph Theory 00: 1-14, 2012

We construct a family of r-graphs having a minimum 1-factor cover of cardinality (disproving a conjecture of Bonisoli and Cariolaro, Birkhäuser, Basel, 2007, 73–84). Furthermore, we show the equivalence between the statement that is the best possible upper bound for the cardinality of a minimum 1-factor cover of an r-graph and the well-known generalized Berge–Fulkerson conjecture.

In this article, we obtain two new characterizations of circular-arc bigraphs. One of them is the representation of a circular-arc bigraph in terms of two two-clique circular-arc graphs while another one represents the same as a union of an interval bigraph and a Ferrers bigraph. Finally, we introduce the notions of proper and unit circular-arc bigraphs, characterize them and show that, as in the case of circular-arc graphs, unit circular-arc bigraphs form a proper subclass of the class of proper circular-arc bigraphs.

For a multigraph G, the integer round-up of the fractional chromatic index provides a good general lower bound for the chromatic index . For an upper bound, Kahn 1996 showed that for any real there exists a positive integer N so that whenever . We show that for any multigraph G with order n and at least one edge, ). This gives the following natural generalization of Kahn's result: for any positive reals , there exists a positive integer N so that + c whenever . We also compare the upper bound found here to other leading upper bounds.

A cycle in a tournament T is said to be even, if when walking along C, an even number of edges point in the wrong direction, that is, they are directed from to . In this short article, we show that for every fixed even integer , if close to half of the k-cycles in a tournament T are even, then T must be quasirandom.This resolves an open question raised in 1991 by Chung and Graham 1991.

In a graph G, a fire starts at some vertex. At every time step, firefighters can protect up to k vertices, and then the fire spreads to all unprotected neighbors. The k-surviving rate of G is the expectation of the proportion of vertices that can be saved from the fire, if the starting vertex of the fire is chosen uniformly at random. For a given class of graphs , we are interested in the minimum value k such that for some constant and all , (i.e., such that linearly many vertices are expected to be saved in every graph from ). In this note, we prove that for planar graphs this minimum value is at most 4, and that it is precisely 2 for triangle-free planar graphs.

This article investigates some properties of the number of subtrees of a tree with given degree sequence. These results are used to characterize trees with the given degree sequence that have the largest number of subtrees, which generalize the recent results of Kirk and Wang (SIAM J Discrete Math 22 (2008), 985–995). These trees coincide with those which were proven by Wang and independently Zhang et al. (2008) to minimize the Wiener index. We also provide a partial ordering of the extremal trees with different degree sequences, some extremal results follow as corollaries.

We study some properties of a serial (i.e., one-by-one) symmetric exchange of elements of two disjoint bases of a matroid. We show that any two elements of one base have a serial symmetric exchange with some two elements of the other base. As a result, we obtain that any two disjoint bases in a matroid of rank 4 have a full serial symmetric exchange

Let be a plane graph with the sets of vertices, edges, and faces V, E, and F, respectively. If one can color all elements in using k colors so that any two adjacent or incident elements receive distinct colors, then G is said to be entirely k-colorable. Kronk and Mitchem [Discrete Math 5 (1973) 253-260] conjectured that every plane graph with maximum degree Δ is entirely -colorable. This conjecture has now been settled in Wang and Zhu (J Combin Theory Ser B 101 (2011) 490–501), where the authors asked: is every simple plane graph entirely -colorable? In this article, we prove that every simple plane graph with is entirely -colorable, and conjecture that every simple plane graph, except the tetrahedron, is entirely -colorable.

The following theorem is proved: for all k-connected graphs G and H each with at least n vertices, the treewidth of the cartesian product of G and H is at least . For , this lower bound is asymptotically tight for particular graphs G and H. This theorem generalizes a well-known result about the treewidth of planar grid graphs.

The independence polynomial of a (finite) graph is the generating function for the number of independent sets of each cardinality. Assuming that each possible edge of a complete graph of order n is independently operational with probability p, we consider the expected independence polynomial. We show here that for all fixed , the expected independence polynomials of complete graphs have all real, simple roots.

As proved by Kahn, the chromatic number and fractional chromatic number of a line graph agree asymptotically.That is, for any line graph G, we have . We extend this result to quasi-line graphs, an important subclass of claw-free graphs. Furthermore, we prove that we can construct a coloring that achieves this bound in polynomial time, giving us an asymptotic approximation algorithm for the chromatic number of quasi-line graphs

A fundamental connection between list vertex colorings of graphs and Property B (also known as hypergraph 2-colorability) was already known to Erdős, Rubin, and Taylor ((1980), 125–157). In this article, we draw similar connections for improper list colorings. This extends results of Kostochka (Electron J Combin 9 (2002)), Alon (Combin Probab Comput 1 (1992), 107–114; (1993), 1–33; Random Structures Algorithms 16 (2000), 364–368), and Král’ and Sgall (J Graph Theory 49 (2005), 177–186) for, respectively, multipartite graphs, graphs of large minimum degree, and list assignments with bounded list union.

It was recently proved that any graph satisfying contains a stable set hitting every maximum clique. In this note, we prove that the same is true for graphs satisfying unless the graph is the strong product of an odd hole and .We also provide a counterexample to a recent conjecture on the existence of a stable set hitting every sufficiently large maximal clique.