On the P4-structure of perfect graphs I. Even decompositions

We present easily verifiable conditions, under which a graph G contains nonempty vertex-disjoint induced subgraphs G₁, G₂ such that G is perfect if and only if G₁ and G₂ are. This decomposition is defined in terms of the induced subgraphs of G that are isomorphic to the chordless path with four vertices.     

On the P4-structure of perfect graphs. II. Odd decompositions

We prove that a graph is perfect if its vertices can be coloured by two colours in such a way that each induced chordless path with four vertices has an odd number of vertices of each colour. Using this result, we prove a decomposition theorem for perfect graphs; this theorem is defined in terms of the chordless path with four vertices.     

P4‐decompositions of regular graphs

In this article, we show that every simple r‐regular graph G admits a balanced P₄‐decomposition if r ≡ 0(mod 3) and G has no cut‐edge when r is odd. We also show that a connected 4‐regular graph G admits a P₄‐decomposition if and only if |E(G)| ≡ 0(mod 3) by characterizing graphs of maximum degree 4 that admit a triangle‐free Eulerian tour. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 135–143, 1999     

On 4-connected 4-regular graphs without even cycle decompositions

An even cycle decomposition of a graph is a partition of its edges into even cycles. Markström constructed infinitely many 2-connected 4-regular graphs without even cycle decompositions. Má?ajová and Mazák then constructed an infinite family of 3-connected 4-regular graphs without even cycle decompositions. In this note, we further show that there exists an infinite family of 4-connected 4-regular graphs without even cycle decompositions.     

Recognizing the P4-structure of a tree

The P₄-structure of a graphG =(V,E) is a hypergraphH = (V,F) such that, for every hyperedgeA inF, the cardinality ofA is four and the subgraph of G induced byA is a path. It is proved in this paper that the P₄-structure of a tree can be recognized in polynomial time.     

On critically perfect graphs

A perfect graph is critical, if the deletion of any edge results in an imperfect graph. We give examples of such graphs and prove some basic properties. We relate critically perfect graphs to well-known classes of perfect graphs, investigate the structure of the class of critically perfect graphs, and study operations preserving critical perfectness. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 394–404, 1999     

On line perfect graphs

Line-perfect graphs have been defined by L.E. Trotter as graphs whose line-graphs are perfect. They are characterized by the property of having no elementary odd cycle of size larger than 3. L.E. Trotter showed constructively that the maximum cardinality of a set of mutually non-adjacent edges (matching) is equal to the minimum cardinality of a collection of sets of mutually adjacent edges which cover all edges.The purpose of this note is to give an algorithmic proof that the chromatic index of these graphs is equal to the maximum cardinality of a set of mutually adjacent edges.     

On the two-edge-colorings of perfect graphs

We investigate the conjecture that a graph is perfect if it admits a two-edge-coloring such that two edges receive different colors if they are the nonincident edges of a P₄ (chordless path with four vertices). Partial results on this conjecture are given in this paper. © 1995 John Wiley & Sons, Inc.     

On transitive decompositions of disconnected graphs

We investigate transitive decompositions of disconnected graphs, and show that these behave very differently from a related class of algebraic graph decompositions, known as homogeneous factorisations. We conclude that although the study of homogeneous factorisations admits a natural reduction to those cases where the graph is connected, the study of transitive decompositions does not.     

ON THE ASCENDING SUBGRAPH DECOMPOSITIONS OF REGULAR GRAPHS

The definition of the ascending suhgraph decomposition was given by Alavi. It has been conjectured that every graph of positive size has an ascending subgraph decomposition. In this paper it is proved that the regular graphs under some conditions do have an ascending subgraph decomposition.     

On kernels in perfect graphs

A kernel of a digraphD is a set of vertices which is both independent and absorbant. In 1983, C. Berge and P. Duchet conjectured that an undirected graphG is perfect if and only if the following condition is fulfilled: ifD is an orientation ofG (where pairs of opposite arcs are allowed) and if every clique ofD has a kernel thenD has a kernel. We prove here the conjecture for the complements of strongly perfect graphs and establish that a minimal counterexample to the conjecture is not a complete join of an independent set with another graph.     

On even cycle decompositions of line graphs of cubic graphs

