グラフの線形樹化数

5.5 The Linear Arboricity of
Graphs
(グラフの線形樹化数)
D3 杉原堅也
内容

線形樹化数（linear arboricity）
連結成分が全てパスの森を線形森（linear forest）と
いう．
グラフGの線形樹化数 la(G) とは，Gの全ての辺をカ
バーするような線形森の最小数．
予想 5.5.1

予想 5.5.1(線形樹化数予想) [Akiyama, Exco, Harary. ’80]
全ての d-正則グラフの線形樹化数は
 d  1
 2 .
• d-正則グラフの辺の数は nd/2, 線形森は最大 n－1 本の辺をもつから，
la (G ) 
nd
d
 .
2(n  1) 2
• 最大次数Δのグラフ G はΔ-正則グラフの部分グラフなので，この予想は
la(G) ≦ (  1) / 2 と同値．
定理 5.5.7
• 確率的な手法を使わない結果は，
la (G )  3 / 5
（Δが偶数）
la (G )  (3  2) / 5 （Δが奇数）
• 最も良い結果は，1988年の Alon の結果
  0　, 0   0 ( ),   0 , la (G)  ( 12   ).

• この節で示すのは下の結果．

定理 5.5.7
定数 c > 0 が存在し，全ての d-正則無向グラフ G が
la (G)  d / 2  cd 3 / 4 (log d )1/ 2 を満たす．
予想 5.5.2

予想 5.5.2 (有向グラフ) [Nakayama, Peroche. ’87]
全ての d-正則有向グラフ D の線形樹化数は
dla ( D)  d  1.
d-正則有向グラフ：各節点の indegree と outdegree が両方とも d．
dla (G)：有向グラフ G の線形樹化数
(⇔ G の枝を全てカバーする線形有向森の最小数)
森の連結成分が有向パス．
無向と有向の関係

2d-正則無向グラフの辺をオイラー閉路に沿って向き付
ければ，d-正則有向グラフになる．
4-正則

2-正則
d-正則有向グラフに対する予想（または，dla の上界）
⇒ 2d-正則無向グラフに対する予想（または，la の上界）
全ての(2d-1)-正則無向グラフは，ある2d-正則無向グラフの部分グラフなので，
対応する d-正則有向グラフが存在する．
定理 5.5.6

定理 5.5.6
定数 c > 0 が存在し，全ての d-正則有向グラフ G が
dla (G)  d  cd 3 / 4 (log d )1/ 2 を満たす．

定理 5.5.7（再褐）
定数 c > 0 が存在し，全ての d-正則無向グラフ G が
la (G)  d / 2  cd 3 / 4 (log d )1/ 2 を満たす．
命題 5.5.3

命題 5.5.3
H = (V, E) を最大次数 d の無向グラフ，
V  V1 V2 Vr を分割（Vi は互いに共通部分を持たない），
各Vi は|Vi|≧2ed を満たすとすると，
各Vi の節点を含む独立集合 W⊆Vが存在する．
証明


全ての Vi で | Vi | 2ed  : g となることを示せば十分．
Vi から節点を一つずつランダムに選んで W とし，W が独立
集合となる確率が正となることを示す．
命題 5.5.3の証明



辺 f に対し，Af を W が f の端点を両方含む事象と
する．明らかに，Pr(Af) ≦ 1/g2
Af は，両端点が Vi∪Vj に含まれない辺 f’ に対する
事象 Af’ と独立．
独立とならない事象は 2gd－1 個以下．
→ Corollary 5.1.2
(Local Lemma; Symmetric Case)
Vi
Vj
f
H
命題 5.5.3の証明

Corollary 5.1.2
A1, A2, ..., An を事象とする．
各 Ai が他の高々 d 個以外の事象と独立で，
Pr(Ai) ≦ p (1 ≦ i ≦ n)の時，
n
ep(d+1) ≦ 1 ならば Pr( Ai )  0.
i 1
上の p, d に前スライドで得られたものを代入すると，
e(2 gd ) / g 2  2ed / 2ed   1
従って，全てのAf が起こらない確率（W が独立）は正．
定理 5.5.4

