※ [本文轉錄自 NTU-Exam 看板]
作者: TassTW (為文載道尊於勢) 看板: NTU-Exam
標題: [試題] 數學系　圖論一 期末考
時間: Fri Jan 13 20:15:05 2006
課程名稱︰　圖論一
課程性質︰　選修
課程教師︰　張鎮華
開課系所︰　數學系
考試時間︰　2006/01/10
試題 :
(1) (15%) Prove that every 3-regular graph with at most two cut-edge has
a 1-factor.
(1-1) (3%) What kind of condition do we need to guarantee a k-regular graph
to have a 1-factor? Why?
(2) (15%) Prove that any claw-free connected graph of even order has a
1-factor.
(3) (15%) Prove that for any simple graph G we have k(G)≦k'(G)≦δ(G).
(3-1) (3%) Is there any graph G for which k(G) = k'(G) = δ(G)?
Is there any graph G for which k(G) < k'(G) = δ(G)?
Is there any graph G for which k(G) = k'(G) < δ(G)?
Is there any graph G for which k(G) < k'(G) < δ(G)?
(4) (15%) Prove that a graph G having at least three vertices is
2-connected if and only if for each pair u,v belong to V(G) there exist
two internally disjoint u,v-paths in G.
(5) (15%) Suppose v1,v2,...,vn is an ordering of V(G). Letχ(G;v1,...,vn)
be the number of colors used in the coloring obtained by the greedy
algorithm using the vertex ordering v1, v2, ... vn. Also let
S(G) = {χ(G;v1,...,vn): v1, v2, ... ,vn is an ordering of V(G)},
and χ_max(G) (respectively, χ_min) is the maximum (respectively,
minimum) value in S. Prove that χ(G)≦χ_min(G)≦χ_max(G)≦Δ(G)+1
(5-1) (2%) Is it possible to have a graph G with χ(G) < χ_min(G)? If it is
possible, please find one. If it is impossible, prove why this is the
case.
(6) (15%) Let G be a graph having no induced subgraph isomorphic to P4.
Prove that χ(G) = χ_max(G).
(6-1) (2%) Is it possible to have a graph G with χ(G) < χ_max(G)? If it is
possible, please find one. If it is impossible, prove why this is the
case.
Is it possible to have a graph G, having an induced subgraph isomorphic
to P4, with χ(G) = χ_max(G)? If it is possible, please find one.
If it is impossible, prove why this is the case.