Triangle‐free graphs that are signable without even holes

We characterize triangle‐free graphs for which there exists a subset of edges that intersects every chordless cycle in an odd number of edges (TF odd‐signable graphs). These graphs arise as building blocks of a decomposition theorem (for cap‐free odd‐signable graphs) obtained by the same authors. We give a polytime algorithm to test membership in this class. This algorithm is itself based on a decomposition theorem. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 204–220, 2000     

Nowhere‐zero 3‐flows in products of graphs

A graph G is an odd‐circuit tree if every block of G is an odd length circuit. It is proved in this paper that the product of every pair of graphs G and H admits a nowhere‐zero 3‐flow unless G is an odd‐circuit tree and H has a bridge. This theorem is a partial result to the Tutte's 3‐flow conjecture and generalizes a result by Imrich and Skrekovski [7] that the product of two bipartite graphs admits a nowhere‐zero 3‐flow. A byproduct of this theorem is that every bridgeless Cayley graph G = Cay(Γ,S) on an abelian group Γ with a minimal generating set S admits a nowhere‐zero 3‐flow except for odd prisms. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Graphs with independent perfect matchings

A graph with at least two vertices is matching covered if it is connected and each edge lies in some perfect matching. A matching covered graph G is extremal if the number of perfect matchings of G is equal to the dimension of the lattice spanned by the set of incidence vectors of perfect matchings of G. We first establish several basic properties of extremal matching covered graphs. In particular, we show that every extremal brick may be obtained by splicing graphs whose underlying simple graphs are odd wheels. Then, using the main theorem proved in 2 and 3 , we find all the extremal cubic matching covered graphs. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 19–50, 2005     

Note on Perfect Forests in Digraphs

A spanning subgraph F of a graph G is called perfect if F is a forest, the degree of each vertex x in F is odd, and each tree of F is an induced subgraph of G. Alex Scott (Graphs Combin 17 (2001), 539–553) proved that every connected graph G contains a perfect forest if and only if G has an even number of vertices. We consider four generalizations to directed graphs of the concept of a perfect forest. While the problem of existence of the most straightforward one is NP‐hard, for the three others this problem is polynomial‐time solvable. Moreover, every digraph with only one strong component contains a directed forest of each of these three generalization types. One of our results extends Scott's theorem to digraphs in a nontrivial way.     

Coloring quasi‐line graphs

A graph G is a quasi‐line graph if for every vertex v, the set of neighbors of v 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. A theorem of Shannon's implies that if G is a line graph, then it can be properly colored using no more than 3/2 ω(G) colors, where ω(G) is the size of the largest clique in G. In this article, we extend this result to all quasi‐line graphs. We also show that this bound is tight. © 2006 Wiley Periodicals, Inc. J Graph Theory     

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     

Note on Perfect Forests

A spanning subgraph F of a graph G is called perfect if F is a forest, the degree of each vertex x in F is odd, and each tree of F is an induced subgraph of G. We provide a short linear‐algebraic proof of the following theorem of A. D. Scott (Graphs Combin 17 (2001), 539–553): A connected graph G contains a perfect forest if and only if G has an even number of vertices.     

Perfect Graphs with No Balanced Skew‐Partition are 2‐Clique‐Colorable