定理 5.5.4
G = (U, F ) が d-正則有向グラフで，有向内周 g が g ≧ 8ed を
満たすとすると， dla (G )  d  1.
(有向)内周：最小な(有向)閉路の長さ
|F| = d|U| ，有向線形木は高々|U|－1 本の辺をもつので，
d
dla (G)  |U|U||1
d
dla (G)  d  1 を示す．
定理 5.5.4の証明

辺集合 F は d 個の disjoint な 1-正則の全域部分グ
ラフに分割することができる．
1-正則な全域部分グラフ：連結成分が有向閉路．
2-正則
定理 5.5.4の証明

辺集合 F は d 個の disjoint な 1-正則の全域部分グ
ラフに分割することができる．
1-正則な全域部分グラフ：連結成分が有向閉路．
2-正則
それぞれの閉路から一つずつうまく辺を選び，線形森を作れば d+1 個の線形木で
分割できることを示せる．
実際には，マッチングとなるように辺を選べる．
定理 5.5.4の証明


G=(U, F)の線グラフ (節点集合がFで，Gで同じ節点を共有し
ていた f, f’ ∈ F の間に辺があるグラフ)をつくる．
Gのマッチング ⇔ 線グラフの独立集合
2-正則
線グラフ
定理 5.5.4の証明

命題 5.5.3（再褐）
H = (V, W ) を最大次数 D のグラフ，
V  V1 V2 Vr を分割（互いに共通部分を持たない），
各Vi は|Vi|≧2eD を満たすとすると，
各Vi の節点を含む独立集合 W⊆Vが存在する．
• 線グラフに命題5.5.3を適用する．
Vi を最初の分割の閉路に対応した節点集合とすると，
|Vi| は上の条件を満たす．
線グラフの次数 D は 4d－2, |Vi|は G の内周 g ≧ 8ed ≧ 2e(4d－2).
• それぞれの閉路（に対応した線グラフの節点集合）から
一つずつ独立集合になるように節点を選べる，元のグラフではマッチング．
定理 5.5.4の証明
2-正則
線グラフ
定理 5.5.4の証明
d+1個の線形森に分割可能
つまり，
dla (G)  d  1
2-正則
線グラフ
補題 5.5.5

補題 5.5.5
G = (V, W ) を d-正則有向グラフとし，d は十分大きいとし．
p を 10 d  p  20 d を満たす整数とすると，
下の条件を満たす節点の p-着色(0, 1, ..., p－1)が存在する．
N  (v, i) | {u V ; (v, u )  E　and u　is colored i} |
N  (v, i) | {u V ; (u, v)  E　and u　is colored i} |
が

| N (v, i)  | 3 d / p log d

d
p
| N (v, i)  | 3 d / p log d
を満たす．
d
p
1
1
v
3
(5.8)
1
2
補題 5.5.5の証明


節点に対し，ランダムに 0,..., p－1 を着色．

v, i に対して， Av ,i を N  (v, i ) が不等式(5.8)を満たさないとい
う事象とする．
1

Av ,i も同様．
1
v
すると， Pr( A )  1 / d 4
v ,i
3
Pr( Av,i )  1 / d 4
∵
N  (v, i) は2項分布 (期待値 d/p, 分散
1
d
p
(1  1p ) 
d
p
2
)．
あとは，独立でない事象の数を見積もって Local Lemma．
全ての v, i で Av,i , Av,i が起こらない（式5.8を満たす）確率が正であることを示す．
補題 5.5.5の証明




Av,i と独立でない Av,i , Av,i は，v と隣接点を共有するような v’
に対するもの．
d-正則なので，このような v’ は高々 (2d)2 個．
色は p 個あるので， Av,i と独立でない事象は高々 (2d)2 p個．
従って次を満たす．
5
2
1
d4
80d  1
(( 2d ) p  1) 
 1.
