NCE+AGCE | 61.1(1.29) | 55.2(3.29) | 42.9(4.15) | 15.1(2.81) | 57.4(2.64) | 46.3(2.72) | 41.7(3.57)
MSE | 38.9(1.24) | 34.4(3.15) | 25.4(2.67) | 14.3(1.79) | 36.2(2.18) | 34.3(1.97) | 32.3(2.21)
MAE | 13.2(1.31) | 13.2(1.38) | 12.7(1.3) | 11.7(2.27) | 13.1(1.49) | 13.1(1.48) | 13.1(1.64)
News20 | ALDR-KL | 97.8(0.145) | 95.8(0.149) | 89.4(0.908) | 40.9(3.67) | 97.3(0.157) | 96.8(0.222) | 96.1(0.154)
LDR-KL | 97.8(0.213) | 95.8(0.137) | 89.5(1.26) | 40.1(6.17) | 97.5(0.109) | 96.9(0.106) | 96.4(0.286)
CE | 86.9(0.38) | 57.8(2.09) | 31.0(2.37) | 14.4(1.14) | 86.0(0.375) | 86.0(0.607) | 85.6(0.287)
SCE | 85.0(0.469) | 53.3(1.21) | 30.5(2.92) | 15.9(2.44) | 84.1(0.653) | 84.4(0.931) | 84.1(0.866)
GCE | 77.8(0.963) | 45.1(0.789) | 28.8(1.98) | 15.3(0.847) | 76.5(1.2) | 78.6(1.31) | 78.5(0.873)
TGCE | 76.1(1.08) | 44.4(1.23) | 28.6(1.82) | 15.3(0.847) | 74.7(1.53) | 77.2(1.39) | 77.0(1.05)
WW | 80.2(1.05) | 57.5(3.19) | 38.0(2.64) | 15.6(2.52) | 79.6(1.15) | 80.7(1.14) | 79.5(0.95)
JS | 43.6(0.792) | 28.4(1.74) | 21.8(1.84) | 15.6(1.19) | 44.3(1.03) | 40.3(0.734) | 39.7(1.08)
CS | 92.0(0.925) | 92.6(0.76) | 76.7(1.9) | 19.8(2.28) | 91.9(1.05) | 90.8(1.02) | 89.8(0.652)
RLL | 25.5(0.168) | 20.9(1.7) | 19.1(2.88) | 15.6(1.22) | 26.1(0.421) | 26.1(0.729) | 25.9(0.374)
NCE+RCE | 95.6(0.078) | 82.3(3.0) | 35.0(2.7) | 15.0(1.33) | 93.8(2.26) | 71.9(1.44) | 67.6(0.56)
NCE+AUL | 65.7(2.07) | 32.2(1.75) | 24.1(1.82) | 15.5(0.745) | 56.1(1.93) | 49.9(2.48) | 47.4(1.91)
NCE+AGCE | 41.7(3.43) | 23.5(2.23) | 19.8(2.38) | 16.5(0.775) | 37.0(0.911) | 31.6(2.49) | 31.6(1.61)
MSE | 21.9(2.69) | 20.5(1.53) | 17.7(1.11) | 14.8(0.709) | 20.6(1.71) | 19.3(1.04) | 19.4(2.13)
MAE | 16.0(0.316) | 15.6(0.867) | 15.4(0.741) | 15.4(0.685) | 15.8(0.525) | 16.0(0.328) | 16.0(0.328)
ALOI | ALDR-KL | 98.4(0.099) | 95.3(0.122) | 90.7(0.108) | 45.1(0.612) | 97.2(0.06) | 94.7(0.117) | 91.3(0.161)
LDR-KL | 97.5(0.073) | 95.3(0.132) | 91.2(0.11) | 45.1(0.749) | 95.8(0.546) | 93.6(0.051) | 89.3(0.075)
CE | 86.6(0.172) | 80.9(0.221) | 60.6(0.424) | 8.2(0.455) | 85.4(0.223) | 78.4(0.21) | 52.6(0.402)
SCE | 86.1(0.147) | 79.8(0.266) | 58.5(0.616) | 8.19(0.505) | 84.7(0.217) | 77.3(0.178) | 50.4(0.273)
GCE | 83.9(0.162) | 74.8(0.257) | 48.2(0.306) | 6.12(0.47) | 82.0(0.268) | 71.6(0.326) | 41.5(0.256)
TGCE | 83.1(0.256) | 73.6(0.266) | 47.1(0.484) | 6.12(0.47) | 81.1(0.152) | 70.3(0.195) | 39.8(0.36)
WW | 77.5(0.266) | 66.7(0.619) | 46.3(0.244) | 6.94(0.228) | 67.0(0.503) | 45.1(0.392) | 22.4(0.373)
JS | 7.68(0.511) | 6.84(0.488) | 3.73(0.544) | 0.491(0.175) | 7.46(0.684) | 5.62(0.413) | 3.66(0.377)
CS | 91.7(0.182) | 83.8(0.234) | 42.4(0.427) | 3.63(0.131) | 90.0(0.069) | 86.2(0.123) | 71.1(0.228)
RLL | 1.54(0.335) | 1.03(0.231) | 0.574(0.147) | 0.356(0.079) | 1.39(0.315) | 1.0(0.192) | 0.82(0.106)
NCE+RCE | 5.93(0.518) | 5.63(0.498) | 4.64(0.508) | 0.7(0.316) | 6.1(0.1) | 4.68(0.195) | 3.23(0.231)
NCE+AUL | 6.23(0.554) | 4.18(0.349) | 1.92(0.318) | 0.354(0.108) | 5.54(0.72) | 4.0(0.304) | 2.63(0.32)
NCE+AGCE | 4.93(0.448) | 2.83(0.361) | 1.3(0.212) | 0.441(0.139) | 4.19(0.666) | 2.98(0.436) | 1.92(0.244)
MSE | 0.669(0.202) | 0.528(0.091) | 0.463(0.095) | 0.343(0.061) | 0.613(0.141) | 0.53(0.06) | 0.467(0.05)
MAE | 0.441(0.067) | 0.441(0.067) | 0.363(0.099) | 0.311(0.067) | 0.441(0.067) | 0.42(0.07) | 0.396(0.082)

Table 11: Testing Top-3 Accuracy (%) with mean and standard deviation for
image dataset. The highest values are marked as bold.

Dataset | Loss | Clean | Uniform 0.3 | Uniform 0.6 | Uniform 0.9 | CD 0.1 | CD 0.3 | CD 0.5
---|---|---|---|---|---|---|---|---
Kuzushiji-49 | ALDR-KL | 98.6(0.147) | 97.8(0.094) | 95.2(0.551) | 60.8(1.21) | 98.1(0.053) | 97.8(0.062) | 96.9(0.187)
LDR-KL | 98.6(0.048) | 97.7(0.071) | 95.7(0.729) | 60.2(1.29) | 98.1(0.063) | 97.7(0.057) | 96.9(0.181)
CE | 98.8(0.074) | 97.7(0.116) | 91.0(0.304) | 47.0(2.47) | 98.1(0.059) | 97.7(0.068) | 97.1(0.15)
SCE | 98.9(0.113) | 97.7(0.172) | 90.5(0.534) | 46.1(2.06) | 98.1(0.042) | 97.7(0.025) | 97.0(0.111)
GCE | 98.8(0.142) | 97.8(0.09) | 90.6(0.285) | 44.7(1.8) | 98.0(0.045) | 97.7(0.05) | 97.0(0.114)
TGCE | 98.7(0.126) | 97.8(0.102) | 90.5(0.216) | 45.6(1.1) | 98.0(0.044) | 97.7(0.064) | 97.0(0.135)
WW | 99.0(0.105) | 97.1(0.092) | 91.5(0.487) | 45.2(1.23) | 98.2(0.066) | 98.1(0.081) | 97.7(0.108)
JS | 98.7(0.066) | 95.3(0.615) | 91.0(0.845) | 45.0(0.9) | 97.0(0.911) | 95.4(0.101) | 94.6(0.097)
CS | 98.6(0.066) | 92.3(2.0) | 12.3(3.35) | 6.21(0.246) | 98.1(0.039) | 95.2(0.708) | 66.3(2.87)
RLL | 93.0(0.048) | 92.6(0.101) | 84.1(1.25) | 42.8(0.771) | 92.7(0.045) | 90.5(0.84) | 91.4(0.834)
NCE+RCE | 92.5(0.146) | 92.1(0.142) | 71.8(0.931) | 16.7(1.33) | 91.4(0.328) | 89.4(0.181) | 86.8(0.801)
NCE+AUL | 92.6(0.062) | 87.2(0.861) | 68.2(1.17) | 18.3(1.54) | 92.4(0.137) | 90.8(0.101) | 90.4(0.692)
NCE+AGCE | 92.4(0.029) | 79.4(0.778) | 59.6(0.927) | 18.1(1.46) | 92.1(0.091) | 89.8(0.431) | 89.3(0.175)
MSE | 84.1(1.69) | 58.7(1.56) | 36.3(1.8) | 10.8(0.804) | 64.5(1.75) | 48.9(1.44) | 35.9(3.28)
MAE | 6.12(0.0) | 35.5(2.36) | 20.3(2.91) | 9.9(0.879) | 39.6(2.09) | 24.5(1.81) | 18.5(1.6)
CIFAR100 | ALDR-KL | 79.7(0.586) | 72.6(0.306) | 56.8(0.778) | 10.0(0.895) | 76.6(0.749) | 70.7(0.756) | 63.6(0.902)
LDR-KL | 80.1(0.397) | 72.1(0.534) | 56.6(0.607) | 10.2(0.824) | 76.3(0.586) | 70.3(0.463) | 64.2(0.641)
CE | 79.1(0.492) | 69.5(0.637) | 52.5(1.06) | 10.5(0.695) | 75.5(0.318) | 69.7(0.636) | 64.1(0.289)
SCE | 79.0(0.779) | 69.8(0.817) | 51.4(0.947) | 11.1(1.05) | 75.2(0.298) | 70.1(0.499) | 63.9(0.671)
GCE | 79.5(0.318) | 69.5(1.39) | 52.3(0.677) | 10.1(1.11) | 75.4(0.726) | 70.0(0.392) | 64.1(0.345)
TGCE | 78.8(0.469) | 70.4(0.846) | 49.5(0.466) | 10.1(1.02) | 75.9(0.324) | 70.7(0.56) | 62.8(0.582)
WW | 74.6(0.441) | 60.8(0.6) | 41.1(0.586) | 10.7(0.738) | 72.2(0.456) | 68.1(0.296) | 58.7(0.646)
JS | 77.8(0.405) | 71.8(0.735) | 46.4(1.27) | 10.2(0.821) | 76.5(0.395) | 68.4(0.778) | 59.8(0.969)
CS | 21.9(0.744) | 11.6(1.04) | 3.97(0.407) | 3.0(0.004) | 17.6(0.812) | 12.0(0.547) | 8.52(0.847)
RLL | 54.9(2.19) | 47.3(1.24) | 26.9(0.785) | 10.1(0.527) | 52.5(1.25) | 46.3(2.71) | 31.8(1.78)
NCE+RCE | 17.0(0.403) | 14.0(0.664) | 11.4(0.654) | 5.64(1.38) | 15.7(0.471) | 13.1(0.71) | 8.5(0.457)
NCE+AUL | 20.0(0.521) | 16.6(0.49) | 13.1(0.448) | 7.76(0.888) | 18.7(0.509) | 16.3(0.669) | 11.4(0.316)
NCE+AGCE | 19.8(0.791) | 16.6(0.587) | 13.2(0.814) | 7.61(0.501) | 18.6(0.602) | 16.2(0.847) | 11.4(0.333)
MSE | 25.4(0.644) | 21.1(0.755) | 18.3(0.542) | 10.9(0.766) | 23.4(0.443) | 19.9(0.563) | 14.4(0.523)
MAE | 3.14(0.21) | 3.13(0.208) | 2.93(0.22) | 2.94(0.373) | 3.11(0.171) | 2.97(0.251) | 3.0(0.308)
Tiny-ImageNet | ALDR-KL | 65.9(0.139) | 56.5(0.28) | 38.7(0.249) | 3.28(0.78) | 61.9(0.237) | 55.7(0.669) | 49.0(0.214)
LDR-KL | 65.2(0.331) | 56.1(0.515) | 38.8(0.456) | 3.01(0.754) | 61.5(0.148) | 55.4(0.454) | 50.4(0.217)
CE | 65.9(0.149) | 54.4(0.565) | 29.0(0.584) | 3.05(0.38) | 63.5(0.214) | 58.3(0.501) | 49.9(0.294)
SCE | 65.9(0.366) | 54.2(0.389) | 28.5(0.937) | 3.79(0.769) | 63.3(0.482) | 58.0(0.267) | 49.8(0.166)
GCE | 65.7(0.219) | 54.1(0.557) | 25.2(0.874) | 2.99(0.473) | 63.4(0.168) | 57.8(0.278) | 49.5(0.193)
TGCE | 64.2(0.129) | 49.9(0.129) | 23.0(0.792) | 3.22(0.22) | 61.3(0.243) | 55.5(0.206) | 44.9(0.433)
WW | 52.4(0.338) | 39.3(0.292) | 22.9(0.558) | 2.66(0.283) | 49.7(0.393) | 45.6(0.424) | 33.4(0.192)
JS | 55.2(0.546) | 32.2(0.671) | 10.5(0.703) | 3.61(0.401) | 49.8(0.616) | 34.8(0.222) | 22.6(1.17)
CS | 2.57(0.243) | 1.67(0.123) | 1.5(0.0) | 1.5(0.0) | 2.07(0.141) | 1.7(0.137) | 1.52(0.089)
RLL | 14.2(1.26) | 7.96(0.586) | 5.92(0.363) | 3.22(0.26) | 10.7(0.59) | 7.41(0.588) | 5.44(0.067)
NCE+RCE | 4.21(0.207) | 4.09(0.173) | 3.36(0.124) | 1.82(0.281) | 4.01(0.345) | 3.72(0.257) | 3.1(0.227)
NCE+AUL | 4.79(0.114) | 4.39(0.105) | 3.68(0.296) | 2.13(0.39) | 4.63(0.22) | 4.36(0.365) | 3.59(0.375)
NCE+AGCE | 4.87(0.252) | 4.5(0.188) | 3.9(0.262) | 2.18(0.417) | 4.79(0.281) | 4.45(0.268) | 3.55(0.174)
MSE | 6.1(0.247) | 2.93(0.161) | 2.75(0.298) | 2.01(0.361) | 3.01(0.291) | 2.89(0.188) | 2.78(0.197)
MAE | 1.57(0.063) | 2.51(0.254) | 2.06(0.254) | 2.11(0.243) | 2.49(0.205) | 2.51(0.185) | 2.47(0.189)

Table 12: Testing Top-4 Accuracy (%) with mean and standard deviation for
tabular dataset. The highest values are marked as bold.

