On Linial’s Conjecture for Split Digraphs
Maycon Sambinelli1 Cândida Nunes da Silva2 Orlando Lee1
1 Institute of Computing – University of Campinas
2 Department of Computing – Federal University of São Carlos
I Encontro de Teoria da Computação
Porto Alegre, July of 2016
1 / 20
Outline
1. Basic definitions
2. Linial’s conjecture
3. Our results
4. An update
2 / 20
Definitions
3 / 20
Basic definitions
• Digraphs
• Paths = directed paths
4 / 20
Basic definitions
• Digraphs
• Paths = directed paths
4 / 20
Path Partition
• P = {P1 , P2 , . . . , P` }
• V (Pi ) ∩ V (Pj ) = ∅ for every i 6= j
• V (P) = V (D)
5 / 20
k-norm of a path partition
X
|P|k := min{|V (Pi )|, k}
Pi ∈P
k=4
+ 3
17
|P|4 = 17
6 / 20
k-optimal path partition
• A path partition P is k-optimal if |P|k is minimum
|P|2 = 4 |P 0 |2 = 3
7 / 20
k-optimal path partition
• A path partition P is k-optimal if |P|k is minimum
|P|2 = 4 |P 0 |2 = 3
πk (D) = min{|P|k : P is a path partition of D}
7 / 20
k-partial coloring
• C k = {C1 , C2 , . . . , Ck }
• Ci is a stable set (possibly empty)
• Ci ∩ Cj = ∅ if i 6= j
C3 = { , , }
8 / 20
Weight of k-partial coloring
• ||C k || = number of colored vertices
9 / 20
Weight of k-partial coloring
• ||C k || = number of colored vertices
C3 = { , , }
||C 3 || = 6
A k-partial coloring C k is optimal if ||C k || is maximum
αk (D) = max{||C k || : C k is a k-partial coloring of D}
9 / 20
Linial’s conjecture
Linial’s Conjecture (1981). Let D be a digraph and let k be a
positive integer. Then, πk (D) ≤ αk (D).
10 / 20
Linial’s conjecture
Linial’s Conjecture (1981). Let D be a digraph and let k be a
positive integer. Then, πk (D) ≤ αk (D).
Solved for:
• k=1
• k=2
• k ≥ λ(D) − 3
• Acyclic digraphs
• Bipartite digraphs
• Traceable digraphs
10 / 20
Our results
11 / 20
Split digraph
• D is a split digraph if V (D) = X ∪ Y such that:
• D[X] is a semi-complete digraph
• Y is a stable set in D
Y
X
12 / 20
Our results
Let D be a split digraph
Lemma 1. αk (D) ≥ |Y | + k − 1
13 / 20
Our results
Let D be a split digraph
Lemma 1. αk (D) ≥ |Y | + k − 1
Theorem 2. If αk (D) ≥ |Y | + k, then πk (D) ≤ αk (D)
• Remaining case: αk (D) = |Y | + k − 1
13 / 20
Our results
Let D be a split digraph
Lemma 1. αk (D) ≥ |Y | + k − 1
Theorem 2. If αk (D) ≥ |Y | + k, then πk (D) ≤ αk (D)
• Remaining case: αk (D) = |Y | + k − 1
Lemma 3. αk (D) = |Y | + k − 1 iff D is k-tight
13 / 20
k-tight
Definition 4. A split digraph D is k-tight if:
• |X| ≥ k; and
• ∀S ⊆ X, such that |S| = k, exists a vertex y ∈ Y which is
adjacent to every vertex in S.
S⊆X
x1 x2 x3 x4 xk
y∈Y
14 / 20
Thick spider digraph
X
yi
xi
k-tight if |X| ≥ k
15 / 20
Thick spider digraphs
Lemma 5. ∃P such than |P|k ≤ |Y | + k − 1
• There exists a Hamiltonian path in D[X]
x1 x2 x3 xi x`−2 x`−1 x`
yi
if j < i ⇒ (xj , yi ) ∈ A(D)
if j > i ⇒ (yi , xj ) ∈ A(D)
16 / 20
Thick spider digraphs
Lemma 5. ∃P such than |P|k ≤ |Y | + k − 1
• There exists a Hamiltonian path in D[X]
x1 x2 x3 xi x`−2 x`−1 x`
yi
if j < i ⇒ (xj , yi ) ∈ A(D)
if j > i ⇒ (yi , xj ) ∈ A(D)
16 / 20
Thick spider digraphs
Lemma 5. ∃P such than |P|k ≤ |Y | + k − 1
x1 x2 x3 x4 x5 x6 x7
y1 y2 y3 y4 y5 y6 y7
17 / 20
Thick spider digraphs
Lemma 5. ∃P such than |P|k ≤ |Y | + k − 1
x1 x2 x3 x4 x5 x6 x7
y1 y2 y3 y4 y5 y6 y7
Lemma 1. αk (D) ≥ |Y | + k − 1
17 / 20
Thick spider digraphs
Lemma 5. ∃P such than |P|k ≤ |Y | + k − 1
x1 x2 x3 x4 x5 x6 x7
y1 y2 y3 y4 y5 y6 y7
Lemma 1. αk (D) ≥ |Y | + k − 1
Corollary 6. If D is a thick spider, then πk (D) ≤ αk (D)
17 / 20
An update
18 / 20
An update
• Linial’s conjecture is true for k-tight digraphs (⇒ split digraphs)
19 / 20
An update
• Linial’s conjecture is true for k-tight digraphs (⇒ split digraphs)
Theorem 7. If D is a spine digraph, than πk (D) ≤ αk (D)
Y
X
19 / 20
Questions?
20 / 20