4
d
v
2d個
2
（d は十分大きく，仮定より p  20 d ）
・・・
2d個
Corollary 5.1.2 から，
全ての v, i で Av,i , Av,i が起こらない（式5.8を満たす）確率は
正となる．
定理 5.5.6の証明

定理 5.5.6 （再褐）
定数 c > 0 が存在し，全ての d-正則有向グラフ G が
dla (G)  d  cd 3 / 4 (log d )1/ 2 を満たす．
定理 5.5.6の証明


グラフ G を補題5.5.5を利用して p 個の部分グラフ
G0,...,Gp－1に分割．(G1,...,Gp－1は内周が大きく定理5.5.4が使
える)
（p は 10 d  p  20 d を満たす素数）
G の線形樹化数は， G0,...,Gp－1の線形樹化数の上界の和
でおさえられる．
定理 5.5.6の証明
G0,...,Gp－1 の作り方

G の節点を f : V → {0,...p-1} で彩色．
補題 5.5.5 から，不等式 (5.8) を満たす着色が存在．

Gi =(V, Ei) の辺集合 Ei を以下のようにする．
Ei  {(u, v)  E : f (v)  ( f (u)  i) mod p}
2
2
5
2
2
E0
2
9
13
閉路の長さは p の倍数
…
…
同じ色の
節点を結ぶ
2
1
p-3
p-7
E4
∵ 長さを L とすると，
f (v)  ( f (v)  Li) mod p
を満たす，かつ，
i < p で，p は素数だから．
定理 5.5.6の証明

G0 は， trivial な上界 dla (G0 )  2 0 .
Δi は Gi の最大次数
定理 5.5.4 の証明の最初の議論で Δ0 個の 1-正則全域部分グラフに分割
して，各々をさらに２つに分割．

Gi (1≦ i ≦p-1) は，内周≧ p ≧10√d ＞8eΔi なので，
定理 5.5.4 から dla (Gi )  i  1.
10 d  p  20 d
定理 5.5.6の証明

G0 は， trivial な上界 dla (G0 )  2 0 .
Δi は Gi の最大次数
定理 5.5.4 の証明の最初の議論で Δ0 個の 1-正則全域部分グラフに分割
して，各々をさらに２つに分割．

Gi (1≦ i ≦p-1) は，内周≧ p ≧10√d ＞8eΔi なので，
定理 5.5.4 から dla (Gi )  i  1.
1
N±(v,
最大次数は補題 5.5.5 の
i) の不等式(5.8)による．
N±(v, i) は節点 v に隣接する色 i が塗られた節点の数．
つまり， N±(v, i) で v の indegree /outdegree を押さえられる．
| N  (v, i)  dp | 3 d / p log d
| N  (v, i)  dp | 3 d / p log d
 i  dp  3
d
p
log d , i  dp  3
v
1
(5.8)
1
3
3
10 d  p  20 d
d
p
log d  201 d .
定理 5.5.6の証明
dla (G0 )  2 0  2 dp  6
dla (Gi )  i  1  dp  3
∴
dla (G )  dla (G0 ) 
d
p
log d
log d  1
d
p
 dla (G )
1i  p 1
i
 d  2 dp  3 pd log d  3
3
4
 d  cd (log d )
1
2
d
p
log d  p  1
定理 5.5.6

定理 5.5.6 （再褐）
定数 c > 0 が存在し，全ての d-正則有向グラフ G が
dla (G)  d  cd 3 / 4 (log d )1/ 2 を満たす．
定理 5.5.7

定理 5.5.7 （再褐）
定数 c > 0 が存在し，全ての d-正則無向グラフ G が
la (G)  d / 2  cd 3 / 4 (log d )1/ 2を満たす．
前述したように，
d-正則無向グラフ G に対応する d/2-正則有向グラフを考えれば定理5.5.6 から自明．
d が奇数のときは，(d+1)/2-正則有向グラフを考えれば同様に定理 5.5.7 がいえる．

Download Report