Dataset | Loss | Clean | Uniform 0.3 | Uniform 0.6 | Uniform 0.9 | CD 0.1 | CD 0.3 | CD 0.5
---|---|---|---|---|---|---|---|---
Vowel | ALDR-KL | 98.8(0.99) | 91.7(0.99) | 79.8(3.06) | 37.8(6.25) | 98.8(0.756) | 99.0(1.11) | 98.2(0.756)
LDR-KL | 97.6(0.808) | 92.1(2.34) | 73.5(6.8) | 39.2(4.11) | 97.8(1.18) | 97.6(1.51) | 96.8(2.96)
CE | 97.8(0.756) | 93.3(1.87) | 78.2(2.9) | 36.6(6.56) | 98.2(1.74) | 97.8(0.756) | 95.8(0.756)
SCE | 97.6(0.808) | 93.3(1.64) | 75.6(6.86) | 37.2(4.84) | 98.2(0.756) | 97.4(1.51) | 94.7(1.18)
GCE | 97.8(0.756) | 93.9(1.69) | 80.6(2.74) | 37.2(5.32) | 97.6(1.03) | 97.8(0.404) | 95.4(1.21)
TGCE | 97.8(0.756) | 93.1(1.49) | 80.0(3.34) | 37.2(5.32) | 98.0(0.639) | 97.8(0.404) | 95.2(1.18)
WW | 98.0(0.0) | 93.3(1.37) | 78.2(3.65) | 39.2(7.04) | 97.2(0.99) | 97.6(1.37) | 96.4(1.03)
JS | 96.0(1.28) | 93.5(0.808) | 79.2(3.65) | 37.4(6.64) | 97.2(1.34) | 96.4(1.21) | 93.3(1.87)
CS | 98.0(1.43) | 90.5(3.48) | 72.7(4.19) | 39.4(6.03) | 98.2(0.404) | 96.8(1.96) | 93.1(2.25)
RLL | 94.1(1.18) | 90.9(1.11) | 82.0(0.404) | 34.9(4.36) | 95.6(1.03) | 94.1(0.756) | 90.5(0.808)
NCE+RCE | 92.7(1.18) | 89.1(2.67) | 74.1(2.44) | 40.2(2.81) | 92.9(0.639) | 91.7(1.18) | 91.1(1.18)
NCE+AUL | 91.3(1.21) | 88.5(2.97) | 70.1(5.91) | 36.2(6.21) | 93.7(0.756) | 93.5(1.03) | 91.7(0.756)
NCE+AGCE | 91.9(2.63) | 88.1(2.74) | 68.9(4.62) | 38.6(5.09) | 93.1(0.99) | 93.1(1.18) | 91.5(0.495)
MSE | 90.5(0.808) | 89.5(1.37) | 72.3(1.87) | 36.2(5.58) | 91.5(2.36) | 90.9(0.639) | 89.9(1.11)
MAE | 41.6(5.69) | 42.8(6.34) | 44.6(5.47) | 44.2(5.17) | 39.0(2.9) | 38.8(2.68) | 40.4(4.04)
Letter | ALDR-KL | 92.4(0.183) | 90.8(0.268) | 87.9(1.07) | 65.9(3.19) | 92.6(0.275) | 91.5(0.37) | 89.7(0.411)
LDR-KL | 91.7(0.173) | 90.7(0.528) | 87.5(0.541) | 64.0(4.31) | 91.2(0.434) | 91.0(0.437) | 89.1(0.252)
CE | 90.1(0.195) | 88.5(0.265) | 83.1(1.81) | 40.9(1.91) | 89.4(0.203) | 88.1(0.256) | 85.6(0.344)
SCE | 90.0(0.185) | 88.4(0.369) | 82.8(1.94) | 37.6(3.88) | 89.4(0.133) | 88.2(0.229) | 85.5(0.483)
GCE | 89.7(0.146) | 87.9(0.138) | 81.8(2.05) | 32.9(4.88) | 89.2(0.243) | 88.0(0.288) | 85.3(0.377)
TGCE | 89.5(0.105) | 87.9(0.138) | 83.6(1.43) | 32.8(5.02) | 89.2(0.3) | 87.9(0.193) | 85.2(0.386)
WW | 88.9(0.208) | 88.4(0.202) | 85.6(0.614) | 38.5(2.85) | 88.3(0.1) | 86.8(0.126) | 83.7(0.084)
JS | 88.4(0.314) | 86.9(0.121) | 76.4(0.812) | 25.9(3.73) | 88.1(0.287) | 87.1(0.402) | 84.1(0.213)
CS | 89.0(0.2) | 87.6(0.419) | 84.6(0.934) | 54.3(4.58) | 88.5(0.3) | 86.9(0.227) | 84.0(0.169)
RLL | 86.1(0.086) | 80.6(0.394) | 56.9(0.491) | 16.5(2.56) | 85.8(0.317) | 84.5(0.229) | 79.2(1.3)
NCE+RCE | 71.3(1.48) | 65.1(2.36) | 56.2(5.03) | 26.6(3.99) | 68.1(2.29) | 55.5(0.956) | 49.5(1.72)
NCE+AUL | 70.2(3.73) | 63.5(1.89) | 54.5(3.35) | 25.0(2.62) | 63.7(1.8) | 53.9(3.16) | 46.8(2.77)
NCE+AGCE | 62.0(1.41) | 55.9(3.61) | 44.7(3.4) | 19.7(1.44) | 58.4(2.71) | 48.5(1.86) | 44.7(1.55)
MSE | 46.5(1.16) | 41.1(2.45) | 31.7(2.62) | 18.2(1.89) | 42.9(2.26) | 41.4(2.01) | 39.9(1.89)
MAE | 16.9(1.49) | 17.1(1.55) | 16.8(1.84) | 15.2(2.19) | 16.9(1.47) | 17.0(1.51) | 16.8(1.36)
News20 | ALDR-KL | 98.3(0.144) | 96.6(0.203) | 91.4(0.972) | 44.5(2.68) | 98.2(0.121) | 97.8(0.216) | 97.4(0.326)
LDR-KL | 98.3(0.204) | 96.5(0.221) | 91.6(1.04) | 45.5(4.8) | 98.2(0.172) | 97.7(0.136) | 97.7(0.162)
CE | 90.3(0.434) | 67.1(1.18) | 38.7(3.68) | 19.9(1.02) | 89.7(0.264) | 89.8(0.34) | 89.5(0.086)
SCE | 88.9(0.317) | 63.2(0.651) | 37.2(4.88) | 19.9(0.539) | 88.2(0.539) | 88.8(0.601) | 88.4(0.375)
GCE | 83.7(0.62) | 55.8(0.96) | 36.0(3.91) | 20.1(0.779) | 82.6(1.16) | 83.5(0.744) | 83.5(0.835)
TGCE | 81.9(0.728) | 55.3(0.437) | 36.0(3.91) | 20.1(0.779) | 80.6(1.36) | 82.2(1.6) | 82.2(1.35)
WW | 85.4(0.899) | 64.9(2.17) | 42.5(3.36) | 20.8(2.09) | 84.9(0.685) | 85.6(0.771) | 84.9(0.595)
JS | 51.7(0.279) | 36.2(0.842) | 27.7(0.745) | 20.6(1.31) | 51.4(1.31) | 49.3(0.713) | 48.7(1.12)
CS | 95.2(0.543) | 95.2(0.333) | 81.5(0.953) | 23.8(2.6) | 95.0(0.726) | 95.2(0.606) | 94.1(0.646)
RLL | 33.2(0.464) | 26.3(1.52) | 25.3(3.24) | 20.2(1.14) | 33.8(0.722) | 34.2(0.574) | 34.4(0.561)
NCE+RCE | 96.3(0.232) | 84.5(3.1) | 39.7(3.62) | 20.5(0.449) | 94.6(2.29) | 72.6(1.57) | 68.1(0.657)
NCE+AUL | 66.4(1.63) | 35.4(0.569) | 31.4(1.38) | 20.5(0.75) | 56.4(1.76) | 50.5(2.16) | 47.7(2.05)
NCE+AGCE | 42.7(3.07) | 29.0(1.18) | 27.2(3.88) | 22.0(1.82) | 38.8(3.08) | 33.2(1.85) | 33.8(1.6)
MSE | 28.2(2.11) | 25.0(0.965) | 23.7(1.23) | 19.8(0.615) | 26.7(2.43) | 26.2(2.06) | 25.8(1.35)
MAE | 20.8(0.453) | 20.9(0.462) | 20.2(1.03) | 19.8(1.34) | 20.8(0.453) | 20.8(0.453) | 20.8(0.453)
ALOI | ALDR-KL | 98.8(0.073) | 96.2(0.118) | 92.0(0.158) | 48.1(0.334) | 97.8(0.033) | 95.8(0.107) | 93.3(0.166)
LDR-KL | 98.1(0.096) | 96.1(0.122) | 92.4(0.118) | 48.4(0.474) | 96.3(0.382) | 94.7(0.076) | 91.6(0.167)
CE | 88.5(0.072) | 83.5(0.196) | 65.5(0.455) | 9.82(0.444) | 87.6(0.137) | 81.6(0.095) | 58.2(0.527)
SCE | 88.1(0.11) | 82.8(0.253) | 63.4(0.497) | 9.89(0.522) | 86.9(0.143) | 80.7(0.132) | 56.3(0.456)
GCE | 86.2(0.186) | 78.2(0.15) | 53.7(0.392) | 7.58(0.509) | 84.7(0.222) | 75.8(0.209) | 47.0(0.241)
TGCE | 85.5(0.144) | 77.3(0.288) | 52.4(0.604) | 7.58(0.509) | 83.9(0.169) | 74.4(0.36) | 45.1(0.302)
WW | 81.6(0.328) | 72.1(0.618) | 52.6(0.196) | 8.81(0.195) | 73.0(0.4) | 51.7(0.272) | 27.4(0.323)
JS | 9.39(0.643) | 8.38(0.517) | 4.67(0.542) | 0.593(0.211) | 9.21(0.77) | 6.77(0.627) | 4.51(0.314)
CS | 93.1(0.146) | 85.8(0.327) | 45.4(0.53) | 4.27(0.23) | 91.4(0.046) | 88.1(0.149) | 75.5(0.179)
RLL | 1.88(0.336) | 1.28(0.276) | 0.763(0.169) | 0.474(0.126) | 1.71(0.3) | 1.33(0.135) | 1.06(0.063)
NCE+RCE | 7.19(0.531) | 6.96(0.552) | 5.92(0.604) | 0.833(0.397) | 7.32(0.197) | 5.82(0.175) | 4.02(0.167)
NCE+AUL | 7.59(0.566) | 5.26(0.362) | 2.32(0.329) | 0.554(0.208) | 6.93(0.714) | 4.96(0.422) | 3.36(0.199)
NCE+AGCE | 5.97(0.51) | 3.52(0.487) | 1.59(0.277) | 0.598(0.182) | 5.22(0.593) | 3.7(0.46) | 2.54(0.151)
MSE | 0.806(0.206) | 0.683(0.13) | 0.646(0.125) | 0.43(0.06) | 0.73(0.187) | 0.693(0.154) | 0.643(0.137)
MAE | 0.543(0.061) | 0.552(0.056) | 0.5(0.105) | 0.48(0.081) | 0.552(0.056) | 0.541(0.049) | 0.498(0.074)

Table 13: Testing Top-4 Accuracy (%) with mean and standard deviation for
image dataset. The highest values are marked as bold.

Dataset | Loss | Clean | Uniform 0.3 | Uniform 0.6 | Uniform 0.9 | CD 0.1 | CD 0.3 | CD 0.5
---|---|---|---|---|---|---|---|---
Kuzushiji-49 | ALDR-KL | 98.8(0.15) | 98.2(0.059) | 95.8(0.238) | 64.1(1.81) | 98.4(0.071) | 98.2(0.039) | 97.9(0.038)
LDR-KL | 98.8(0.035) | 97.9(0.314) | 95.7(0.862) | 63.7(0.856) | 98.4(0.029) | 98.1(0.04) | 97.9(0.097)
CE | 99.1(0.102) | 98.0(0.114) | 92.3(0.062) | 51.0(2.52) | 98.4(0.044) | 98.1(0.08) | 97.8(0.062)
SCE | 99.0(0.123) | 98.1(0.077) | 91.7(0.734) | 50.1(2.15) | 98.4(0.049) | 98.1(0.029) | 97.8(0.061)
GCE | 99.0(0.138) | 98.2(0.05) | 91.5(0.295) | 48.9(1.81) | 98.4(0.021) | 98.0(0.041) | 97.8(0.052)
TGCE | 99.0(0.143) | 97.9(0.321) | 91.4(0.28) | 49.9(0.791) | 98.4(0.035) | 98.0(0.058) | 97.8(0.101)
WW | 99.1(0.138) | 97.6(0.108) | 93.5(0.487) | 50.0(1.34) | 98.5(0.096) | 98.4(0.065) | 98.4(0.12)
JS | 98.8(0.019) | 95.8(0.574) | 91.4(0.902) | 48.8(1.06) | 97.4(0.894) | 95.8(0.064) | 95.4(0.071)
CS | 98.7(0.05) | 93.4(1.88) | 14.5(3.48) | 8.33(0.264) | 98.2(0.043) | 96.2(0.791) | 70.3(2.96)
RLL | 93.1(0.033) | 92.8(0.049) | 84.6(1.21) | 46.3(0.693) | 92.9(0.042) | 91.3(0.667) | 91.7(1.14)
NCE+RCE | 92.8(0.244) | 92.4(0.157) | 72.1(0.951) | 20.9(1.66) | 92.3(0.172) | 91.5(0.024) | 89.2(0.39)
NCE+AUL | 92.8(0.041) | 87.4(0.879) | 68.6(0.937) | 23.5(2.27) | 92.7(0.036) | 93.4(0.248) | 92.6(0.633)
NCE+AGCE | 92.6(0.051) | 78.1(2.97) | 59.6(1.44) | 22.9(1.55) | 92.6(0.058) | 93.2(0.262) | 91.2(0.213)
MSE | 84.3(1.69) | 58.8(1.59) | 36.5(1.67) | 14.2(0.746) | 64.6(1.76) | 50.1(1.89) | 36.0(3.27)
MAE | 8.19(0.027) | 35.5(2.19) | 20.6(2.41) | 12.8(1.15) | 39.7(2.11) | 24.6(2.01) | 18.7(1.36)
CIFAR100 | ALDR-KL | 83.7(0.439) | 77.2(0.326) | 62.2(0.734) | 12.8(0.688) | 80.5(0.613) | 75.2(0.988) | 69.7(0.54)
LDR-KL | 83.9(0.248) | 76.7(0.516) | 62.2(0.617) | 13.7(0.831) | 80.3(0.297) | 74.8(0.822) | 70.1(0.838)
CE | 82.9(0.64) | 74.3(0.716) | 58.3(1.11) | 13.2(0.785) | 79.4(0.356) | 74.1(0.661) | 69.9(0.247)
SCE | 82.9(0.592) | 74.2(0.778) | 57.2(1.08) | 13.9(1.2) | 79.3(0.273) | 74.5(0.416) | 69.7(0.685)
GCE | 83.2(0.234) | 74.8(0.407) | 58.1(0.774) | 13.0(0.483) | 79.4(0.703) | 74.5(0.384) | 69.9(0.281)
TGCE | 82.6(0.376) | 75.1(0.797) | 55.3(0.495) | 12.4(1.21) | 80.0(0.271) | 75.1(0.568) | 68.5(0.514)
WW | 79.8(0.35) | 67.6(0.602) | 47.3(0.951) | 13.9(0.91) | 77.3(0.485) | 73.4(0.224) | 65.7(0.41)
JS | 81.7(0.203) | 76.0(1.08) | 50.9(1.06) | 13.3(0.48) | 80.4(0.424) | 73.1(1.16) | 65.2(0.508)
CS | 26.3(0.856) | 14.4(0.907) | 4.91(0.68) | 4.01(0.07) | 21.5(0.882) | 15.5(0.83) | 11.1(1.09)
RLL | 57.2(2.13) | 49.8(1.39) | 28.9(0.97) | 12.7(0.901) | 55.0(1.4) | 48.7(3.0) | 34.7(1.8)
NCE+RCE | 20.2(0.588) | 17.3(1.04) | 14.6(0.809) | 7.54(1.91) | 19.1(0.433) | 16.4(0.832) | 11.4(0.337)
NCE+AUL | 24.2(0.528) | 20.5(0.627) | 16.1(0.387) | 9.93(1.12) | 22.8(0.462) | 20.0(0.739) | 14.5(0.474)
NCE+AGCE | 24.4(0.816) | 20.5(0.623) | 16.2(0.535) | 10.3(0.729) | 22.9(0.578) | 20.2(0.981) | 14.7(0.516)
MSE | 28.9(0.699) | 25.2(0.874) | 22.2(0.584) | 13.6(0.687) | 27.1(0.484) | 23.7(0.631) | 17.8(0.484)
MAE | 4.16(0.274) | 4.14(0.287) | 3.87(0.292) | 4.04(0.121) | 4.14(0.286) | 4.07(0.36) | 3.81(0.327)
Tiny-ImageNet | ALDR-KL | 70.0(0.15) | 61.0(0.381) | 43.6(0.495) | 4.73(0.51) | 66.0(0.391) | 60.5(0.229) | 54.3(0.215)
LDR-KL | 69.4(0.174) | 60.5(0.45) | 43.8(0.751) | 4.69(0.789) | 65.5(0.28) | 59.8(0.352) | 55.6(0.331)
CE | 70.0(0.269) | 59.4(0.332) | 33.9(0.614) | 3.4(0.583) | 67.6(0.208) | 62.3(0.422) | 55.1(0.149)
SCE | 70.2(0.192) | 59.0(0.385) | 33.3(0.788) | 5.32(0.641) | 67.4(0.448) | 62.2(0.052) | 55.1(0.262)
GCE | 69.9(0.194) | 58.8(0.462) | 29.8(0.729) | 3.62(0.401) | 67.6(0.241) | 62.0(0.226) | 54.7(0.325)
TGCE | 68.3(0.164) | 54.9(0.158) | 27.4(0.691) | 3.94(0.349) | 65.7(0.226) | 59.5(0.243) | 50.0(0.476)
WW | 58.2(0.329) | 45.2(0.408) | 27.5(0.388) | 3.32(0.356) | 55.3(0.436) | 51.3(0.48) | 39.7(0.376)
JS | 58.9(0.417) | 35.0(0.682) | 12.9(0.797) | 4.65(0.249) | 53.3(0.814) | 38.0(0.204) | 24.9(1.4)
CS | 3.37(0.295) | 2.22(0.129) | 2.0(0.0) | 2.0(0.0) | 2.66(0.184) | 2.21(0.144) | 2.15(0.189)
RLL | 14.8(1.37) | 9.59(0.72) | 7.23(0.443) | 3.59(0.803) | 11.5(0.351) | 8.95(0.751) | 6.64(0.186)
NCE+RCE | 5.5(0.193) | 5.36(0.357) | 4.24(0.182) | 2.38(0.332) | 5.28(0.387) | 4.89(0.184) | 3.93(0.177)
NCE+AUL | 6.27(0.264) | 5.6(0.228) | 4.7(0.499) | 2.71(0.427) | 6.0(0.147) | 5.58(0.315) | 4.72(0.41)
NCE+AGCE | 6.3(0.271) | 5.77(0.187) | 5.03(0.338) | 3.07(0.341) | 6.27(0.208) | 5.65(0.377) | 4.67(0.148)
MSE | 7.64(0.284) | 3.7(0.353) | 3.58(0.28) | 2.56(0.452) | 3.68(0.311) | 3.69(0.209) | 3.62(0.183)
MAE | 2.06(0.113) | 3.23(0.305) | 2.77(0.342) | 2.75(0.419) | 3.33(0.328) | 3.29(0.166) | 3.25(0.207)

Table 14: Testing Top-5 Accuracy (%) with mean and standard deviation for
tabular dataset. The highest values are marked as bold.

