共查询到20条相似文献,搜索用时 15 毫秒
1.
We present easily verifiable conditions, under which a graph G contains nonempty vertex-disjoint induced subgraphs G1, G2 such that G is perfect if and only if G1 and G2 are. This decomposition is defined in terms of the induced subgraphs of G that are isomorphic to the chordless path with four vertices. 相似文献
2.
C.T Hoang 《Journal of Combinatorial Theory, Series B》1985,39(3):220-232
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. 相似文献
3.
In this article, we show that every simple r‐regular graph G admits a balanced P4‐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 P4‐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 相似文献
4.
《Discrete Mathematics》2022,345(10):113012
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. 相似文献
5.
Guoli Ding 《Graphs and Combinatorics》1994,10(2-4):323-328
The P4-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 P4-structure of a tree can be recognized in polynomial time. 相似文献
6.
Annegret Wagler 《Journal of Graph Theory》1999,32(4):394-404
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 相似文献
7.
D. de Werra 《Mathematical Programming》1978,15(1):236-238
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. 相似文献
8.
Chính T. Hong 《Journal of Graph Theory》1995,19(2):271-279
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 P4 (chordless path with four vertices). Partial results on this conjecture are given in this paper. © 1995 John Wiley & Sons, Inc. 相似文献
9.
Geoffrey Pearce 《Discrete Mathematics》2009,309(12):3774-3778
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. 相似文献
10.
CHENHUAITANG MAKEJIE 《高校应用数学学报(英文版)》1998,13(2):165-170
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. 相似文献
11.
12.
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. 相似文献
13.
《Discrete Mathematics》2020,343(7):111904
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. 相似文献
14.
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 相似文献
15.
《Journal of Graph Theory》2018,88(3):434-448
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 . 相似文献
16.
Cun-Quan Zhang 《Journal of Graph Theory》1994,18(1):51-57
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 K5, then E(G) has an even circuit decomposition. 相似文献
17.
18.
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. 相似文献
19.
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 相似文献
20.
Sean McGuinness 《Combinatorica》1994,14(3):321-334
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 2/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( n ) cliques. Heret p-1( n ) 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/2. We prove this conjecture forK 4-free graphs and show that in the case of equality forC andG there are only two possibilities:
- G?K n/2,n/2
- G is complete 3-partite, where each part hasn/3 vertices.