Discrete Geometry, Combinatorics and Graph Theory: 7th by Jin Akiyama, William Y.C. Chen, Mikio Kano, Xueliang Li,

By Jin Akiyama, William Y.C. Chen, Mikio Kano, Xueliang Li, Qinglin Yu

Show description

Read or Download Discrete Geometry, Combinatorics and Graph Theory: 7th China-Japan Conference, CJCDGCGT 2005, Tianjin, China, November 18-20, 2005, and Xi'an, China, November ... Computer Science and General Issues) PDF

Best geometry and topology books

Plane Geometry and its Groups

San Francisco 1967 Holden-Day. octavo. , 288pp. , index, hardcover. advantageous in VG DJ, a couple of small closed tears.

Extra info for Discrete Geometry, Combinatorics and Graph Theory: 7th China-Japan Conference, CJCDGCGT 2005, Tianjin, China, November 18-20, 2005, and Xi'an, China, November ... Computer Science and General Issues)

Example text

Toussaint. Quadrangulations of planar sets. In Proceedings of the 4th International Workshop on Algorithms and Data Structures, pages 218–227. SpringerVerlag, 1995. cn Abstract. Let G = (V, E) be an edge-colored graph. A matching of G is called heterochromatic if its any two edges have different colors. Unlike uncolored matchings for which the maximum matching problem is solvable in polynomial time, the maximum heterochromatic matching problem is NP-complete. This means that to find both sufficient and necessary good conditions for the existence of perfect heterochromatic matchings should be not easy.

L. L. Chia colored from the list (because |L(w) − {c1 , . . , cnk }| ≥ 1). Hence ch(G) ≤ nk + 1 so that ch(G) = nk + 1. (ii) Let A be a set of size (n − 1)k and let A be partitioned into n − 1 subsets C2 , C3 , . . , Cn each of size k. Let D2 , D3 , . . , Dn be pairwise disjoint sets each of size (n − 1)k such that Di ∩ A = Ci for each i = 2, 3, . . , n. Let Dn, k = {B = B2 ∪ B3 ∪ · · · ∪ Bn | Bi ⊆ Di , |Bi | = k, i = 2, 3, . . , n, B ∩ A = ∅} . (n−1)k n−1 k (n−1)k n−1 (n−2)k n−1 . k (n−2)k n−1 Note that respectively k k lists B2 ∪B3 ∪· · · ∪Bn where Bi ⊆ Di (respectively Then |Dn, k | = − ( ) counts the number of those Bi ⊆ Di − Ci ) and |Bi | = k, i = 2, 3, .

Theorem B. (Chen [7]) Let G be a 2-connected graph and c an integer. If max{id(u), id(v) | d(u, v) = 2} ≥ c/2, then G contains either a Hamilton cycle or a cycle of length at least c. On the other hand, Bedrossian et al. [1] gave a further generalization of Fan’s theorem. They imposed one more restriction on the pair of vertices u and v: they must be vertices of an induced claw or an induced modified claw. Theorem C. ([Bedrossian et al. [1]) Let G be a 2-connected graph and c an integer. If max{d(u), d(v)} ≥ c/2 for each pair of nonadjacent vertices u and v that are vertices of an induced claw or an induced modified claw of G, then G contains either a Hamilton cycle or a cycle of length at least c.

Download PDF sample

Rated 4.85 of 5 – based on 26 votes