Dataset | Loss | Clean | Uniform 0.3 | Uniform 0.6 | Uniform 0.9 | CD 0.1 | CD 0.3 | CD 0.5
---|---|---|---|---|---|---|---|---
Vowel | ALDR-KL | 98.6(0.808) | 94.7(0.404) | 85.1(4.49) | 44.2(3.75) | 99.2(0.756) | 99.2(0.756) | 98.8(0.404)
LDR-KL | 98.6(0.808) | 94.9(2.12) | 81.0(2.59) | 47.1(4.22) | 98.8(0.404) | 98.8(1.18) | 98.0(0.639)
CE | 98.8(1.18) | 95.8(1.62) | 85.9(3.67) | 42.0(5.21) | 98.6(0.808) | 98.4(0.495) | 97.2(0.756)
SCE | 98.8(0.756) | 95.4(2.6) | 83.2(4.59) | 47.7(4.84) | 99.4(0.495) | 98.4(0.495) | 96.8(0.404)
GCE | 98.8(0.756) | 95.4(2.68) | 85.7(3.16) | 46.9(4.07) | 98.4(0.495) | 97.6(1.03) | 97.2(0.404)
TGCE | 98.8(0.756) | 95.4(2.68) | 86.5(3.23) | 46.9(4.07) | 98.6(0.495) | 97.2(1.18) | 97.2(0.404)
WW | 98.8(0.756) | 96.0(1.43) | 86.7(1.74) | 48.3(6.4) | 98.2(0.756) | 98.8(0.99) | 98.2(0.99)
JS | 97.2(2.06) | 94.5(1.21) | 86.3(2.6) | 46.3(5.97) | 97.6(1.03) | 97.6(0.495) | 96.4(1.51)
CS | 99.4(0.808) | 92.9(1.81) | 76.0(4.11) | 50.1(8.0) | 98.4(1.51) | 98.2(1.49) | 96.0(0.903)
RLL | 96.0(1.11) | 95.4(0.808) | 84.4(5.25) | 44.2(6.37) | 96.4(0.808) | 96.4(1.37) | 94.5(2.18)
NCE+RCE | 96.4(0.808) | 92.9(2.47) | 82.2(2.9) | 44.8(4.5) | 96.2(0.404) | 96.0(0.903) | 92.5(2.36)
NCE+AUL | 96.2(0.756) | 93.3(2.36) | 78.6(8.7) | 50.5(4.99) | 96.0(0.639) | 95.4(1.21) | 93.7(1.18)
NCE+AGCE | 96.2(0.756) | 94.3(1.98) | 76.8(6.06) | 44.6(7.21) | 95.6(1.03) | 95.4(0.808) | 93.5(0.808)
MSE | 93.7(1.34) | 92.7(1.96) | 75.4(11.9) | 47.7(3.09) | 94.9(0.639) | 94.3(0.808) | 93.3(1.03)
MAE | 52.5(5.53) | 51.9(5.98) | 53.1(4.41) | 51.9(5.48) | 52.3(5.36) | 52.1(5.48) | 49.5(4.14)
Letter | ALDR-KL | 94.3(0.336) | 92.9(0.306) | 89.7(0.796) | 70.1(4.21) | 94.3(0.174) | 93.4(0.229) | 91.8(0.427)
LDR-KL | 93.5(0.108) | 93.0(0.406) | 89.5(1.0) | 70.3(3.98) | 92.8(0.468) | 92.7(0.216) | 91.2(0.399)
CE | 91.8(0.12) | 90.6(0.159) | 87.7(0.511) | 40.5(8.44) | 91.6(0.169) | 90.1(0.129) | 88.6(0.223)
SCE | 91.8(0.143) | 90.7(0.169) | 87.0(0.584) | 43.2(3.21) | 91.5(0.117) | 90.1(0.314) | 88.6(0.379)
GCE | 91.5(0.126) | 90.3(0.215) | 86.2(0.514) | 42.0(2.35) | 91.1(0.08) | 89.9(0.223) | 88.3(0.343)
TGCE | 91.5(0.125) | 90.3(0.21) | 87.5(0.745) | 41.8(2.39) | 91.0(0.081) | 89.8(0.196) | 88.1(0.394)
WW | 91.0(0.108) | 90.4(0.159) | 88.5(0.6) | 42.8(4.43) | 90.5(0.116) | 89.2(0.153) | 86.7(0.223)
JS | 90.3(0.246) | 89.2(0.177) | 80.7(0.606) | 31.8(1.72) | 90.1(0.191) | 89.3(0.187) | 87.1(0.522)
CS | 91.0(0.244) | 89.9(0.405) | 88.0(0.219) | 56.3(5.13) | 90.2(0.159) | 88.6(0.289) | 86.7(0.484)
RLL | 88.4(0.174) | 84.0(0.24) | 61.6(0.612) | 23.6(3.09) | 88.0(0.242) | 87.0(0.196) | 82.8(1.06)
NCE+RCE | 72.1(1.19) | 65.8(2.56) | 57.1(5.08) | 32.8(3.36) | 69.6(1.24) | 63.9(1.1) | 55.6(1.19)
NCE+AUL | 70.9(4.05) | 64.3(1.88) | 55.9(2.85) | 28.4(2.64) | 64.5(1.64) | 56.0(2.18) | 52.0(2.07)
NCE+AGCE | 63.5(2.32) | 58.5(3.16) | 50.1(3.48) | 22.7(1.88) | 61.2(2.42) | 55.2(1.37) | 51.5(1.82)
MSE | 53.4(0.907) | 46.9(1.62) | 36.5(2.63) | 22.2(1.82) | 51.0(1.43) | 47.4(1.78) | 44.9(2.43)
MAE | 21.1(1.16) | 21.0(1.3) | 20.4(1.5) | 20.4(1.75) | 21.0(1.34) | 20.9(1.5) | 20.3(1.31)
News20 | ALDR-KL | 98.6(0.072) | 97.2(0.149) | 93.0(0.768) | 50.9(2.19) | 98.6(0.14) | 98.2(0.157) | 98.0(0.337)
LDR-KL | 98.6(0.132) | 97.0(0.303) | 92.9(0.63) | 50.2(3.46) | 98.5(0.119) | 98.3(0.123) | 98.1(0.17)
CE | 92.6(0.306) | 74.8(0.619) | 45.0(2.67) | 25.4(1.15) | 91.9(0.17) | 92.0(0.254) | 91.6(0.226)
SCE | 91.6(0.282) | 71.6(0.778) | 44.3(4.5) | 26.2(1.94) | 90.8(0.226) | 91.3(0.203) | 90.8(0.275)
GCE | 87.6(0.357) | 64.3(0.357) | 41.3(4.15) | 24.7(0.799) | 86.6(0.591) | 87.0(0.632) | 86.9(0.378)
TGCE | 86.2(0.554) | 64.0(0.514) | 40.9(4.29) | 24.7(0.799) | 85.5(0.613) | 86.2(0.656) | 86.2(0.82)
WW | 88.7(0.425) | 72.3(1.27) | 47.9(3.18) | 26.0(2.36) | 88.6(0.358) | 88.5(0.214) | 87.9(0.346)
JS | 58.7(0.538) | 44.0(0.663) | 34.6(2.3) | 25.2(1.55) | 58.5(0.951) | 57.3(0.561) | 57.0(0.977)
CS | 96.7(0.664) | 97.2(0.182) | 85.1(1.51) | 30.0(3.31) | 96.7(0.387) | 96.9(0.522) | 96.4(0.552)
RLL | 40.8(1.05) | 33.0(1.57) | 31.2(2.23) | 25.4(1.18) | 40.6(0.837) | 41.6(1.03) | 41.0(1.17)
NCE+RCE | 96.9(0.201) | 86.0(3.13) | 42.5(3.52) | 25.6(1.96) | 95.0(2.02) | 73.3(1.42) | 68.5(0.604)
NCE+AUL | 67.6(1.11) | 41.1(1.0) | 37.4(2.68) | 24.6(0.774) | 56.8(1.36) | 51.2(2.35) | 48.5(1.9)
NCE+AGCE | 44.6(2.77) | 35.0(0.94) | 33.7(3.99) | 25.0(1.23) | 42.4(4.11) | 38.7(1.97) | 38.8(2.18)
MSE | 33.9(1.96) | 30.6(0.669) | 29.8(0.907) | 24.8(0.62) | 32.6(1.89) | 31.5(2.33) | 31.5(1.61)
MAE | 26.1(0.276) | 26.1(0.276) | 25.8(1.03) | 24.9(1.16) | 26.1(0.276) | 26.1(0.276) | 26.1(0.276)
ALOI | ALDR-KL | 99.0(0.069) | 96.7(0.118) | 92.8(0.14) | 50.7(0.693) | 98.2(0.047) | 96.5(0.075) | 94.5(0.187)
LDR-KL | 98.4(0.075) | 96.7(0.111) | 93.3(0.146) | 50.8(0.416) | 97.2(0.34) | 95.5(0.068) | 92.8(0.147)
CE | 89.8(0.059) | 85.5(0.181) | 69.1(0.627) | 11.4(0.708) | 89.1(0.113) | 83.7(0.173) | 62.5(0.417)
SCE | 89.5(0.1) | 84.7(0.166) | 67.2(0.647) | 11.4(0.615) | 88.6(0.141) | 83.0(0.181) | 60.5(0.569)
GCE | 87.9(0.086) | 80.8(0.163) | 57.8(0.51) | 8.58(0.893) | 86.6(0.173) | 78.8(0.299) | 51.2(0.291)
TGCE | 87.3(0.059) | 79.9(0.185) | 56.5(0.638) | 8.58(0.893) | 85.8(0.226) | 77.5(0.343) | 49.3(0.352)
WW | 84.2(0.41) | 76.0(0.52) | 57.5(0.175) | 10.5(0.205) | 77.0(0.362) | 57.0(0.344) | 31.8(0.303)
JS | 11.0(0.743) | 9.69(0.529) | 5.55(0.492) | 0.62(0.129) | 10.6(0.935) | 8.18(0.719) | 5.32(0.324)
CS | 94.1(0.192) | 87.1(0.349) | 47.9(0.514) | 4.77(0.468) | 92.5(0.105) | 89.4(0.124) | 78.3(0.241)
RLL | 2.17(0.384) | 1.53(0.274) | 0.87(0.209) | 0.524(0.065) | 1.98(0.31) | 1.57(0.145) | 1.27(0.088)
NCE+RCE | 8.55(0.52) | 8.34(0.598) | 6.95(0.589) | 1.03(0.387) | 8.44(0.687) | 7.11(0.385) | 4.73(0.215)
NCE+AUL | 8.76(0.631) | 6.27(0.422) | 2.65(0.36) | 0.702(0.309) | 8.07(0.822) | 5.79(0.436) | 3.98(0.198)
NCE+AGCE | 6.99(0.535) | 4.26(0.589) | 1.92(0.297) | 0.609(0.129) | 6.15(0.568) | 4.26(0.506) | 2.99(0.185)
MSE | 0.926(0.242) | 0.811(0.197) | 0.744(0.164) | 0.493(0.033) | 0.88(0.214) | 0.83(0.224) | 0.8(0.165)
MAE | 0.635(0.067) | 0.617(0.089) | 0.585(0.092) | 0.581(0.1) | 0.611(0.09) | 0.565(0.108) | 0.583(0.088)

Table 15: Testing Top-5 Accuracy (%) with mean and standard deviation for
image dataset. The highest values are marked as bold.

Dataset | Loss | Clean | Uniform 0.3 | Uniform 0.6 | Uniform 0.9 | CD 0.1 | CD 0.3 | CD 0.5
---|---|---|---|---|---|---|---|---
Kuzushiji-49 | ALDR-KL | 98.9(0.129) | 98.4(0.059) | 96.5(0.143) | 67.3(1.97) | 98.6(0.065) | 98.4(0.037) | 98.1(0.151)
LDR-KL | 98.9(0.033) | 98.1(0.352) | 96.5(0.571) | 66.4(1.01) | 98.5(0.052) | 98.4(0.06) | 98.2(0.053)
CE | 99.1(0.096) | 98.3(0.063) | 93.2(0.226) | 54.4(1.57) | 98.5(0.055) | 98.4(0.056) | 98.2(0.051)
SCE | 99.1(0.138) | 98.1(0.464) | 93.0(0.377) | 53.0(1.94) | 98.6(0.042) | 98.4(0.048) | 98.1(0.046)
GCE | 99.1(0.148) | 98.4(0.042) | 92.4(0.31) | 51.9(2.02) | 98.5(0.024) | 98.3(0.07) | 98.1(0.045)
TGCE | 99.0(0.112) | 98.0(0.341) | 92.3(0.329) | 53.1(0.717) | 98.5(0.046) | 98.3(0.053) | 98.1(0.079)
WW | 99.2(0.157) | 97.9(0.065) | 94.8(0.308) | 53.7(0.948) | 98.7(0.137) | 98.7(0.1) | 98.6(0.152)
JS | 98.9(0.012) | 96.0(0.597) | 91.7(0.722) | 51.9(1.07) | 97.9(0.7) | 96.1(0.068) | 95.8(0.087)
CS | 98.8(0.072) | 94.2(1.82) | 16.1(3.25) | 10.2(0.022) | 98.3(0.039) | 96.5(0.642) | 73.1(2.97)
RLL | 93.2(0.064) | 92.9(0.118) | 84.8(1.11) | 48.9(0.645) | 93.1(0.037) | 91.7(0.588) | 92.4(0.827)
NCE+RCE | 93.0(0.39) | 92.4(0.226) | 72.5(0.659) | 25.0(1.22) | 92.7(0.108) | 91.9(0.06) | 90.7(0.507)
NCE+AUL | 93.0(0.036) | 87.6(0.85) | 69.0(0.774) | 27.3(2.64) | 92.9(0.051) | 94.0(0.081) | 93.7(0.06)
NCE+AGCE | 92.7(0.046) | 78.5(2.37) | 61.3(0.89) | 27.0(1.83) | 92.9(0.055) | 93.8(0.177) | 93.3(0.242)
MSE | 84.4(1.66) | 59.0(1.57) | 37.3(1.19) | 17.3(0.961) | 64.8(1.67) | 52.0(1.85) | 35.8(3.73)
MAE | 10.3(0.069) | 35.9(2.23) | 21.6(1.27) | 15.7(1.07) | 39.8(2.21) | 24.5(2.2) | 19.9(1.39)
CIFAR100 | ALDR-KL | 86.3(0.455) | 80.3(0.39) | 66.3(0.585) | 15.7(1.12) | 83.1(0.534) | 78.5(0.563) | 73.5(0.581)
LDR-KL | 86.4(0.376) | 79.7(0.558) | 66.2(0.653) | 15.9(0.933) | 83.0(0.172) | 77.8(0.651) | 74.0(0.68)
CE | 85.5(0.508) | 78.0(0.622) | 62.2(1.11) | 15.8(1.46) | 82.2(0.245) | 77.4(0.639) | 73.6(0.372)
SCE | 85.5(0.628) | 77.9(0.97) | 61.6(1.06) | 16.3(1.57) | 82.1(0.264) | 77.6(0.507) | 73.4(0.516)
GCE | 85.9(0.17) | 78.4(0.774) | 62.5(0.854) | 16.0(1.14) | 82.3(0.577) | 77.7(0.497) | 73.6(0.157)
TGCE | 85.3(0.329) | 78.4(0.77) | 59.7(0.395) | 15.2(1.8) | 82.6(0.422) | 78.0(0.479) | 72.3(0.54)
WW | 83.3(0.409) | 72.0(0.522) | 52.2(0.918) | 16.8(0.596) | 80.6(0.465) | 77.1(0.189) | 70.4(0.505)
JS | 84.5(0.349) | 79.3(0.8) | 54.5(1.04) | 15.2(1.04) | 83.4(0.374) | 76.0(1.11) | 68.7(0.489)
CS | 29.8(0.888) | 16.8(1.1) | 6.52(0.596) | 5.0(0.0) | 24.9(1.1) | 18.5(0.597) | 13.2(1.12)
RLL | 58.8(2.08) | 51.4(1.64) | 31.0(0.911) | 14.8(0.787) | 56.7(1.49) | 50.3(3.02) | 36.9(1.81)
NCE+RCE | 23.6(0.616) | 20.1(1.2) | 17.3(0.963) | 8.74(2.01) | 22.5(0.671) | 19.6(0.74) | 14.2(0.477)
NCE+AUL | 27.9(0.602) | 23.8(0.661) | 18.9(0.614) | 11.1(3.16) | 26.6(0.486) | 23.2(0.945) | 17.7(0.264)
NCE+AGCE | 28.2(0.841) | 24.3(0.492) | 19.1(0.85) | 11.8(0.931) | 26.7(0.48) | 23.2(1.08) | 17.9(0.182)
MSE | 31.9(0.519) | 28.9(0.992) | 25.5(0.494) | 15.8(0.558) | 30.3(0.557) | 27.1(0.696) | 20.6(0.592)
MAE | 5.11(0.161) | 5.12(0.15) | 5.15(0.128) | 5.03(0.163) | 5.03(0.291) | 5.13(0.145) | 4.88(0.356)
Tiny-ImageNet | ALDR-KL | 73.0(0.216) | 64.4(0.354) | 47.4(0.827) | 5.5(0.527) | 69.0(0.212) | 63.8(0.185) | 58.1(0.295)
LDR-KL | 72.4(0.174) | 63.9(0.477) | 47.8(0.693) | 6.15(0.338) | 68.5(0.32) | 63.1(0.254) | 58.9(0.383)
CE | 73.3(0.219) | 62.9(0.28) | 38.0(0.557) | 4.36(0.76) | 70.8(0.203) | 65.5(0.38) | 58.7(0.263)
SCE | 73.3(0.111) | 62.8(0.359) | 37.4(0.98) | 6.72(0.332) | 70.5(0.26) | 65.4(0.152) | 58.7(0.313)
GCE | 73.1(0.272) | 62.5(0.542) | 33.7(0.599) | 4.35(0.65) | 70.6(0.126) | 64.9(0.14) | 58.2(0.249)
TGCE | 71.6(0.087) | 58.8(0.229) | 31.3(0.514) | 4.84(0.498) | 68.9(0.311) | 62.8(0.174) | 53.8(0.432)
WW | 62.6(0.248) | 49.8(0.357) | 31.7(0.284) | 4.54(0.23) | 59.8(0.446) | 55.8(0.224) | 44.6(0.548)
JS | 61.5(0.403) | 37.1(0.774) | 15.2(0.892) | 5.51(0.464) | 55.8(0.842) | 40.4(0.241) | 26.6(1.45)
CS | 3.98(0.328) | 2.69(0.165) | 2.5(0.0) | 2.5(0.0) | 3.27(0.303) | 2.76(0.09) | 2.7(0.242)
RLL | 15.2(1.48) | 10.9(0.915) | 8.34(0.455) | 4.55(1.0) | 12.3(0.401) | 10.2(0.751) | 7.71(0.358)
NCE+RCE | 6.78(0.139) | 6.48(0.493) | 5.22(0.178) | 2.79(0.345) | 6.43(0.506) | 5.95(0.207) | 5.0(0.217)
NCE+AUL | 7.72(0.263) | 6.74(0.248) | 5.65(0.641) | 3.5(0.525) | 7.41(0.272) | 6.72(0.265) | 5.76(0.346)
NCE+AGCE | 7.65(0.408) | 7.01(0.278) | 6.21(0.345) | 3.78(0.382) | 7.75(0.279) | 6.79(0.318) | 5.77(0.178)
MSE | 9.11(0.375) | 4.59(0.356) | 4.18(0.341) | 3.28(0.109) | 4.76(0.629) | 4.55(0.27) | 4.22(0.093)
MAE | 2.57(0.107) | 3.97(0.31) | 3.46(0.364) | 3.31(0.478) | 4.14(0.354) | 4.02(0.241) | 3.92(0.13)

###  L.3 Setups for Mini-Webvision Experiments