A graph G is perfect if for all induced subgraphs H of G, . A graph G is Berge if neither G nor its complement contains an induced odd cycle of length at least five. The Strong Perfect Graph Theorem [9] states that a graph is perfect if and only if it is Berge. The Strong Perfect Graph Theorem was obtained as a consequence of a decomposition theorem for Berge graphs [M. Chudnovsky, Berge trigraphs and their applications, PhD thesis, Princeton University, 2003; M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, The strong perfect graph theorem, Ann Math 164 (2006), 51–229.], and one of the decompositions in this decomposition theorem was the “balanced skew‐partition.” A clique‐coloring of a graph G is an assignment of colors to the vertices of G in such a way that no inclusion‐wise maximal clique of G of size at least two is monochromatic, and the clique‐chromatic number of G, denoted by , is the smallest number of colors needed to clique‐color G. There exist graphs of arbitrarily large clique‐chromatic number, but it is not known whether the clique‐chromatic number of perfect graphs is bounded. In this article, we prove that every perfect graph that does not admit a balanced skew‐partition is 2‐clique colorable. The main tool used in the proof is a decomposition theorem for “tame Berge trigraphs” due to Chudnovsky et al. ( http://arxiv.org/abs/1308.6444 ).     

Strong Chromatic Index of Chordless Graphs

A strong edge coloring of a graph is an assignment of colors to the edges of the graph such that for every color, the set of edges that are given that color form an induced matching in the graph. The strong chromatic index of a graph G, denoted by , is the minimum number of colors needed in any strong edge coloring of G. A graph is said to be chordless if there is no cycle in the graph that has a chord. Faudree, Gyárfás, Schelp, and Tuza (The Strong Chromatic Index of Graphs, Ars Combin 29B (1990), 205–211) considered a particular subclass of chordless graphs, namely, the class of graphs in which all the cycle lengths are multiples of four, and asked whether the strong chromatic index of these graphs can be bounded by a linear function of the maximum degree. Chang and Narayanan (Strong Chromatic Index of 2‐degenerate Graphs, J Graph Theory, 73(2) (2013), 119–126) answered this question in the affirmative by proving that if G is a chordless graph with maximum degree Δ, then . We improve this result by showing that for every chordless graph G with maximum degree Δ, . This bound is tight up to an additive constant.     

Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms

A minimal blocker in a bipartite graph G is a minimal set of edges the removal of which leaves no perfect matching in G. We give an explicit characterization of the minimal blockers of a bipartite graph G. This result allows us to obtain a polynomial delay algorithm for finding all minimal blockers of a given bipartite graph. Equivalently, we obtain a polynomial delay algorithm for listing the anti‐vertices of the perfect matching polytope of G. We also provide generation algorithms for other related problems, including d‐factors in bipartite graphs, and perfect 2‐matchings in general graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 209–232, 2006     

Expansion properties of random Cayley graphs and vertex transitive graphs via matrix martingales

The Alon–Roichman theorem states that for every ε> 0 there is a constant c(ε), such that the Cayley graph of a finite group G with respect to c(ε)log ∣G∣ elements of G, chosen independently and uniformly at random, has expected second largest eigenvalue less than ε. In particular, such a graph is an expander with high probability. Landau and Russell, and independently Loh and Schulman, improved the bounds of the theorem. Following Landau and Russell we give a new proof of the result, improving the bounds even further. When considered for a general group G, our bounds are in a sense best possible. We also give a generalization of the Alon–Roichman theorem to random coset graphs. Our proof uses a Hoeffding‐type result for operator valued random variables, which we believe can be of independent interest. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

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     

On total 9‐coloring planar graphs of maximum degree seven

Given a graph G, a total k‐coloring of G is a simultaneous coloring of the vertices and edges of G with at most k colors. If Δ(G) is the maximum degree of G, then no graph has a total Δ‐coloring, but Vizing conjectured that every graph has a total (Δ + 2)‐coloring. This Total Coloring Conjecture remains open even for planar graphs. This article proves one of the two remaining planar cases, showing that every planar (and projective) graph with Δ ≤ 7 has a total 9‐coloring by means of the discharging method. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 67–73, 1999     

Signed degree sets in signed graphs

The set D of distinct signed degrees of the vertices in a signed graph G is called its signed degree set. In this paper, we prove that every non-empty set of positive (negative) integers is the signed degree set of some connected signed graph and determine the smallest possible order for such a signed graph. We also prove that every non-empty set of integers is the signed degree set of some connected signed graph.     

Claw‐free circular‐perfect graphs

The circular chromatic number of a graph is a well‐studied refinement of the chromatic number. Circular‐perfect graphs form a superclass of perfect graphs defined by means of this more general coloring concept. This article studies claw‐free circular‐perfect graphs. First, we prove that if G is a connected claw‐free circular‐perfect graph with χ(G)>ω(G), then min{α(G), ω(G)}=2. We use this result to design a polynomial time algorithm that computes the circular chromatic number of claw‐free circular‐perfect graphs. A consequence of the strong perfect graph theorem is that minimal imperfect graphs G have min{α(G), ω(G)}=2. In contrast to this result, it is shown in Z. Pan and X. Zhu [European J Combin 29(4) (2008), 1055–1063] that minimal circular‐imperfect graphs G can have arbitrarily large independence number and arbitrarily large clique number. In this article, we prove that claw‐free minimal circular‐imperfect graphs G have min{α(G), ω(G)}≤3. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 163–172, 2010     

Quasi‐Random Oriented Graphs

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.     

K4‐free graphs with no odd hole: Even pairs and the circular chromatic number

An odd hole in a graph is an induced cycle of odd length at least five. In this article we show that every imperfect K₄‐free graph with no odd hole either is one of two basic graphs, or has an even pair or a clique cutset. We use this result to show that every K₄‐free graph with no odd hole has circular chromatic number strictly smaller than 4. We also exhibit a sequence {H_n} of such graphs with lim_n→∞χ_c(H_n)=4. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 303–322, 2010     

Odd 4‐edge‐colorability of graphs

An odd k‐edge‐coloring of a graph G is a (not necessarily proper) edge‐coloring with at most k colors such that each nonempty color class induces a graph in which every vertex is of odd degree. Pyber (1991) showed that every simple graph is odd 4‐edge‐colorable, and Lužar et al. (2015) showed that connected loopless graphs are odd 5‐edge‐colorable, with one particular exception that is odd 6‐edge‐colorable. In this article, we prove that connected loopless graphs are odd 4‐edge‐colorable, with two particular exceptions that are respectively odd 5‐ and odd 6‐edge‐colorable. Moreover, a color class can be reduced to a size at most 2.     

Resilience of perfect matchings and Hamiltonicity in random graph processes

Let {G_i} be the random graph process: starting with an empty graph G₀ with n vertices, in every step i ≥ 1 the graph G_i is formed by taking an edge chosen uniformly at random among the nonexisting ones and adding it to the graph G_{i ? 1}. The classical “hitting‐time” result of Ajtai, Komlós, and Szemerédi, and independently Bollobás, states that asymptotically almost surely the graph becomes Hamiltonian as soon as the minimum degree reaches 2, that is if δ(G_i) ≥ 2 then G_i is Hamiltonian. We establish a resilience version of this result. In particular, we show that the random graph process almost surely creates a sequence of graphs such that for edges, the 2‐core of the graph G_m remains Hamiltonian even after an adversary removes ‐fraction of the edges incident to every vertex. A similar result is obtained for perfect matchings.     

The circular chromatic number of series‐parallel graphs

In this article, we consider the circular chromatic number χ_c(G) of series‐parallel graphs G. It is well known that series‐parallel graphs have chromatic number at most 3. Hence, their circular chromatic numbers are at most 3. If a series‐parallel graph G contains a triangle, then both the chromatic number and the circular chromatic number of G are indeed equal to 3. We shall show that if a series‐parallel graph G has girth at least 2 ⌊(3k − 1)/2⌋, then χ_c(G) ≤ 4k/(2k − 1). The special case k = 2 of this result implies that a triangle free series‐parallel graph G has circular chromatic number at most 8/3. Therefore, the circular chromatic number of a series‐parallel graph (and of a K₄‐minor free graph) is either 3 or at most 8/3. This is in sharp contrast to recent results of Moser [5] and Zhu [14], which imply that the circular chromatic number of K₅‐minor free graphs are precisely all rational numbers in the interval [2, 4]. We shall also construct examples to demonstrate the sharpness of the bound given in this article. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 14–24, 2000