An even cycle decomposition of a graph is a partition of its edges into cycles of even length. In 2012, Markström conjectured that the line graph of every 2-connected cubic graph has an even cycle decomposition and proved this conjecture for cubic graphs with oddness at most 2. However, for 2-connected cubic graphs with oddness 2, Markström only considered these graphs with a chordless 2-factor. (A chordless 2-factor of a graph is a 2-factor consisting of only induced cycles.) In this paper, we first construct an infinite family of 2-connected cubic graphs with oddness 2 and without chordless 2-factors. We then give a complete proof of Markström’s result and further prove this conjecture for cubic graphs with oddness 4.     

On the structure of bull-free perfect graphs

A bull is a graph obtained by adding a pendant vertex at two vertices of a triangle. Chvátal and Sbihi showed that the Strong Perfect Graph Conjecture holds for bull-free graphs. We show that bull-free perfect graphs are quasi-parity graphs, and that bull-free perfect graphs with no antihole are perfectly contractile. Our proof yields a polynomial algorithm for coloring bull-free strict quasi-parity graphsPartially supported by CNPq, grant 30 1160/91.0     

On Hamilton decompositions of infinite circulant graphs

The natural infinite analog of a (finite) Hamilton cycle is a two‐way‐infinite Hamilton path (connected spanning 2‐valent subgraph). Although it is known that every connected 2k‐valent infinite circulant graph has a two‐way‐infinite Hamilton path, there exist many such graphs that do not have a decomposition into k edge‐disjoint two‐way‐infinite Hamilton paths. This contrasts with the finite case where it is conjectured that every 2k‐valent connected circulant graph has a decomposition into k edge‐disjoint Hamilton cycles. We settle the problem of decomposing 2k‐valent infinite circulant graphs into k edge‐disjoint two‐way‐infinite Hamilton paths for , in many cases when , and in many other cases including where the connection set is or .     

On even circuit decompositions of eulerian graphs

Let G be an eulerian graph without odd block. It was proved by P. D. Seymour that if G is planar, then E(G) has a circuit decomposition F such that each circuit of F is of even length. In this paper the theorem of Seymour is generalized: If G contains no subgraph contractible to K₅, then E(G) has an even circuit decomposition.     

On regular graphs. III

A graph G is locally s-regular if for any two s-arcs of G having the same head there exists a unique automorphism of G mapping the first of these s-arcs to the second. This is a natural generalization of the concept of an s-regular graph. We extend the results of [2] concerning s-regular graphs to this wider class. We also describe an example of a locally 7-regular cubic graph which is not 7-regular.     

On the chromatic spectrum of acyclic decompositions of graphs

If G is any graph, a G‐decomposition of a host graph H = (V, E) is a partition of the edge set of H into subgraphs of H which are isomorphic to G. The chromatic index of a G‐decomposition is the minimum number of colors required to color the parts of the decomposition so that two parts which share a node get different colors. The G‐spectrum of H is the set of all chromatic indices taken on by G‐decompositions of H. If both S and T are trees, then the S‐spectrum of T consists of a single value which can be computed in polynomial time. On the other hand, for any fixed tree S, not a single edge, there is a unicyclic host whose S‐spectrum has two values, and if the host is allowed to be arbitrary, the S‐spectrum can take on arbitrarily many values. Moreover, deciding if an integer k is in the S‐spectrum of a general bipartite graph is NP‐hard. We show that if G has c > 1 components, then there is a host H whose G‐spectrum contains both 3 and 2c + 1. If G is a forest, then there is a tree T whose G‐spectrum contains both 2 and 2c. Furthermore, we determine the complete spectra of both paths and cycles with respect to matchings. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 83–104, 2007     

Restricted greedy clique decompositions and greedy clique decompositions ofK 4-free graphs

A greedy clique decomposition of a graph is obtained by removing maximal cliques from a graph one by one until the graph is empty. It has recently been shown that any greedy clique decomposition of a graph of ordern has at mostn ²/4 cliques. In this paper, we extend this result by showing that for any positive integerp, 3≤p any clique decomposisitioof a graph of ordern obtained by removing maximal cliques of order at leastp one by one until none remain, in which case the remaining edges are removed one by one, has at mostt _p-1( ⁿ ) cliques. Heret _p-1( ⁿ ) is the number of edges in the Turán graph of ordern, which has no complete subgraphs of orderp. In connection with greedy clique decompositions, P. Winkler conjectured that for any greedy clique decompositionC of a graphG of ordern the sum over the number of vertices in each clique ofC is at mostn ²/2. We prove this conjecture forK ₄-free graphs and show that in the case of equality forC andG there are only two possibilities:

1. G?K _n/2,n/2
2. G is complete 3-partite, where each part hasn/3 vertices.

We show that in either caseC is completely determined.