We adopt the noisy Google resized version from Webvision version 1.0 as
training dataset (only for the first 50 classes) (Li et al., 2017) and do
evaluation on the ILSVRC 2012 validation data (only for the first 50 classes).
The total training epochs is set as 250. The weight decay is set as 3e-5. SGD
optimizer is utilized with nesterov momentum as 0.9, initial learning rate as
0.4 that is epoch-wise decreased by 0.97. Typical data augmentations including
color jittering, random width/height shift and random horizontal flip are
applied. For our proposed LDR-KL and ALDR-KL, we apply SoftPlus function to
make model output $\mathbf{f}$ to be positive. The results are presented at
Table 3.

###  L.4 Leaderboard with Standard Deviation

In addition to the averaged rank for the leaderboard at Table 3, we provide
the leaderboard with standard deviation at Table 16.

Table 16: leaderboard for comparing 15 different loss functions on 7 datasets in 6 noise and 1 clean settings. The reported numbers are averaged ranks of performance. The smaller the better. Loss Function | top-1 | top-2 | top-3 | top-4 | top-5 | overall
---|---|---|---|---|---|---
ALDR-KL | 2.163(1.754) | 2.469(2.149) | 2.245(1.933) | 2.224(1.951) | 2.673(2.543) | 2.355(2.092)
LDR-KL | 2.449(1.819) | 2.571(1.841) | 2.776(2.043) | 3.0(2.138) | 2.959(2.109) | 2.751(2.006)
CE | 4.714(1.852) | 4.592(2.465) | 4.224(2.131) | 4.449(2.148) | 4.388(2.184) | 4.473(2.171)
SCE | 4.959(1.958) | 4.816(1.769) | 4.449(1.63) | 4.918(2.174) | 4.469(1.63) | 4.722(1.857)
GCE | 5.796(2.39) | 5.347(2.462) | 6.061(2.18) | 5.551(2.167) | 5.571(2.241) | 5.665(2.304)
TGCE | 6.204(2.204) | 6.204(1.948) | 6.286(2.109) | 6.204(1.84) | 6.306(1.929) | 6.241(2.011)
WW | 7.673(2.198) | 6.592(2.465) | 6.061(2.377) | 5.898(2.35) | 5.469(2.492) | 6.339(2.496)
JS | 7.816(2.946) | 7.837(2.637) | 7.857(2.295) | 7.98(2.114) | 8.245(2.005) | 7.947(2.43)
CS | 8.653(4.943) | 8.857(4.699) | 8.755(4.506) | 8.551(4.764) | 8.714(4.84) | 8.706(4.754)
RLL | 10.184(2.569) | 10.224(1.951) | 10.224(2.41) | 10.49(2.34) | 10.408(2.166) | 10.306(2.3)
NCE+RCE | 9.694(3.065) | 10.633(2.686) | 10.878(2.553) | 10.612(2.798) | 10.714(2.483) | 10.506(2.756)
NCE+AUL | 10.449(2.167) | 10.98(1.436) | 11.102(1.297) | 11.245(1.17) | 11.163(1.633) | 10.988(1.605)
NCE+AGCE | 11.735(1.613) | 11.837(1.448) | 11.878(1.56) | 11.51(1.704) | 11.673(1.038) | 11.727(1.496)
MSE | 12.776(2.216) | 12.612(2.64) | 12.735(2.126) | 12.939(1.921) | 12.878(2.067) | 12.788(2.21)
MAE | 14.735(0.563) | 14.429(1.666) | 14.469(1.739) | 14.429(2.06) | 14.367(2.087) | 14.486(1.72)

###  L.5 Convergence for ALDR-KL Optimization

We show the practical convergence curves (mean value with standard deviation
band) for Algorithm 1 for ALDR-KL loss at this section. ‘CD’ is short for
class-dependent noise; ‘U’ is short for uniform noise; ‘$c$’ is the margin
value; initial learning rate $\eta_{0}$ is tuned in $\\{1e-1,1e-2,1e-3\\}$.
The convergence curves on ALOI dataset is shown in Figure 4; the convergence
curves on News20 dataset is shown in Figure 5; the convergence curves on
Letter dataset is shown in Figure 6; the convergence curves on Vowel dataset
is shown in Figure 7.

(a) CD(0.1), $c=0.1$ (b) CD(0.1), $c=1$ (c) CD(0.1), $c=10$ (d) CD(0.3),
$c=0.1$ (e) CD(0.3), $c=1$ (f) CD(0.3), $c=10$ (g) CD(0.5), $c=0.1$ (h)
CD(0.5), $c=1$ (i) CD(0.5), $c=10$ (j) U(0.3), $c=0.1$ (k) U(0.3), $c=1$ (l)
U(0.3), $c=10$ (m) U(0.6), $c=0.1$ (n) U(0.6), $c=1$ (o) U(0.6), $c=10$ (p)
U(0.9), $c=0.1$ (q) U(0.9), $c=1$ (r) U(0.9), $c=10$

Figure 4: Training loss convergence for ALDR-KL (Algorithm 1) on ALOI dataset

(a) CD(0.1), $c=0.1$ (b) CD(0.1), $c=1$ (c) CD(0.1), $c=10$ (d) CD(0.3),
$c=0.1$ (e) CD(0.3), $c=1$ (f) CD(0.3), $c=10$ (g) CD(0.5), $c=0.1$ (h)
CD(0.5), $c=1$ (i) CD(0.5), $c=10$ (j) U(0.3), $c=0.1$ (k) U(0.3), $c=1$ (l)
U(0.3), $c=10$ (m) U(0.6), $c=0.1$ (n) U(0.6), $c=1$ (o) U(0.6), $c=10$ (p)
U(0.9), $c=0.1$ (q) U(0.9), $c=1$ (r) U(0.9), $c=10$

Figure 5: Training loss convergence for ALDR-KL (Algorithm 1) on News20
dataset

(a) CD(0.1), $c=0.1$ (b) CD(0.1), $c=1$ (c) CD(0.1), $c=10$ (d) CD(0.3),
$c=0.1$ (e) CD(0.3), $c=1$ (f) CD(0.3), $c=10$ (g) CD(0.5), $c=0.1$ (h)
CD(0.5), $c=1$ (i) CD(0.5), $c=10$ (j) U(0.3), $c=0.1$ (k) U(0.3), $c=1$ (l)
U(0.3), $c=10$ (m) U(0.6), $c=0.1$ (n) U(0.6), $c=1$ (o) U(0.6), $c=10$ (p)
U(0.9), $c=0.1$ (q) U(0.9), $c=1$ (r) U(0.9), $c=10$

Figure 6: Training loss convergence for ALDR-KL (Algorithm 1) on Letter
dataset

(a) CD(0.1), $c=0.1$ (b) CD(0.1), $c=1$ (c) CD(0.1), $c=10$ (d) CD(0.3),
$c=0.1$ (e) CD(0.3), $c=1$ (f) CD(0.3), $c=10$ (g) CD(0.5), $c=0.1$ (h)
CD(0.5), $c=1$ (i) CD(0.5), $c=10$ (j) U(0.3), $c=0.1$ (k) U(0.3), $c=1$ (l)
U(0.3), $c=10$ (m) U(0.6), $c=0.1$ (n) U(0.6), $c=1$ (o) U(0.6), $c=10$ (p)
U(0.9), $c=0.1$ (q) U(0.9), $c=1$ (r) U(0.9), $c=10$

Figure 7: Training loss convergence for ALDR-KL (Algorithm 1) on Vowel dataset

###  L.6 More Synthetic Experiments

We additionally provide the synthetic experiments for training from scratch
setting in Figure 8, and LDR-KL loss in Figure 9 and Figure 8. The
experimental settings are kept as the same, except for training from scratch
setting, the total training epoch is fixed as 200 for all methods. The
$\lambda$ parameter for LDR-KL loss is set as the mean value from the
optimized $\lambda$ from ALDR-KL loss. From the results, the ALDR-KL loss
consistently enjoys the most robust decision boundary.

Figure 8: Design: training from scratch. Left: decision boundary for CE loss;
Middle: decision boundary for LDR-KL loss with $\lambda$ set as
$\mathbb{E}_{\mathbf{x}_{i},t}[\lambda^{i}_{t}]$ from ALDR-KL loss; Right:
decision boundary for ALDR-KL loss.  Figure 9: Design: pretrained from CE loss
on clean data. Left: decision boundary for pretrained model with CE loss;
Middle: decision boundary for LDR-KL loss with $\lambda$ set as
$\mathbb{E}_{\mathbf{x}_{i},t}[\lambda^{i}_{t}]$ from ALDR-KL loss; Right:
decision boundary for ALDR-KL loss.

###  L.7 Running Time Cost

We provide the empirical running time cost for all baselines in Table 17. Each
entry stands for mean and standard deviation for 100 consecutive epochs
running on a x86_64 GNU/Linux cluster with NVIDIA GeForce GTX 1080 Ti GPU
card.

Table 17: Running time for 15 baselines on 7 benchmark datasets (seconds per
epoch).

Loss | Vowel | Letter | News20 | ALOI | Kuzushiji-49 | CIFAR100 | Tiny-ImageNet
---|---|---|---|---|---|---|---
ALDR-KL | 0.176(0.009) | 0.933(0.033) | 2.002(0.068) | 7.029(0.091) | 121.123(1.767) | 31.923(0.381) | 61.204(0.26)
LDR-KL | 0.172(0.006) | 0.783(0.033) | 1.868(0.107) | 5.779(0.098) | 116.774(0.512) | 31.507(0.826) | 59.106(0.318)
CE | 0.17(0.008) | 0.719(0.027) | 1.846(0.095) | 5.157(0.074) | 116.612(0.296) | 31.49(0.289) | 58.687(0.141)
SCE | 0.167(0.008) | 0.756(0.024) | 2.082(0.081) | 5.903(0.175) | 120.376(0.275) | 29.97(0.156) | 60.336(0.456)
GCE | 0.165(0.008) | 0.771(0.029) | 1.869(0.079) | 5.772(0.42) | 122.294(0.268) | 30.373(0.187) | 61.026(0.213)
TGCE | 0.178(0.009) | 0.769(0.03) | 1.921(0.077) | 5.813(0.193) | 120.343(1.339) | 30.293(0.163) | 58.869(0.765)
WW | 0.155(0.009) | 0.715(0.028) | 2.067(0.068) | 5.255(0.165) | 127.304(0.49) | 29.386(0.148) | 63.249(0.666)
JS | 0.161(0.011) | 0.876(0.034) | 1.942(0.108) | 6.648(0.1) | 118.172(0.279) | 31.618(0.259) | 59.562(0.14)
CS | 0.158(0.012) | 0.73(0.036) | 1.909(0.084) | 5.393(0.178) | 120.702(1.923) | 29.278(0.139) | 60.391(1.28)
RLL | 0.172(0.008) | 0.794(0.024) | 2.118(0.077) | 6.198(0.157) | 122.021(0.339) | 30.35(0.48) | 60.609(0.785)
NCE+RCE | 0.177(0.007) | 0.818(0.037) | 2.264(0.085) | 6.326(0.194) | 116.682(1.909) | 30.139(0.124) | 59.967(0.589)
NCE+AUL | 0.174(0.007) | 0.835(0.031) | 2.154(0.121) | 6.464(0.194) | 115.613(0.766) | 29.951(0.12) | 60.022(0.49)
NCE+AGCE | 0.169(0.01) | 0.835(0.039) | 2.21(0.122) | 6.418(0.203) | 121.702(1.55) | 29.632(0.063) | 63.533(0.499)
MSE | 0.158(0.006) | 0.702(0.025) | 1.932(0.089) | 4.983(0.158) | 117.601(1.364) | 29.951(0.46) | 59.44(0.684)
MAE | 0.163(0.011) | 0.687(0.031) | 1.884(0.263) | 4.843(0.179) | 119.065(1.854) | 29.404(0.092) | 61.176(1.256)

###  L.8 Ablation Study for $\lambda$ and $\lambda_{0}$

We addtionally show the validation results for LDR-KL and ALDR-KL losses on
CIFAR100 dataset with different $\lambda$ and $\lambda_{0}$ values in Table
18. When noisy level is higher, LDR-KL or ALDR-KL loss prefer larger $\lambda$
or $\lambda_{0}$ (1 over 0.1) on CIFAR100 dataset.

Table 18: The mean and standard deviation for top-1 validation accurcay on
CIFAR100 dataset. The best choice is marked as bold.

Loss | LDR-KL | ALDR-KL
---|---|---
Noise setting |  $\lambda$=0.1 |  $\lambda$=1 |  $\lambda$=10 |  $\lambda_{0}$=0.1 |  $\lambda_{0}$=1 |  $\lambda_{0}$=10
Clean | 68.948(0.211) | 66.848(0.465) | 61.528(0.665) | 68.456(0.351) | 66.54(0.304) | 60.702(0.332)
Uniform 0.3 | 40.658(0.218) | 38.918(0.337) | 36.914(0.466) | 40.872(0.259) | 38.888(0.24) | 36.958(0.255)
Uniform 0.6 | 13.462(0.831) | 16.084(0.467) | 14.766(0.306) | 13.196(0.821) | 16.038(0.55) | 14.976(0.158)
Uniform 0.9 | 1.414(0.086) | 1.46(0.088) | 1.348(0.063) | 1.444(0.084) | 1.468(0.044) | 1.366(0.118)
CD 0.1 | 59.346(0.258) | 56.478(0.376) | 51.696(0.718) | 59.368(0.32) | 55.99(0.328) | 52.252(0.416)
CD 0.3 | 43.198(0.434) | 40.098(0.375) | 33.89(1.045) | 43.272(0.34) | 39.66(0.445) | 34.354(1.212)
CD 0.5 | 32.026(0.373) | 32.344(0.373) | 25.672(0.379) | 31.916(0.286) | 32.378(0.333) | 26.396(0.637)


# Ramsey-type results for path covers and path partitions. II. Digraphs

Shuya<EMAIL_ADDRESS>Michitaka
<EMAIL_ADDRESS>
1Applied Mathematics, Faculty of Advanced Science and Technology,
Kumamoto University,
2-39-1 Kurokami, Kumamoto 860-8555, Japan
2College of Liberal Arts and Sciences,
Kitasato University,
1-15-1 Kitasato, Minami-ku, Sagamihara, Kanagawa 252-0373, Japan

###### Abstract

Recently, the authors [4] gave Ramsey-type results for the path
cover/partition number of graphs. In this paper, we continue the research
about them focusing on digraphs, and find a relationship between the path
cover/partition number and forbidden structures in digraphs.

Let $D$ be a weakly connected digraph. A family $\mathcal{P}$ of subdigraphs
of $D$ is called a path cover (resp. a path partition) of $D$ if
$\bigcup_{P\in\mathcal{P}}V(P)=V(D)$ (resp.
$\dot{\bigcup}_{P\in\mathcal{P}}V(P)=V(D)$) and every element of $\mathcal{P}$
is a directed path. The minimum cardinality of a path cover (resp. a path
partition) of $D$ is denoted by ${\rm pc}(D)$ (resp. ${\rm pp}(D)$). In this
paper, we find forbidden structure conditions assuring us that ${\rm pc}(D)$
(or ${\rm pp}(D)$) is bounded by a constant.

Key words and phrases. digraph, path cover number, path partition number,
forbidden subdigraph, Ramsey number

AMS 2020 Mathematics Subject Classification. 05C20, 05C38, 05C55.

##  1 Introduction

###  1.1 Definitions

All graphs and digraphs considered in this paper are finite and simple.
Furthermore, to simplify the situations, we assume that all digraphs in this
paper have no $2$-cycles (and such digraphs are sometimes called oriented
graphs). However, one might notice that our results are easily extended to
digraphs with $2$-cycles. For terms and symbols not defined in this paper, we
refer the reader to [8].

Let $G$ be a graph. Let $V(G)$ and $E(G)$ denote the vertex set and the edge
set of $G$, respectively. For a vertex $x\in V(G)$, let $N_{G}(x)$ denote the
neighborhood of $x$ in $G$; thus $N_{G}(x)=\\{y\in V(G):xy\in E(G)\\}$. For a
subset $X$ of $V(G)$, let $N_{G}(X)=(\bigcup_{x\in X}N_{G}(x))\setminus X$.
Let $\alpha(G)$ denote the independence number of $G$, i.e., the maximum
cardinality of an independent set of $G$. Let $K_{n}$, $P_{n}$ and $K_{1,n}$
denote the complete graph of order $n$, the path of order $n$ and the star of
order $n+1$, respectively. For two positive integers $n_{1}$ and $n_{2}$, the
Ramsey number $R(n_{1},n_{2})$ is the minimum positive integer $R$ such that
any graph of order at least $R$ contains a clique of cardinality $n_{1}$ or an
independent set of cardinality $n_{2}$.

Let $D$ be a digraph. Let $V(D)$ and $E(D)$ denote the vertex set and the arc
set of $D$, respectively. Let $G_{D}$ be the underlying graph of $D$, i.e.,
$G_{D}$ is the graph on $V(D)$ with $E(G_{D})=\\{xy:(x,y)\in E(D)\mbox{ or
}(y,x)\in E(D)\\}$. A digraph is said to be weakly connected if its underlying
graph is connected. For a vertex $x\in V(D)$, let $d^{+}_{D}(x)$ and
$d^{-}_{D}(x)$ denote the out-degree and in-degree of $x$ in $D$,
respectively; thus $d^{+}_{D}(x)=|\\{y\in V(D):(x,y)\in E(D)\\}|$ and
$d^{-}_{D}(x)=|\\{y\in V(D):(y,x)\in E(D)\\}|$. A digraph $P$ is a pseudo-path
if $G_{P}$ is a path. For a pseudo-path $P$, let $r(P)=|\\{x\in
V(P):d_{P}^{+}(x)=2\mbox{ or }d_{P}^{-}(x)=2\\}|$. A pseudo-path $P$ is called
a directed path if $r(P)=0$. A (non-oriented) path $P$ with
$V(P)=\\{x_{i}:1\leq i\leq l\\}$ and $E(P)=\\{x_{i}x_{i+1}:1\leq i\leq l-1\\}$
is often denoted by $P=x_{1}x_{2}\cdots x_{l}$. Furthermore, if there is no
fear of confusion, a directed path $P$ with $V(P)=\\{x_{i}:1\leq i\leq l\\}$
and $E(P)=\\{(x_{i},x_{i+1}):1\leq i\leq l-1\\}$ is also denoted by
$P=x_{1}x_{2}\cdots x_{l}$.

For a (di)graph $\Gamma$ and a subset $X$ of $V(\Gamma)$, let $\Gamma[X]$
(resp. $\Gamma-X$) denote the sub(di)graph of $\Gamma$ induced by $X$ (resp.
$V(\Gamma)\setminus X$). For two (di)graphs $\Gamma$ and $\Gamma^{\prime}$,
$\Gamma$ is said to be $\Gamma^{\prime}$-free if $\Gamma$ contains no induced
copy of $\Gamma^{\prime}$. For a family ${\mathcal{G}}$ of (di)graphs, a
(di)graph $\Gamma$ is said to be ${\mathcal{G}}$-free if $\Gamma$ is
$\Gamma^{\prime}$-free for every $\Gamma^{\prime}\in{\mathcal{G}}$. In this
context, the members of ${\mathcal{G}}$ are called forbidden sub(di)graphs.

Let $\Gamma$ be a (di)graph. When $\Gamma$ is a graph, a family
${\mathcal{P}}$ of subgraphs of $\Gamma$ is called a path cover of $\Gamma$ if
$\bigcup_{P\in{\mathcal{P}}}V(P)=V(\Gamma)$ and each element of
${\mathcal{P}}$ is a path. When $\Gamma$ is a digraph, a family
${\mathcal{P}}$ of subdigraphs of $\Gamma$ is called a path cover of $\Gamma$
if $\bigcup_{P\in{\mathcal{P}}}V(P)=V(\Gamma)$ and each element of
${\mathcal{P}}$ is a directed path. Note that some elements of a path cover of
$\Gamma$ might have common vertices. A path cover ${\mathcal{P}}$ of $\Gamma$
is called a path partition of $\Gamma$ if the elements of ${\mathcal{P}}$ are
pairwise vertex-disjoint. Since $\\{\Gamma[\\{x\\}]:x\in V(\Gamma)\\}$ is a
path partition of $\Gamma$ (and so it is a path cover of $\Gamma$), the
minimum cardinality of a path cover (or a path partition) of any (di)graph is
well-defined. The value $\min\\{|{\mathcal{P}}|:{\mathcal{P}}\mbox{ is a path
cover of }\Gamma\\}$ (resp. $\min\\{|{\mathcal{P}}|:{\mathcal{P}}\mbox{ is a
path partition of }\Gamma\\}$), denoted by ${\rm pc}(\Gamma)$ (resp. ${\rm
pp}(\Gamma)$), is called the path cover number (resp. the path partition
number) of $\Gamma$. It is trivial that ${\rm pc}(\Gamma)\leq{\rm
pp}(\Gamma)$. Since a digraph $D$ has a Hamiltonian directed path if and only
if ${\rm pp}(D)=1$, the decision problem for the path partition number is a
natural generalization of the Hamiltonian directed path problem in digraphs.

###  1.2 Ramsey-type problem and main results

The statement of a classical Ramsey theorem equals to the following: For an
integer $n\geq 1$, there exists a constant $c=c(n)$ depending on $n$ only such
that every $\\{K_{n},\overline{K_{n}}\\}$-free graph $G$ satisfies $|V(G)|\leq
c$, where $\overline{K_{n}}$ is the complement of $K_{n}$. Its analogy for
connected graphs is well-known as a folklore (see [8, Proposition 9.4.1]): For
an integer $n\geq 1$, there exists a constant $c^{\prime}=c^{\prime}(n)$
depending on $n$ only such that every connected
$\\{K_{n},K_{1,n},P_{n}\\}$-free graph $G$ satisfies $|V(G)|\leq c^{\prime}$.
Furthermore, some researchers have tried to extend the result to a theorem for
some invariants (other than order), and found Ramsey-type properties which
claim the following (see, for example, [3, 6, 7, 11]): For a given graph-
invariant $\mu$, if we impose forbidden structure conditions on a connected
graph $G$, then $\mu(G)$ is bounded by a constant.

Recently, the authors [4] gave Ramsey-type theorems for the path
cover/partition number of graphs (see Theorem A below). In this paper, we
continue the research about them focusing on digraphs, and find a relationship
between the path cover/partition number and forbidden structures in digraphs.
Although

  1. $\bullet$

the problems finding a longest directed path or a path partition in digraphs
are major topics in graph theory (see [1, 2, 5, 16, 17, 18]) and

  2. $\bullet$

there are many results on forbidden subgraph conditions for the existence of a
Hamiltonian path in graphs (see [9, 10, 13, 14, 15]),

there are only a few papers which treat directed paths in digraphs together
with forbidden structure conditions. One of its reasons is the number of
forbidden structures for the existence of directed paths having a good
property. Indeed, our main theorem (Theorem 1.1) essentially uses eight or ten
forbidden structures. Note that half of them derives from the assumptions in
Theorem A which treats a small path cover/partition problem in graphs. In
general, when we analyze a relationship between directed paths and forbidden
structures, it is necessary to previously clarify forbidden subgraph
conditions for a path of graphs in quite some detail. Thus, after getting the
results in [4], we estimate that it is a suitable time to start to analyze
forbidden structure conditions for the problem finding a small path
cover/partition of digraphs.

To state previous research and our main results, we prepare some (di)graphs
which will be used as forbidden sub(di)graphs (see Figure 1). Let $n$ be a
positive integers.

  1. $\bullet$

Let $K^{*}_{n}$ denote the graph with $V(K^{*}_{n})=\\{x_{i},y_{i}:1\leq i\leq
n\\}$ and $E(K^{*}_{n})=\\{x_{i}x_{j}:1\leq i<j\leq
n\\}\cup\\{x_{i}y_{i}:1\leq i\leq n\\}$.

  2. $\bullet$

Let $A:=\\{x_{1},x_{2}\\}\cup\\{y_{i},z_{i}:1\leq i\leq n\\}$.

    1. $\circ$

Let $F^{(1)}_{n}$ denote the graph on $A$ such that
$E(F^{(1)}_{n})=\\{x_{1}x_{2},x_{1}y_{1},x_{1}z_{1}\\}\cup\\{y_{i}y_{i+1},z_{i}z_{i+1}:1\leq
i\leq n-1\\}$.

    2. $\circ$

Let $F^{(2)}_{n}$ be the graph obtained from $F^{(1)}_{n}$ by adding the edge
$y_{1}z_{1}$.

    3. $\circ$

Let $F^{(3)}_{n}$ denote the graph on $A$ such that
$E(F^{(3)}_{n})=\\{x_{1}y_{1},x_{1}z_{1},x_{2}y_{1},x_{2}z_{1}\\}\cup\\{y_{i}y_{i+1},z_{i}z_{i+1}:1\leq
i\leq n-1\\}$.

    4. $\circ$

Let $F^{(4)}_{n}$ be the graph obtained from $F^{(3)}_{n}$ by adding the edge
$y_{1}z_{1}$.

    5. $\circ$

Let $D^{(1)}_{n}$ denote the digraph on $A\setminus\\{x_{2}\\}$ such that
$E(D^{(1)}_{n})=\\{(x_{1},y_{1}),(z_{1},x_{1}),(y_{1},z_{1})\\}\cup\\{(y_{i+1},y_{i}),(z_{i},z_{i+1}):1\leq
i\leq n-1\\}$.

    6. $\circ$

Let $D^{(2)}_{n}$ be the digraph obtained from $D^{(1)}_{n}$ by replacing the
arc $(z_{1},x_{1})$ by $(x_{1},z_{1})$.

    7. $\circ$

Let $D^{(3)}_{n}$ be the digraph obtained from $D^{(1)}_{n}$ by replacing the
arc $(x_{1},y_{1})$ by $(y_{1},x_{1})$.

$K^{*}_{n}:$$x_{1}$$x_{2}$$x_{n}$$y_{n}$$y_{2}$$y_{1}$$K_{n}$$y_{n}$$y_{1}$$x_{1}$$z_{1}$$z_{n}$$x_{2}$$y_{n}$$y_{1}$$z_{1}$$z_{n}$$x_{1}$$x_{2}$$y_{n}$$y_{1}$$z_{1}$$z_{n}$$x_{1}$$x_{2}$$F^{(1)}_{n}:$$F^{(4)}_{n}:$$F^{(3)}_{n}:$$y_{n}$$x_{1}$$z_{n}$$F^{(2)}_{n}:$$x_{2}$$z_{1}$$y_{1}$$D^{(1)}_{n}:$$x_{1}$$y_{n}$$y_{n-1}$$y_{1}$$z_{1}$$z_{n-1}$$z_{n}$$D^{(2)}_{n}:$$x_{1}$$y_{n}$$y_{n-1}$$y_{1}$$z_{1}$$z_{n-1}$$z_{n}$$F^{(2)}_{n}:$$D^{(3)}_{n}:$$x_{1}$$y_{n}$$y_{n-1}$$y_{1}$$z_{1}$$z_{n-1}$$z_{n}$
Figure 1: Graphs $K^{*}_{n}$ and $F^{(i)}_{n}~{}(1\leq i\leq 4)$, and digraphs
$D^{(i)}_{n}~{}(1\leq i\leq 3)$

For a fixed integer $n\geq 2$ and for a graph $G$, we consider two forbidden
subgraph conditions:

  1. (F1)

$G$ is $\\{K^{*}_{n},K_{1,n},F^{(1)}_{n},F^{(2)}_{n}\\}$-free; and

  2. (F’1)

$G$ is
$\\{K^{*}_{n},K_{1,n},F^{(1)}_{n},F^{(2)}_{n},F^{(3)}_{n},F^{(4)}_{n}\\}$-free.

In [4], the authors proved the following theorem (and, indeed, they also
showed the forbidden subgraph conditions are necessary in a sense.).

######  Theorem A (Chiba and Furuya [4])

For an integer $n\geq 2$, the following hold:

  1. (i)

There exists a constant $c_{0}=c_{0}(n)$ depending on $n$ only such that ${\rm
pc}(G)\leq c_{0}$ for every connected graph $G$ satisfying (F1).

  2. (ii)

There exists a constant $c^{\prime}_{0}=c^{\prime}_{0}(n)$ depending on $n$
only such that ${\rm pp}(G)\leq c^{\prime}_{0}$ for every connected graph $G$
satisfying (F’1).

In this paper our aim is to give an analogy of Theorem A for digraphs. To
state our main result, we define the following four conditions for a fixed
integer $n\geq 2$ and for a digraph $D$.

  1. (D1)

$G_{D}$ is $\\{K^{*}_{n},K_{1,n},F^{(1)}_{n},F^{(2)}_{n}\\}$-free, i.e.,
$G_{D}$ satisfies (F1);

  2. (D’1)

$G_{D}$ is
$\\{K^{*}_{n},K_{1,n},F^{(1)}_{n},F^{(2)}_{n},F^{(3)}_{n},F^{(4)}_{n}\\}$-free,
i.e., $G_{D}$ satisfies (F’1);

  3. (D2)

$D$ is $\\{D^{(1)}_{n},D^{(2)}_{n},D^{(3)}_{n}\\}$-free; and

  4. (D3)

$r(P)\leq n$ for every induced pseudo-path $P$ of $D$.

Our main theorem is the following.

###### Theorem 1.1

For an integer $n\geq 2$, the following hold:

  1. (i)

There exists a constant $c_{1}=c_{1}(n)$ depending on $n$ only such that ${\rm
pc}(D)\leq c_{1}$ for every weakly connected digraph $D$ satisfying (D1), (D2)
and (D3).

  2. (ii)

There exists a constant $c^{\prime}_{1}=c^{\prime}_{1}(n)$ depending on $n$
only such that ${\rm pp}(D)\leq c^{\prime}_{1}$ for every weakly connected
digraph $D$ satisfying (D’1), (D2) and (D3).

Strictly speaking, the condition (D3) is not a forbidden subdigraph condition.
However, when we consider conditions for bounding the path cover/partition
number of digraphs, we must forbid a pseudo-path $P$ with large $r(P)$ because
${\rm pc}(P)={\rm pp}(P)=r(P)+1$ for every pseudo-path $P$. Since no finite
forbidden subdigraph conditions can exclude all pseudo-paths $P$ with large
$r(P)$, the condition (D3) is reasonable in our main results.

The condition that “weakly connected digraph $D$ satisfying (D1) (or (D’1)),
(D2) and (D3)” is best possible in a sense because essentially weaker
conditions than the conditions (D1) (resp. (D’1)), (D2) and (D3) cannot assure
us the existence of a small path cover (resp. a small path partition) of
digraphs. (We omit its details, but the discussion in [4] will be a good
reference for the checking.)

We introduce some lemmas in Section 2, and prove Theorem 1.1 in Section 3. We
remark that the assumptions imposed on digraphs in Theorem 1.1 are closely
divided into two parts:

  1. $\bullet$

Fundamental assumptions for the underlying graph $G_{D}$ ((D1) and (D’1)),
which lead to the existence of small path cover/partitions of $G_{D}$, and

  2. $\bullet$

additional assumptions which are peculiar to digraphs ((D2) and (D3)).

However in general, when we compare Ramsey-type problems on graphs and
digraphs, the above situation does not always occur. To demonstrate it, in
Section 4, we give a similar theorem on the cycle cover/partition number of
digraphs and show that the assumptions for the underlying graph do not assure
us the existence of small cycle cover/partitions of graphs.

##  2 Lemmas

###  2.1 Global structures

In this subsection, we introduce some known lemmas.

As we mentioned in Subsection 1.1, we have ${\rm pc}(D)\leq{\rm pp}(D)$ for a
digraph $D$. This, together with a result by Gallai and Milgram [12], leads to
the following lemma.

###### Lemma 2.1

For a digraph $D$, ${\rm pc}(D)\leq{\rm pp}(D)\leq\alpha(G_{D})$.

Now we pick up two useful lemmas proved in [4]. In the remainder of this
subsection, we fix an integer $n\geq 3$ and a connected
$\\{K^{*}_{n},K_{1,n},F^{(1)}_{n},F^{(2)}_{n}\\}$-free graph $G$. Set
$n_{0}=\max\\{\lceil\frac{n^{2}-n-2}{2}\rceil,n\\}$. Take a longest induced
path $P$ of $G$, and write $P=u_{1}u_{2}\cdots u_{m}$. Let
$X_{0}=\\{u_{i}:1\leq i\leq n_{0}\mbox{ or }m-n_{0}+1\leq i\leq m\\}$ and
$Y=N_{G}(V(P)\setminus X_{0})\setminus(X_{0}\cup N_{G}(X_{0}))$. Note that if
$|V(P)|\leq 2n_{0}$, then $X_{0}=V(P)$ and $Y=\emptyset$. We further remark
that $N_{G}(y)\cap V(P)\subseteq\\{u_{i}:n_{0}+1\leq i\leq m-n_{0}\\}$ for
every $y\in Y$. Now we recursively define the sets $X_{i}~{}(i\geq 1)$ as
follows: Let $X_{1}=N_{G}(X_{0})\setminus V(P)$, and for $i$ with $i\geq 2$,
let $X_{i}=N_{G}(X_{i-1})\setminus(V(P)\cup Y\cup(\bigcup_{1\leq j\leq
i-2}X_{j}))$ (see Figure 2). Then $N_{G}(V(P))$ is the disjoint union of
$X_{1}$ and $Y$, and the following lemma holds.

$X_{0}$$P$$u_{1}$$u_{n_{0}}$$u_{m-n_{0}+1}$$u_{m}$$X_{2}$$X_{3}$$X_{1}$$Y$
Figure 2: Path $P$, and sets $X_{i}$ and $Y$

######  Lemma 2.2 (Chiba and Furuya [4, Lemma 2.6])

The set $V(G)$ is the disjoint union of $V(P)$, $Y$ and $X_{i}~{}(1\leq i\leq
2n_{0}-1)$. In particular, $X_{i}=\emptyset$ for all $i$ with $i\geq 2n_{0}$.

We recursively define the values $\alpha_{i}~{}(i\geq 0)$ as follows: Let
$\alpha_{0}=2\lceil\frac{n_{0}}{2}\rceil$, and for $i$ with $i\geq 1$, let
$\alpha_{i}=(n-1)R(n,\alpha_{i-1}+1)-1$. We remark that $\alpha_{i}$ depends
on $n$ and $i$. The following lemma holds.

######  Lemma 2.3 (Chiba and Furuya [4, Lemma 2.7])

For an integer $i$ with $i\geq 0$, $\alpha(G[X_{i}])\leq\alpha_{i}$.

###  2.2 An induced path and its neighbors

In this subsection, we fix an integer $n\geq 3$ and an
$\\{F^{(1)}_{n},F^{(2)}_{n}\\}$-free graph $G$. Take an induced path $Q$ of
$G$, and write $Q=v_{1}v_{2}\cdots v_{l}$. For a vertex $y\in N_{G}(V(Q))$,
let $i_{y}=\min\\{i:1\leq i\leq l,~{}yv_{i}\in E(G)\\}$ and
$j_{y}=\max\\{i:1\leq i\leq l,~{}yv_{i}\in E(G)\\}$. Since $N_{G}(y)\cap
V(Q)\neq\emptyset$, the indices $i_{y}$ and $j_{y}$ are well-defined.

###### Lemma 2.4

Let $y\in N_{G}(V(Q))$ be a vertex such that $N_{G}(y)\cap
V(Q)\subseteq\\{v_{i}:n+1\leq i\leq l-n\\}$. Then the following hold:

  1. (i)

We have $1\leq j_{y}-i_{y}\leq 3$.

  2. (ii)

If $G$ is $F^{(3)}_{n}$-free, then $N_{G}(y)\cap V(Q)=\\{v_{i}:i_{y}\leq i\leq
j_{y}\\}$.

###### Proof.

If $j_{y}-i_{y}\geq 3$ and $\\{yv_{i_{y}+1},yv_{j_{y}-1}\\}\not\subseteq
E(G)$, say $yv_{i_{y}+1}\notin E(G)$, then

$\\{v_{i_{y}-n},v_{i_{y}-n+1},\ldots,v_{i_{y}+1},y,v_{j_{y}},v_{j_{y}+1},\ldots,v_{j_{y}+n-2}\\}$

induces a copy of $F^{(1)}_{n}$ in $G$, which is a contradiction. Thus

if $j_{y}-i_{y}\geq 3$, then $yv_{i_{y}+1},yv_{j_{y}-1}\in E(G)$. (2.1)

  1. (i)

If $i_{y}=j_{y}$, then
$\\{v_{i_{y}-n},v_{i_{y}-n+1},\ldots,v_{i_{y}},y,v_{i_{y}+1},\ldots,v_{i_{y}+n}\\}$
induces a copy of $F^{(1)}_{n}$ in $G$, which is a contradiction. Thus
$j_{y}-i_{y}\geq 1$. Suppose that $j_{y}-i_{y}\geq 4$. Then by (2.1), we have
$v_{i_{y}+1}y\in E(G)$. If $yv_{i_{y}+2}\in E(G)$, then
$\\{v_{i_{y}-n+1},v_{i_{y}-n+2},\ldots,v_{i_{y}},y,v_{i_{y}+2},v_{j_{y}},v_{j_{y}+1},\ldots,v_{j_{y}+n-1}\\}$
induces a copy of $F^{(1)}_{n}$ in $G$; if $yv_{i_{y}+2}\notin E(G)$, then
$\\{v_{i_{y}-n+1},v_{i_{y}-n+2},\ldots,v_{i_{y}+2},y,v_{j_{y}},v_{j_{y}+1},\ldots,v_{j_{y}+n-2}\\}$
induces a copy of $F^{(2)}_{n}$ in $G$. In either case, we obtain a
contradiction. This implies that $j_{y}-i_{y}\leq 3$.

  2. (ii)

Suppose that $G$ is $F^{(3)}_{n}$-free and $N_{G}(y)\cap
V(Q)\neq\\{v_{i}:i_{y}\leq i\leq j_{y}\\}$. By the definitions of $i_{y}$ and
$j_{y}$, $N_{G}(y)\cap V(Q)\subseteq\\{v_{i}:i_{y}\leq i\leq j_{y}\\}$ and
$yv_{i_{y}},yv_{j_{y}}\in E(G)$. Thus there exists an index $i$ with
$i_{y}+1\leq i\leq j_{y}-1$ such that $yv_{i}\notin E(G)$. Considering (2.1)
and (i), this forces $j_{y}-i_{y}=2$ and $yv_{i_{y}+1}\notin E(G)$. Then
$\\{v_{i_{y}-n+1},v_{i_{y}-n+2},\ldots,v_{i_{y}},y,v_{i_{y}+1},v_{i_{y}+2},\ldots,v_{i_{y}+n+1}\\}$
induces a copy of $F^{(3)}_{n}$ in $G$, which is a contradiction. ∎

###### Lemma 2.5

Let $y,y^{\prime}\in N_{G}(V(Q))$ be vertices with $y\neq y^{\prime}$ and
$(N_{G}(y)\cup N_{G}(y^{\prime}))\cap V(Q)\subseteq\\{v_{i}:n+1\leq i\leq
l-n\\}$. Then the following hold:

  1. (i)

If $i_{y^{\prime}}\geq i_{y}+n+3$, then $yy^{\prime}\notin E(G)$.

  2. (ii)

If $G$ is $\\{F^{(3)}_{n},F^{(4)}_{n}\\}$-free and $i_{y}=i_{y^{\prime}}$,
then $yy^{\prime}\in E(G)$.

###### Proof.

  1. (i)

Suppose that $i_{y^{\prime}}\geq i_{y}+n+3$ and $yy^{\prime}\in E(G)$. By
Lemma 2.4(i), $j_{y}\leq i_{y}+3\leq(i_{y^{\prime}}-n-3)+3=i_{y^{\prime}}-n$,
and hence

$\displaystyle N_{G}(y)\cap\\{v_{i}:i_{y^{\prime}}-n+1\leq i\leq
l\\}=\emptyset.$ (2.2)

Again by Lemma 2.4(i), we have $1\leq j_{y^{\prime}}-i_{y^{\prime}}\leq 3$.
Considering (2.2), if $j_{y^{\prime}}-i_{y^{\prime}}=1$, then

$\\{v_{i_{y^{\prime}}-n+1},v_{i_{y^{\prime}}-n+2},\ldots,v_{i_{y^{\prime}}},y^{\prime},y,v_{i_{y^{\prime}}+1},v_{i_{y^{\prime}}+2},\ldots,v_{i_{y^{\prime}}+n}\\}$

induces a copy of $F^{(2)}_{n}$ in $G$; if $2\leq
j_{y^{\prime}}-i_{y^{\prime}}\leq 3$, then

$\\{v_{i_{y^{\prime}}-n+1},v_{i_{y^{\prime}}-n+2},\ldots,v_{i_{y^{\prime}}},y^{\prime},y,v_{j_{y^{\prime}}},v_{j_{y^{\prime}}+1},\ldots,v_{j_{y^{\prime}}+n-1}\\}$

induces a copy of $F^{(1)}_{n}$ in $G$. In either case, we obtain a
contradiction.

  2. (ii)

Suppose that $G$ is $\\{F^{(3)}_{n},F^{(4)}_{n}\\}$-free,
$i_{y}=i_{y^{\prime}}$ and $yy^{\prime}\notin E(G)$. Without loss of
generality, we may assume that $j_{y}\geq j_{y^{\prime}}$. It follows from
Lemma 2.4, we have $yv_{i_{y}+1},y^{\prime}v_{i_{y}+1}\in E(G)$. If
$j_{y}=j_{y^{\prime}}=i_{y}+1$, then

$\\{v_{i_{y}-n+1},v_{i_{y}-n+2},\ldots,v_{i_{y}},y,y^{\prime},v_{i_{y}+1},v_{i_{y}+2},\ldots,v_{i_{y}+n}\\}$

induces a copy of $F^{(4)}_{n}$ in $G$; if $j_{y}=j_{y^{\prime}}\geq i_{y}+2$,
then

$\\{v_{i_{y}-n+1},v_{i_{y}-n+2},\ldots,v_{i_{y}},y,y^{\prime},v_{j_{y}},v_{j_{y}+1},\ldots,v_{j_{y}+n-1}\\}$

induces a copy of $F^{(3)}_{n}$ in $G$; if $j_{y}>j_{y^{\prime}}$, then

$\\{v_{i_{y}-n},v_{i_{y}-n+1},\ldots,v_{i_{y}},y^{\prime},y,v_{j_{y}},v_{j_{y}+1},\ldots,v_{j_{y}+n-2}\\}$

induces a copy of $F^{(1)}_{n}$ in $G$. In any case, we obtain a
contradiction. ∎

###  2.3 An induced directed path and its neighbors

In this subsection, we prove the following lemma which plays a key role in the
proof of Theorem 1.1.

###### Lemma 2.6

Let $n\geq 3$ be an integer, and let $D$ be a digraph satisfying (D1), (D2)
and (D3). Let $Q$ be an induced directed path in $D$, and write
$Q=v_{1}v_{2}\cdots v_{l}$. Let $Y^{\prime}$ be a subset of $N_{G_{D}}(V(Q))$
such that $N_{G_{D}}(y)\cap V(Q)\subseteq\\{v_{i}:n+1\leq i\leq l-n\\}$ for
every $y\in Y^{\prime}$. Then the following hold:

  1. (i)

We have ${\rm pc}(D[V(Q)\cup Y^{\prime}])\leq\frac{(n-2)n(n+5)}{2}+6(n-2)$.

  2. (ii)

If $D$ satisfies (D’1), then ${\rm pp}(D[V(Q)\cup
Y^{\prime}])\leq\frac{n(n+5)}{2}+1$ and ${\rm
pp}(D[(V(Q)\setminus\\{v_{t}\\})\cup Y^{\prime}])\leq\frac{n(n+5)}{2}+1$ for
each $t\in\\{1,l\\}$.

###### Proof.

Since $Q=v_{1}v_{2}\cdots v_{l}$ is a directed path, $(v_{i},v_{i+1})\in E(D)$
for every $i$ with $1\leq i\leq l-1$. If $Y^{\prime}=\emptyset$, then

  1. $\bullet$

$\\{Q\\}$ is a path partition of $D[V(Q)\cup Y^{\prime}]$ and

  2. $\bullet$

$\\{Q-\\{v_{t}\\}\\}$ is a path partition of $D[(V(Q)\setminus\\{v_{t}\\})\cup
Y^{\prime}]$ for each $t\in\\{1,l\\}$,

as desired. Thus we may assume that $Y^{\prime}\neq\emptyset$.

For each $y\in Y^{\prime}$, let $i_{y}=\min\\{i:n+1\leq i\leq l-n,~{}yv_{i}\in
E(G_{D})\\}$ and $j_{y}=\max\\{i:n+1\leq i\leq l-n,~{}yv_{i}\in E(G_{D})\\}$.
Since $N_{G_{D}}(y)\cap\\{v_{i}:n+1\leq i\leq l-n\\}\neq\emptyset$, the
indices $i_{y}$ and $j_{y}$ are well-defined. Since $G_{D}$ is
$\\{F^{(1)}_{n},F^{(2)}_{n}\\}$-free, it follows from Lemma 2.4(i) that $1\leq
j_{y}-i_{y}\leq 3$. Furthermore, if $D$ satisfies (D’1), then by Lemma
2.4(ii), we have $N_{G_{D}}(y)\cap V(Q)=\\{v_{i}:i_{y}\leq i\leq j_{y}\\}$.

We call a subset $B$ of $Y^{\prime}$ bad if either

  1. $\bullet$

$B=\\{y\\}$ for some $y\in Y^{\prime}$, and
$E(D)\cap\\{(y,v_{i_{y}}),(v_{j_{y}},y)\\}\neq\emptyset$; or

  2. $\bullet$

$B=\\{y,y^{\prime}\\}$ for some $y,y^{\prime}\in Y^{\prime}$ with $y\neq
y^{\prime}$, and the following conditions hold: $yy^{\prime}\notin E(G_{D})$,
$j_{y}-i_{y}=j_{y^{\prime}}-i_{y^{\prime}}=3$, $i_{y^{\prime}}=i_{y}+2$, and
$\\{(v_{i_{y}},y),(y,v_{i_{y}+3}),(y^{\prime},v_{i_{y}+3}),(y^{\prime},v_{i_{y}+5})\\}\subseteq
E(D)$

(see Figure 3). If $\\{y\\}$ is a bad set and $j_{y}-i_{y}=1$, then

$\\{v_{i_{y}-n+1},v_{i_{y}-n+2},\ldots,v_{i_{y}},y,v_{i_{y}+1},v_{i_{y}+2},\ldots,v_{i_{y}+n}\\}$

induces a copy of one of $D^{(1)}_{n}$, $D^{(2)}_{n}$ and $D^{(3)}_{n}$ in
$D$, which contradicts the assumption that $D$ satisfies (D2). Thus if
$\\{y\\}$ is a bad set, then $2\leq j_{y}-i_{y}\leq 3$.

$y$$y$$y$$v_{i_{y}}$$v_{j_{y}}$$v_{i_{y}}$$v_{j_{y}}$$v_{i_{y}}$$v_{j_{y}}$$y$$y^{\prime}$$v_{i_{y}}$$v_{i_{y}+3}$$v_{i_{y}+5}$
Figure 3: Bad sets and a related induced pseudo-path in the proof of Claim 2.1

Let $i_{B}=\min\\{i_{y}:y\in B\\}$ for each bad set $B$, and let
$I=\\{i_{B}:B\mbox{ is a bad set}\\}$.

###### Claim 2.1

We have $|I|\leq\frac{n(n+5)}{2}$.

###### Proof.

We may assume that $I\neq\emptyset$. Now we consider an operation recursively
defining the indices $h_{1},h_{2},\ldots$ with $h_{1}<h_{2}<\cdots$ as
follows: Let $h_{1}=\min\\{i:i\in I\\}$. For $p\geq 2$, we assume that the
index $h_{p-1}$ has been defined. If there exists an index $i\in I$ with
$i\geq h_{p-1}+n+5$, we let $h_{p}=\min\\{i\in I:i\geq h_{p-1}+n+5\\}$;
otherwise, we finish the operation.

Let $I^{\prime}=\\{h_{p}:p\geq 1\\}$, and set $p_{0}=|I^{\prime}|$. For each
$p$ with $1\leq p\leq p_{0}$, we take a bad set $B_{p}$ with
$i_{B_{p}}=h_{p}$, and let $j_{p}=\max\\{j_{y}:y\in B_{p}\\}$. Then for $y\in
B_{p}$,

$\displaystyle\begin{cases}i_{y}=i_{B_{p}}&(|B_{p}|=1)\\\
i_{y}\in\\{i_{B_{p}},i_{B_{p}}+2\\}&(|B_{p}|=2),\end{cases}$ (2.3)

and

$\displaystyle\begin{cases}j_{p}\leq h_{p}+3&(|B_{p}|=1)\\\
j_{p}=h_{p}+5&(|B_{p}|=2).\end{cases}$ (2.4)

Fix two indices $p$ and $p^{\prime}$ with $1\leq p<p^{\prime}\leq p_{0}$, and
let $y\in B_{p}$ and $y^{\prime}\in B_{p^{\prime}}$. Then by (2.3), we have

$i_{y}+n+3\leq(i_{B_{p}}+2)+n+3=h_{p}+n+5\leq
h_{p^{\prime}}=i_{B_{p^{\prime}}}\leq i_{y^{\prime}}.$

This together with Lemma 2.5(i) implies that $yy^{\prime}\notin E(G_{D})$.
Consequently,

there is no edge of $G_{D}$ between $B_{p}$ and $B_{p^{\prime}}$ for $1\leq
p<p^{\prime}\leq p_{0}$. (2.5)

Suppose that $p_{0}\geq\frac{n+1}{2}$. For each $p$ with $1\leq p\leq p_{0}$,
we define a pseudo-path $R_{p}$ in $D$ as follows: If $|B_{p}|=1$, say
$B_{p}=\\{y\\}$, let $R_{p}=v_{i_{y}-1}v_{i_{y}}yv_{j_{y}}v_{j_{y}+1}$; if
$|B_{p}|=2$, say $B_{p}=\\{y,y^{\prime}\\}$ with $i_{y^{\prime}}=i_{y}+2$, let
$R_{p}=v_{i_{y}-1}v_{i_{y}}yv_{i_{y}+3}y^{\prime}v_{i_{y}+5}v_{i_{y}+6}$ (see
Figure 3 again). Then $R_{p}$ is an induced pseudo-path in $D$ and
$r(R_{p})=2$. Let $R$ be the subdigraph of $D$ induced by

$(V(Q)\setminus\\{v_{i}:1\leq p\leq p_{0},~{}h_{p}-1\leq i\leq
j_{p}+1\\})\cup\left(\bigcup_{1\leq p\leq p_{0}}V(R_{p})\right).$

By (2.5) and the definition of a bad set, $\bigcup_{1\leq p\leq p_{0}}B_{p}$
is an independent set of $G_{D}$. For $p$ and $p^{\prime}$ with $1\leq
p<p^{\prime}\leq p_{0}$, it follows from (2.4) that $j_{p}+1\leq
h_{p}+6\leq(h_{p^{\prime}}-n-5)+6=h_{p^{\prime}}-n+1\leq h_{p^{\prime}}-2$,
and hence $V(R_{p})\cap V(R_{p^{\prime}})=\emptyset$. Therefore, $R$ is an
induced pseudo-path in $D$ and $r(R)=\sum_{1\leq p\leq
p_{0}}r(R_{p})=2p_{0}\geq n+1$, which contradicts the assumption that $D$
satisfies (D3). Thus $p_{0}\leq\frac{n}{2}$.

Suppose that $I\setminus\\{i:1\leq p\leq p_{0},~{}h_{p}\leq i\leq
h_{p}+n+4\\}\neq\emptyset$, and take its minimum element $h$. Since $h\neq
h_{1}~{}(=\min\\{i:i\in I\\})$ and $h\in I$, we have $h_{1}<h$. In particular,
the value $p^{*}=\max\\{p:1\leq p\leq p_{0},~{}h_{p}<h\\}$ is well-defined.
Then by the definition of $h$,

$\displaystyle h\neq h_{p^{*}+1}$ (2.6)

and $h\notin\\{i:h_{p^{*}}\leq i\leq h_{p^{*}}+n+4\\}$, and so

$\displaystyle h\geq h_{p^{*}}+n+5.$ (2.7)

By the maximality of $p^{*}$,

no index $i$ with $h_{p^{*}}+1\leq i\leq h-1$ equals to $h_{p^{*}+1}$. (2.8)

Considering the definition of the indices $h_{p}~{}(1\leq p\leq p_{0})$, it
follows from (2.7), (2.8) and the minimality of $h$ that $h_{p^{*}+1}=h$,
which contradicts (2.6). Thus $I\subseteq\\{i:1\leq p\leq p_{0},~{}h_{p}\leq
i\leq h_{p}+n+4\\}$, and so $|I|\leq p_{0}(n+5)\leq\frac{n(n+5)}{2}$. ∎

For each $i$ with $n+1\leq i\leq l-n-1$, let $Y^{\prime}_{i}=\\{y\in
Y^{\prime}:i_{y}=i\\}$. Recall that

$\displaystyle 1\leq j_{y}-i_{y}\leq 3~{}~{}\mbox{and}~{}~{}n+1\leq
i_{y}<j_{y}\leq l-n~{}~{}~{}\mbox{for every }y\in Y^{\prime}.$ (2.9)

By (2.9), $\\{y\in Y^{\prime}:i_{y}\leq n\mbox{ and }i_{y}\geq
l-n\\}=\emptyset$, and hence $Y^{\prime}$ is the disjoint union of
$Y^{\prime}_{i}~{}(n+1\leq i\leq l-n-1)$. Note that $Y^{\prime}_{i}\subseteq
N_{G_{D}}(v_{i})$ and $Y^{\prime}_{i}\cap N_{G_{D}}(v_{i-1})=\emptyset$. Hence
if $\alpha(G_{D}[Y^{\prime}_{i}])\geq n-1$, then
$G_{D}[\\{v_{i-1},v_{i}\\}\cup Y^{\prime}_{i}]$ contains a copy of $K_{1,n}$
as an induced subgraph, which contradicts the $K_{1,n}$-freeness of $G_{D}$.
Thus

$\displaystyle\alpha(G_{D}[Y^{\prime}_{i}])\leq n-2\mbox{ for every }i\mbox{
with }n+1\leq i\leq l-n-1.$ (2.10)

Furthermore, it follows from Lemma 2.5(ii) that

if $D$ satisfies (D’1), then $Y^{\prime}_{i}$ is a clique of $G_{D}$ for every
$i$ with $n+1\leq i\leq l-n-1$. (2.11)

Let $\tilde{Y}=\bigcup_{i\in I}Y^{\prime}_{i}$. By the definition of $I$,
$\tilde{Y}\cap B\neq\emptyset$ for every bad set $B$, and so

$\displaystyle B\not\subseteq Y^{\prime}\setminus\tilde{Y}\mbox{ for every bad
set }B.$ (2.12)

Now we prove that ${\rm pc}(D[V(Q)\cup
Y^{\prime}])\leq\frac{(n-2)n(n+5)}{2}+6(n-2)$, which proves (i). By Lemma 2.1,
Claim 2.1 and (2.10), we have ${\rm
pc}(D[\tilde{Y}])\leq\alpha(G_{D}[\tilde{Y}])\leq\sum_{i\in
I}\alpha(G_{D}[Y^{\prime}_{i}])\leq\frac{(n-2)n(n+5)}{2}$. Thus, to complete
the proof of (i), it suffices to show that ${\rm
pc}(D[V(Q)\cup(Y^{\prime}\setminus\tilde{Y})])\leq 6(n-2)$. For two integers
$i$ and $k$ with $n+1\leq i\leq l-n-k$ and $k\in\\{1,2,3\\}$, we define a set
$Y^{\prime}_{i,k}$ as follows: If $i\notin I$, let $Y^{\prime}_{i,k}=\\{y\in
Y^{\prime}_{i}:j_{y}=i_{y}+k\\}$; if $i\in I$, let
$Y^{\prime}_{i,k}=\emptyset$. Then by (2.9), $Y^{\prime}\setminus\tilde{Y}$ is
the disjoint union of $Y^{\prime}_{i,k}~{}(n+1\leq i\leq
l-n-k,~{}k\in\\{1,2,3\\})$. By Lemma 2.1 and (2.10), there exists a path cover
${\mathcal{Q}}_{i,k}=\\{Q^{(1)}_{i,k},Q^{(2)}_{i,k},\ldots,Q^{(s_{i,k})}_{i,k}\\}$
of $D[Y^{\prime}_{i,k}]$ with $s_{i,k}\leq n-2$, where
${\mathcal{Q}}_{i,k}=\emptyset$ and $s_{i,k}=0$ if
$Y^{\prime}_{i,k}=\emptyset$. Let $p^{(s)}_{i,k}$ and $q^{(s)}_{i,k}$ be the
internal vertex and terminal vertex of $Q^{(s)}_{i,k}$, respectively. If
$Y^{\prime}_{i,k}\neq\emptyset$, then for every $y\in Y^{\prime}_{i,k}$,
$\\{y\\}$ is not a bad set, and so $(v_{i},y),(y,v_{i+k})\in E(D)$. Hence for
each integer $s$ with $1\leq s\leq n-2$, we can define a directed path
$R^{(s)}_{i,k}$ as follows: If $s\leq s_{i,k}$, let
$R^{(s)}_{i,k}=v_{i}p^{(s)}_{i,k}Q^{(s)}_{i,k}q^{(s)}_{i,k}v_{i+k}$;
otherwise, let $R^{(s)}_{i,k}=v_{i}v_{i+1}\cdots v_{i+k}$. For
$r\in\\{0,1\\}$, we define the value $\xi_{r}$ as

$\xi_{r}=\begin{cases}l-n-r&(l\mbox{ is odd})\\\ l-n-1+r&(l\mbox{ is
even}).\end{cases}$

We define the values $\xi^{\prime}_{0}$, $\xi^{\prime}_{1}$ and
$\xi^{\prime}_{2}$ as

$\xi^{\prime}_{0}=\begin{cases}l-n-2&(l-2n\equiv 0~{}(\mbox{mod }3))\\\
l-n&(l-2n\equiv 1~{}(\mbox{mod }3))\\\ l-n-1&(l-2n\equiv 2~{}(\mbox{mod
}3)),\end{cases}$ $\xi^{\prime}_{1}=\begin{cases}l-n-1&(l-2n\equiv
0~{}(\mbox{mod }3))\\\ l-n-2&(l-2n\equiv 1~{}(\mbox{mod }3))\\\
l-n&(l-2n\equiv 2~{}(\mbox{mod }3)),\end{cases}~{}~{}~{}$

and

$\xi^{\prime}_{2}=\begin{cases}l-n&(l-2n\equiv 0~{}(\mbox{mod }3))\\\
l-n-1&(l-2n\equiv 1~{}(\mbox{mod }3))\\\ l-n-2&(l-2n\equiv 2~{}(\mbox{mod
}3)).\end{cases}~{}~{}~{}$

Let

$\displaystyle R^{(s)}_{1}$ $\displaystyle=v_{1}v_{2}\cdots
v_{n+1}R^{(s)}_{n+1,1}v_{n+2}R^{(s)}_{n+2,1}v_{n+3}\cdots
v_{l-n-1}R^{(s)}_{l-n-1,1}v_{l-n}v_{l-n+1}\cdots v_{l},$ $\displaystyle
R^{(s)}_{2}$ $\displaystyle=v_{1}v_{2}\cdots
v_{n+1}R^{(s)}_{n+1,2}v_{n+3}R^{(s)}_{n+3,2}v_{n+5}\cdots
v_{\xi_{0}-2}R^{(s)}_{\xi_{0}-2,2}v_{\xi_{0}}v_{\xi_{0}+1}\cdots v_{l},$
$\displaystyle R^{(s)}_{3}$ $\displaystyle=v_{1}v_{2}\cdots
v_{n+2}R^{(s)}_{n+2,2}v_{n+4}R^{(s)}_{n+4,2}v_{n+6}\cdots
v_{\xi_{1}-2}R^{(s)}_{\xi_{1}-2,2}v_{\xi_{1}}v_{\xi_{1}+1}\cdots v_{l},$
$\displaystyle R^{(s)}_{4}$ $\displaystyle=v_{1}v_{2}\cdots
v_{n+1}R^{(s)}_{n+1,3}v_{n+4}R^{(s)}_{n+4,3}v_{n+7}\cdots
v_{\xi^{\prime}_{0}-3}R^{(s)}_{\xi^{\prime}_{0}-3,3}v_{\xi^{\prime}_{0}}v_{\xi^{\prime}_{0}+1}\cdots
v_{l},$ $\displaystyle R^{(s)}_{5}$ $\displaystyle=v_{1}v_{2}\cdots
v_{n+2}R^{(s)}_{n+2,3}v_{n+5}R^{(s)}_{n+5,3}v_{n+8}\cdots
v_{\xi^{\prime}_{1}-3}R^{(s)}_{\xi^{\prime}_{1}-3,3}v_{\xi^{\prime}_{1}}v_{\xi^{\prime}_{1}+1}\cdots
v_{l},\mbox{ and}$ $\displaystyle R^{(s)}_{6}$ $\displaystyle=v_{1}v_{2}\cdots
v_{n+3}R^{(s)}_{n+3,3}v_{n+6}R^{(s)}_{n+6,3}v_{n+9}\cdots
v_{\xi^{\prime}_{2}-3}R^{(s)}_{\xi^{\prime}_{2}-3,3}v_{\xi^{\prime}_{2}}v_{\xi^{\prime}_{2}+1}\cdots
v_{l}$

(see Figure 4). Then we easily verify that $\\{R^{(s)}_{a}:1\leq a\leq
6,~{}1\leq s\leq n-2\\}$ is a path cover of
$D[V(Q)\cup(Y^{\prime}\setminus\tilde{Y})]$ having cardinality at most
$6(n-2)$. Consequently, ${\rm
pc}(D[V(Q)\cup(Y^{\prime}\setminus\tilde{Y})])\leq 6(n-2)$, which proves (i).

$v_{n+1}$$v_{n+2}$$v_{n+4}$$v_{n+3}$$v_{n}$$v_{n+5}$$v_{n+1}$$v_{n+2}$$v_{n+4}$$v_{n+3}$$v_{n}$$v_{n+5}$$v_{n+1}$$v_{n+2}$$v_{n+4}$$v_{n+3}$$v_{n}$$v_{n+5}$$R^{(s)}_{1}$$R^{(s)}_{2}$$R^{(s)}_{3}$$v_{n+1}$$v_{n+2}$$v_{n+4}$$v_{n+3}$$v_{n}$$v_{n+5}$$R^{(s)}_{4}$$v_{n+1}$$v_{n+2}$$v_{n+4}$$v_{n+3}$$v_{n}$$v_{n+5}$$R^{(s)}_{5}$$v_{n+1}$$v_{n+2}$$v_{n+4}$$v_{n+3}$$v_{n}$$v_{n+5}$$R^{(s)}_{6}$$s>s_{n+5,k}$
Figure 4: The directed paths $R^{(s)}_{a}$

Next we assume that $D$ satisfies (D’1), and prove that (ii) holds. By Lemma
2.1, Claim 2.1 and (2.11), we have ${\rm
pp}(D[\tilde{Y}])\leq\alpha(G_{D}[\tilde{Y}])\leq\sum_{i\in
I}\alpha(G_{D}[Y^{\prime}_{i}])\leq|I|\leq\frac{n(n+5)}{2}$. Thus, to complete
the proof of (ii), it suffices to show that

$\displaystyle{\rm pp}(D[V(Q)\cup(Y^{\prime}\setminus\tilde{Y})])=1$ (2.13)

and

$\displaystyle{\rm
pp}(D[(V(Q)\setminus\\{v_{t}\\})\cup(Y^{\prime}\setminus\tilde{Y})])=1\mbox{
for each }t\in\\{1,l\\}.$ (2.14)

Now we fix a vertex $y\in Y^{\prime}\setminus\tilde{Y}$. Recall that $1\leq
j_{y}-i_{y}\leq 3$ and $N_{G_{D}}(y)\cap V(Q)=\\{v_{i}:i_{y}\leq i\leq
j_{y}\\}$. Since $\\{y\\}$ is not a bad set, $(v_{i_{y}},y),(y,v_{j_{y}})\in
E(D)$. In particular, the index

$\beta_{y}=\min\\{i:i_{y}\leq i\leq j_{y}-1,~{}(v_{i},y),(y,v_{i+1})\in
E(D)\\}$

is well-defined. Furthermore, each vertex $y$ in
$Y^{\prime}\setminus\tilde{Y}$ is divided into the following seven types (see
Figure 5):
Type 1 $j_{y}=i_{y}+1$.
Type 2 $j_{y}=i_{y}+2$ and $(y,v_{i_{y}+1})\in E(D)$.
Type 3 $j_{y}=i_{y}+2$ and $(v_{i_{y}+1},y)\in E(D)$.
Type 4 $j_{y}=i_{y}+3$ and $(y,v_{i_{y}+1}),(y,v_{i_{y}+2})\in E(D)$.
Type 5 $j_{y}=i_{y}+3$ and $(v_{i_{y}+1},y),(y,v_{i_{y}+2})\in E(D)$.
Type 6 $j_{y}=i_{y}+3$ and $(v_{i_{y}+1},y),(v_{i_{y}+2},y)\in E(D)$.
Type 7 $j_{y}=i_{y}+3$ and $(y,v_{i_{y}+1}),(v_{i_{y}+2},y)\in E(D)$.
Note that $\beta_{y}=i_{y}$ if the type of $y$ is 1, 2, 4 or 7;
$\beta_{y}=i_{y}+1$ if the type of $y$ is 3 or 5; $\beta_{y}=i_{y}+2$ if the
type of $y$ is 6. For $i$ with $n+1\leq i\leq l-n-1$, let $W_{i}=\\{y\in
Y^{\prime}\setminus\tilde{Y}:\beta_{y}=i\\}$. Then
$Y^{\prime}\setminus\tilde{Y}$ is the disjoint union of $W_{i}~{}(n+1\leq
i\leq l-n-1)$.

$y$$y$$y$$y$$y$$y$$y$$v_{i_{y}}$$v_{i_{y}}$$v_{i_{y}}$$v_{i_{y}}$$v_{i_{y}}$$v_{i_{y}}$$v_{i_{y}}$$v_{j_{y}}$$v_{j_{y}}$$v_{j_{y}}$$v_{j_{y}}$$v_{j_{y}}$$v_{j_{y}}$$v_{j_{y}}$Type
1Type 2Type 3Type 4Type 5Type 6Type 7 Figure 5: Seven types of $y\in
Y^{\prime}\setminus\tilde{Y}$ where the vertex $v_{\beta_{y}}$ is circled.

###### Claim 2.2

For $i$ with $n+1\leq i\leq l-n-1$, $W_{i}$ is a clique of $G_{D}$.

###### Proof.

By way of contradiction, suppose that $W_{i}$ is not a clique of $G_{D}$. Then
there exist two vertices $y$ and $y^{\prime}$ in $W_{i}$ with
$yy^{\prime}\notin E(G_{D})$ whose types are $t_{y}$ and $t_{y^{\prime}}$,
respectively. We may assume that $t_{y}\leq t_{y^{\prime}}$. By Lemma 2.5(ii),
$i_{y}\neq i_{y^{\prime}}$. This implies that $t_{y}\neq t_{y^{\prime}}$ and

$(t_{y},t_{y^{\prime}})\notin\\{(1,2),(1,4),(1,7),(2,4),(2,7),(4,7),(3,5)\\}.$

Thus there are $\binom{7}{2}-7=14$ estimated cases on the pair
$(t_{y},t_{y^{\prime}})$. We divide the proof into five cases.

Case 1: $(t_{y},t_{y^{\prime}})\in\\{(1,3),(1,6),(2,5),(3,6)\\}$.

Note that $i_{y}>i_{y^{\prime}}$ and $j_{y}=j_{y^{\prime}}$. Hence

$\\{v_{i_{y^{\prime}}-n+2},v_{i_{y^{\prime}}-n+3},\ldots,v_{i_{y^{\prime}}},y^{\prime},v_{j_{y}},y,v_{j_{y}+1},\ldots,v_{j_{y}+n}\\}$

induces a copy of $F^{(1)}_{n}$ in $G_{D}$, which is a contradiction.

Case 2: $(t_{y},t_{y^{\prime}})=(1,5)$.

The set

$\\{v_{i_{y^{\prime}}-n+1},v_{i_{y^{\prime}}-n+2},\ldots,v_{i_{y^{\prime}}+1},y,y^{\prime},v_{j_{y^{\prime}}},v_{j_{y^{\prime}}+1},\ldots,v_{j_{y^{\prime}}+n-2}\\}$

induces a copy of $F^{(2)}_{n}$ in $G_{D}$, which is a contradiction.

Case 3: $(t_{y},t_{y^{\prime}})\in\\{(2,3),(2,6),(4,5),(5,6)\\}$.

Note that $i_{y}>i_{y^{\prime}}$, $j_{y^{\prime}}-i_{y^{\prime}}\geq 2$,
$j_{y^{\prime}}=j_{y}-1$ and $(y,v_{j_{y}-1})\in E(D)$. Hence

$\\{v_{i_{y^{\prime}}-n+3},v_{i_{y^{\prime}}-n+4},\ldots,v_{i_{y^{\prime}}},y^{\prime},v_{j_{y}-1},y,v_{j_{y}},v_{j_{y}+1},\ldots,v_{j_{y}+n-1}\\}$

induces a copy of $D^{(2)}_{n}$ in $D$, which is a contradiction.

Case 4: $(t_{y},t_{y^{\prime}})\in\\{(3,4),(3,7),(5,7)\\}$.

Note that $i_{y}=i_{y^{\prime}}-1$, $(v_{i_{y}+1},y)\in E(D)$ and
$j_{y^{\prime}}-i_{y^{\prime}}=3$ (and so $j_{y}<j_{y^{\prime}}$). Hence

$\\{v_{i_{y}-n+1},v_{i_{y}-n+2},\ldots,v_{i_{y}},y,v_{i_{y}+1},y^{\prime},v_{j_{y^{\prime}}},v_{j_{y^{\prime}}+1},\ldots,v_{j_{y^{\prime}}+n-3}\\}$

induces a copy of $D^{(3)}_{n}$ in $D$, which is a contradiction.

Case 5: $(t_{y},t_{y^{\prime}})\in\\{(4,6),(6,7)\\}$.

It follows that $\\{y,y^{\prime}\\}$ is a bad set and
$\\{y,y^{\prime}\\}\subseteq W_{i}\subseteq Y^{\prime}\setminus\tilde{Y}$,
which contradicts (2.12).

This completes the proof of Claim 2.2. ∎

Fix an index $i$ with $n+1\leq i\leq l-n-1$, and we define the directed path
$R_{i}$ from $v_{i}$ to $v_{i+1}$ with $V(R_{i})=\\{v_{i},v_{i+1}\\}\cup
W_{i}$ as follows: If $W_{i}=\emptyset$, let $R_{i}$ be the directed path
$v_{i}v_{i+1}$. We assume that $W_{i}\neq\emptyset$. By Lemma 2.1 and Claim
2.2, $D$ contains a directed path $R^{\prime}_{i}$ with
$V(R^{\prime}_{i})=W_{i}$. Let $R_{i}=v_{i}p_{i}R^{\prime}_{i}q_{i}v_{i+1}$
where $p_{i}$ and $q_{i}$ are is the internal vertex and terminal vertex of
$R^{\prime}_{i}$, respectively. Since $(v_{i},y),(y,v_{i+1})\in E(D)$ for
every $y\in W_{i}$, $R_{i}$ is a directed path in $D$. Hence

$R^{*}=v_{1}v_{2}\cdots v_{n+1}R_{n+1}v_{n+2}R_{n+2}v_{n+3}\cdots
v_{l-n-1}R_{l-n-1}v_{l-n}v_{l-n+1}\cdots v_{l}$

is a directed path in $D$ with $V(R^{*})=V(Q)\cup(\bigcup_{n+1\leq i\leq
l-n-1}V(R_{i}))~{}(=V(Q)\cup(Y^{\prime}\setminus\tilde{Y}))$. Furthermore,
$R^{*}-v_{1}$ and $R^{*}-v_{l}$ are also directed paths in $D$. Consequently,
(2.13) and (2.14) hold.

This completes the proof of Lemma 2.6. ∎

##  3 Proof of Theorem 1.1

Let $n\geq 2$ be an integer, and let $D$ be a weakly connected digraph
satisfying (D1), (D2) and (D3). We first suppose that $n=2$. Since $G_{D}$ is
$K_{1,2}$-free, $G_{D}$ is a complete graph, i.e., $\alpha(G_{D})=1$. Then by
Lemma 2.1, ${\rm pc}(D)={\rm pp}(D)=1$, as desired. Thus we may assume that
$n\geq 3$.

Set $n_{0}=\max\\{\lceil\frac{n^{2}-n-2}{2}\rceil,n\\}$. Take a longest
induced path $P$ of $G_{D}$, and write $P=u_{1}u_{2}\cdots u_{m}$. Let
$X_{i}~{}(i\geq 0)$ and $Y$ be the sets defined as in Subsection 2.1. Then by
Lemma 2.2, $V(D)$ is the disjoint union of $V(P)$, $Y$ and $X_{i}~{}(1\leq
i\leq 2n_{0}-1)$. By Lemmas 2.1 and 2.3,

$\displaystyle{\rm pc}(D-(V(P)\cup Y))\leq{\rm pp}(D-(V(P)\cup Y))$
$\displaystyle\leq\sum_{1\leq i\leq 2n_{0}-1}{\rm pp}(D[X_{i}])$
$\displaystyle\leq\sum_{1\leq i\leq 2n_{0}-1}\alpha(G_{D}[X_{i}])$
$\displaystyle\leq\sum_{1\leq i\leq 2n_{0}-1}\alpha_{i}$

where $\alpha_{i}$ is the constant defined in Subsection 2.1. As we mentioned
before Lemma 2.3, the value $\alpha_{i}$ depends on $n$ and $i$. Furthermore,
$n_{0}$ is a constant depending on $n$ only. Consequently, the value
$\sum_{1\leq i\leq 2n_{0}-1}\alpha_{i}$ depends on $n$. Thus it suffices to
show that

  1. $\bullet$

${\rm pc}(D[V(P)\cup Y])$ is bounded by a constant depending on $n$ only, and

  2. $\bullet$

if $D$ satisfies (D’1), then ${\rm pp}(D[V(P)\cup Y])$ is bounded by a
constant depending on $n$ only.

Let $Q=D[V(P)]$. Note that $Q$ is a pseudo-path in $D$ and $V(Q)=V(P)$. Let
$I=\\{i:1\leq i\leq m,~{}d^{+}_{Q}(u_{i})=2\mbox{ or }d^{-}_{Q}(u_{i})=2\\}$,
and write $I=\\{i_{1},\ldots,i_{p}\\}$ where $i_{1}<i_{2}<\cdots<i_{p}$. Then
$I\cap\\{1,m\\}=\emptyset$ and it follows from (D3) that $p=|I|=r(Q)\leq n$.
For each $h$ with $0\leq h\leq p$, let $Q_{h}=Q[\\{u_{j}:i_{h}\leq j\leq
i_{h+1}\\}]$ where $i_{0}=1$ and $i_{p+1}=m$. Note that $Q_{0}=Q$ if
$I=\emptyset$. By the definition of $I$, $Q_{0},Q_{1},\ldots,Q_{p}$ are
induced directed paths in $D$.

Let

$\displaystyle J_{0}$ $\displaystyle=\\{j:1\leq j\leq n_{0}\mbox{ or
}m-n_{0}+1\leq j\leq m\\},$ $\displaystyle J_{1}$ $\displaystyle=\\{j:1\leq
h\leq p,~{}i_{h}-n+1\leq j\leq i_{h}+n-1\\},\mbox{ and}$ $\displaystyle
Y^{\sharp}$ $\displaystyle=Y\cap\left(\bigcup_{j\in
J_{1}}N_{G_{D}}(u_{j})\right).$

Now we list two facts which will be used in the proof.

  1. (Q1)

We have $X_{0}=\\{u_{i}:i\in J_{0}\\}$. In particular,
$Y\subseteq\bigcup_{\begin{subarray}{c}1\leq j\leq m\\\ j\notin
J_{0}\end{subarray}}N_{G_{D}}(u_{j})$.

  2. (Q2)

For $h$ with $0\leq h\leq p$, $V(Q_{h})\setminus\\{u_{j}:j\in J_{0}\cup
J_{1}\\}\subseteq\\{u_{j}:i_{h}+n\leq j\leq i_{h+1}-n\\}$. In particular, if
$i_{h+1}-i_{h}\leq 2n-1$, then $V(Q_{h})\setminus\\{u_{j}:j\in J_{0}\cup
J_{1}\\}=\emptyset$.

Since $G_{D}$ is $K_{1,n}$-free, we have $\alpha(G_{D}[N_{G_{D}}(u_{j})])\leq
n-1$ for every $j\in J_{1}$. This together with Lemma 2.1 implies the
following:

$\displaystyle{\rm pc}(D[Y^{\sharp}])\leq{\rm pp}(D[Y^{\sharp}])$
$\displaystyle\leq\alpha(G_{D}[Y^{\sharp}])$
$\displaystyle\leq\alpha\left(G_{D}\left[\bigcup_{j\in
J_{1}}N_{G_{D}}(u_{j})\right]\right)$ $\displaystyle\leq\sum_{j\in
J_{1}}\alpha(G_{D}[N_{G_{D}}(u_{j})])$ $\displaystyle\leq|J_{1}|(n-1)$
$\displaystyle\leq p(2n-1)(n-1)$ $\displaystyle\leq n(2n-1)(n-1).$ (3.1)

For each $h$ with $0\leq h\leq p$, let
$Z_{h}=N_{G_{D}}(V(Q_{h})\setminus\\{u_{j}:j\in J_{0}\cup
J_{1}\\})\cap(Y\setminus Y^{\sharp})$. Now we prove that

$Y\setminus Y^{\sharp}$ is the disjoint union of $Z_{0},Z_{1},\ldots,Z_{p}$.
(3.2)

By (Q1) and the definition of $Y^{\sharp}$, we have $Y\setminus
Y^{\sharp}\subseteq\bigcup_{\begin{subarray}{c}1\leq j\leq m\\\ j\notin
J_{0}\cup J_{1}\end{subarray}}N_{G_{D}}(u_{j})$, and hence $Y\setminus
Y^{\sharp}=\bigcup_{0\leq h\leq p}Z_{h}$. Thus it suffices to show that
$Z_{0},Z_{1},\ldots,Z_{p}$ are pairwise disjoint. By way of contradiction, we
suppose that $Z_{h}\cap Z_{h^{\prime}}\neq\emptyset$ for some $h$ and
$h^{\prime}$ with $0\leq h<h^{\prime}\leq p$. Take $z\in Z_{h}\cap
Z_{h^{\prime}}$. Then there exist two indices $a$ and $b$ such that
$zu_{a},zu_{b}\in E(G_{D})$, $i_{h}\leq a\leq i_{h+1}\leq i_{h^{\prime}}\leq
b\leq i_{h^{\prime}+1}$ and $a,b\notin J_{0}\cup J_{1}$. In particular,
$a<i_{h+1}<b$. Then $1\leq h+1\leq p$, and so $\\{j:i_{h+1}-n+1\leq j\leq
i_{h+1}+n-1\\}\subseteq J_{1}$. This implies that $a\leq
i_{h+1}-n<i_{h+1}<i_{h+1}+n\leq b$, and hence
$b-a\geq(i_{h+1}+n)-(i_{h+1}-n)=2n\geq 6$. On the other hand, since $z$ is
adjacent to no vertices in $X_{0}$, applying Lemma 2.4(i) with $y=z$ and
$Q=P$, we have $b-a\leq 3$, which is a contradiction. Consequently, (3.2)
holds.

Recall that $Q_{h}$ is a directed path in $D$, and $u_{i_{h}}$ is either the
internal vertex or terminal vertex of $Q_{h}$. By (Q2), $Z_{h}$ is a subset of
$N_{G_{D}}(V(Q_{h}))$ such that $N_{G_{D}}(z)\cap
V(Q_{h})\subseteq\\{u_{j}:i_{h}+n\leq j\leq i_{h+1}-n\\}$ for every $z\in
Z_{h}$. Thus, applying Lemma 2.6 with $Q=Q_{h}$ and $Y^{\prime}=Z_{h}$, we
obtain the following:

  1. (P1)

For every $h$ with $0\leq h\leq p$, ${\rm pc}(D[V(Q_{h})\cup
Z_{h}])\leq\frac{(n-2)n(n+5)}{2}+6(n-2)$.

  2. (P2)

If $D$ satisfies (D’1), then

    1. $\circ$

${\rm pp}(D[V(Q_{0})\cup Z_{0}])\leq\frac{n(n+5)}{2}+1$ and

    2. $\circ$

for every $h$ with $1\leq h\leq p$, ${\rm
pp}(D[(V(Q_{h})\setminus\\{u_{i_{h}}\\})\cup Z_{h}])\leq\frac{n(n+5)}{2}+1$.

By (3.2), we can easily verify that $V(P)\cup(Y\setminus Y^{\sharp})$ is the
disjoint union of

$V(Q_{0})\cup Z_{0},(V(Q_{1})\setminus\\{u_{i_{1}}\\})\cup
Z_{1},\ldots,(V(Q_{p})\setminus\\{u_{i_{p}}\\})\cup Z_{p}.$

This together with (3.1), (P1) and (P2) implies that

$\displaystyle{\rm pc}(D[V(P)\cup Y])$ $\displaystyle\leq{\rm
pc}(D[Y^{\sharp}])+\sum_{0\leq h\leq p}{\rm pc}(D[V(Q_{h})\cup Z_{h}])$
$\displaystyle\leq
n(2n-1)(n-1)+(p+1)\left(\frac{(n-2)n(n+5)}{2}+6(n-2)\right)$
$\displaystyle\leq
n(2n-1)(n-1)+(n+1)\left(\frac{(n-2)n(n+5)}{2}+6(n-2)\right)$

and, if $D$ satisfies (D’1), then

$\displaystyle{\rm pp}(D[V(P)\cup Y])$ $\displaystyle\leq{\rm
pp}(D[Y^{\sharp}])+{\rm pp}(D[V(Q_{0})\cup Z_{0}])+\sum_{1\leq h\leq p}{\rm
pp}(D[(V(Q_{h})\setminus\\{u_{i_{h}}\\})\cup Z_{h}])$ $\displaystyle\leq
n(2n-1)(n-1)+(p+1)\left(\frac{n(n+5)}{2}+1\right)$ $\displaystyle\leq
n(2n-1)(n-1)+(n+1)\left(\frac{n(n+5)}{2}+1\right).$

This completes the proof of Theorem 1.1.

##  4 Ramsey-type theorem for the cycle cover/partition number of digraphs

A digraph $C$ is called a directed cycle if $G_{C}$ is a cycle and
$d^{+}_{C}(x)=d^{-}_{C}(x)=1$ for every $x\in V(C)$. Let $\Gamma$ be a
(di)graph. When $\Gamma$ is a graph, a family ${\mathcal{C}}$ of subgraphs of
$\Gamma$ is called a cycle cover of $\Gamma$ if
$\bigcup_{C\in{\mathcal{C}}}V(C)=V(\Gamma)$ and each element of
${\mathcal{C}}$ is either a cycle or a connected graph of order at most two.
When $\Gamma$ is a digraph, a family ${\mathcal{C}}$ of subdigraphs of
$\Gamma$ is called a cycle cover of $\Gamma$ if
$\bigcup_{C\in{\mathcal{C}}}V(C)=V(\Gamma)$ and each element of
${\mathcal{C}}$ is either a directed cycle or a weakly connected digraph of
order at most two. A cycle cover ${\mathcal{C}}$ of $\Gamma$ is called a cycle
partition of $\Gamma$ if the elements of ${\mathcal{C}}$ are pairwise vertex-
disjoint. The value $\min\\{|{\mathcal{C}}|:{\mathcal{C}}\mbox{ is a cycle
cover of }\Gamma\\}$ (resp. $\min\\{|{\mathcal{C}}|:{\mathcal{C}}\mbox{ is a
cycle partition of }\Gamma\\}$), denoted by ${\rm cc}(\Gamma)$ (resp. ${\rm
cp}(\Gamma)$), is called the cycle cover number (resp. the cycle partition
number) of $\Gamma$. In [4], the authors proved the following Ramsey-type
result for the cycle partition number of graphs. (They also showed that the
$\\{K^{*}_{n},K_{1,n},P_{n}\\}$-freeness in the theorem is necessary to bound
the cycle cover number by a constant. Thus Theorem B also offers tight
forbidden subgraph conditions on a Ramsey-type theorem for the cycle cover
number of graphs.)

######  Theorem B (Chiba and Furuya [4])

For an integer $n\geq 2$, there exists a constant $c_{0}=c_{0}(n)$ depending
on $n$ only such that ${\rm cp}(G)\leq c_{0}$ for every connected
$\\{K^{*}_{n},K_{1,n},P_{n}\\}$-free graph $G$.

In this section, we give an analogy of Theorem B for digraphs. Let $T_{n}$
denote a transitive tournament of order $n$, i.e., $T_{n}$ is a digraph on
$\\{1,2,\ldots,n\\}$ such that $E(T_{n})=\\{(i,j):1\leq i<j\leq n\\}$. Our
main result in this section is the following.

###### Theorem 4.1

For an integer $n\geq 2$, there exists a constant $c_{1}=c_{1}(n)$ depending
on $n$ only such that ${\rm cp}(D)\leq c_{1}$ for every weakly connected
$T_{n}$-free digraph $D$ such that $G_{D}$ is $\\{K_{1,n},P_{n}\\}$-free.

Since $T_{n}$ has no directed cycles, we have ${\rm
cp}(T_{n})=\lceil\frac{n}{2}\rceil$. In particular, when we consider a
forbidden subdigraph condition assuring us that the cycle cover/partition
number of digraphs is bounded by a constant, some transitive tournaments
appear in the condition. Thus the forbidden structure condition in Theorem 4.1
is best possible in a sense.

Proof of Theorem 4.1. Let $D$ be a weakly connected $T_{n}$-free digraph such
that $G_{D}$ is $\\{K_{1,n},P_{n}\\}$-free. If $G_{D}$ contains a clique $C$
with $|C|=2^{n-1}$, then it is well-known that $D$ contains a copy of $T_{n}$
as an induced subdigraph, which is a contradiction. Thus $G_{D}$ is
$K_{2^{n-1}}$-free. For every connected graph $G$, it is known that
$|V(G)|\leq\Delta(G)^{\mbox{diam}(G)}$, where $\Delta(G)$ and ${\rm diam}(G)$
are the maximum degree and the diameter of $G$, respectively. Since $G_{D}$ is
$\\{K_{2^{n-1}},K_{1,n}\\}$-free, we can easily verify that the maximum degree
of $G_{D}$ is at most $R(2^{n-1}-1,n)-1$. Since $G_{D}$ is $P_{n}$-free, the
diameter of $G_{D}$ is at most $n-2$. Consequently, ${\rm
cp}(D)\leq|V(D)|=|V(G_{D})|\leq\Delta(G_{D})^{\mbox{diam}(G_{D})}\leq(R(2^{n-1}-1,n)-1)^{n-2}$,
as desired. ∎

One might notice that the $K^{*}_{n}$-freeness appearing in Theorem B is
absorbed by the $T_{n}$-freeness in Theorem 4.1. Thus the forbidden structure
in Theorem 4.1 does not form the forbidden subgraph condition in Theorem B
plus additional assumptions which are peculiar to digraphs.

## Acknowledgment

This work was partially supported by JSPS KAKENHI Grant number JP20K03720 (to
S.C) and JSPS KAKENHI Grant number JP18K13449 (to M.F).

## References

  * [1] J.C. Bermond, A. Germa, M.C. Heydemann and D. Sotteau, Longest paths in digraphs, Combinatorica 1 (1981), 337–341.
  * [2] S. Bessy, Paths partition with prescribed beginnings in digraphs: A Chvátal-Erdős condition approach, Discrete Math. 308 (2008), 4108–4115.
  * [3] C.F. Bornstein, J.W.C. Pinto, D. Rautenbach and J.L.Szwarcfiter, Forbidden induced subgraphs for bounded $p$-intersection number, Discrete Math. 339 (2016), 533–538.
  * [4] S. Chiba and M. Furuya, Ramsey-type results for path covers and path partitions, preprint, arXiv:111.00141.
  * [5] S. Chiba, E. Mishio and P. Montalbano, On degree sum conditions for directed path-factors with a specified number of paths, Discrete Math. 343 (2020), 112114.
  * [6] I. Choi, M. Furuya, R. Kim and B. Park, A Ramsey-type theorem for the matching number regarding connected graphs, Discrete Math. 343 (2020), 111648.
  * [7] K.K. Dabrowski, M. Demange and V.V. Lozin, New results on maximum induced matchings in bipartite graphs and beyond, Theoret. Comput. Sci. 478 (2013) 33–40.
  * [8] R. Diestel, “Graph Theory” (5th edition), Graduate Texts in Mathematics 173, Springer, Berlin (2017).
  * [9] D. Duffus, R.J. Gould and M.S. Jacobson, Forbidden subgraphs and the hamiltonian theme, The Theory and Applications of Graphs, pp. 297–316, Wiley, New York (1981).
  * [10] R.J. Faudree and R.J. Gould, Characterizing forbidden pairs for Hamiltonian properties, Discrete Math. 173 (1997), 45–60.
  * [11] M. Furuya, Forbidden subgraphs for constant domination number, Discrete Math. Theor. Comput. Sci. 20(1) (2018), Paper No. 19.
  * [12] T. Gallai and A.N. Milgram, Verallgemeinerung eines graphentheoretischen Satzes von Redei, Acta Sci. Math. 21 (1960), 181–186.
  * [13] R.J. Gould and J.M. Harris, Forbidden triples of subgraphs and traceability, Congr. Numer. 108 (1995), 183–192.
  * [14] R.J. Gould and J.M. Harris, Traceability in graphs with forbidden triples of subgraphs, Discrete Math. 189 (1998), 123–132.
  * [15] R.J. Gould and J.M. Harris, Forbidden triples and traceability: a characterization, Discrete Math. 203 (1999), 101–120.
  * [16] G. Gutin, Finding a longest path in a complete multipartite digraph, SIAM J. Discrete Math. 6 (1993), 270–273.
  * [17] I.B.-A. Hartman, Berge’s conjecture on directed path partitions–a survey, Discrete Math. 306 (2006), 2498–2514.
  * [18] B. Jackson, Long paths and cycles in oriented graphs, J. Graph Theory 5 (1981), 145–157.