Preprints since 1995 - Douglas B. West

Additional information appears on my home page, list of abstracts (ps pdf), and publication list (ps pdf). Papers before 1995 may eventually be scanned to complete this list, if I can find or recreate the preprints (many are in groff or have obsolete tex macros).

PDF Slides for One-hour Lectures

Lecture "Acquisition Parameters of Graphs", given at MCCCC 2009 (honoring Wal Wallis' 68th Birthday), Rochester, New York, October 2009. slides

Lecture "Degree Ramsey and On-Line Degree Ramsey Numbers", given at Graph Theory 2008 (honoring Carsten Thomassen's 60th birthday), MIGHTY XLVII, and 2009 Workshop on Graph Theory (Kaohsiung) slides

Lecture "Three Variations on Edge-Coloring", 12th CID Meeting, Karpacz, Poland, September 2007, slides

Expository lecture on "Coloring and List Coloring in Graphs and Hypergraphs" slides

Expository lecture on "Circular Coloring" for Graph Theory with Altitude, May 2005, (honoring Joan Hutchinson's 60th Birthday) scanned slides

PDF Slides for talks on papers in preparation

172. Overlap number of graphs (with D.W. Cranston, N. Korula, T. LeSaulnier, K. Milans, C. Stocker, and J. Vandenbussche) slides

171. On-line Ramsey Theory for bounded degree graphs (with J. Butterfield, T. Grauman, B. Kinnersley, K. Milans, and C. Stocker) slides

170. Acquisition number of graphs (with T.D. LeSaulnier, N. Prince, P.S. Wenger, and P. Worah) slides

Preprints, with publication data and pdf slides where available

170. Packing of graphic sequences (with A.H. Busch, M.J. Ferrara, S.G. Hartke, M.S. Jacobson, and H. Kaul) (submitted) ps pdf (11pp)

169. Decomposition of sparse graphs, with application to game coloring number (with M. Montassier, A. Pêcher, A. Raspaud, and X. Zhu) (submitted) ps pdf (7pp)

168. The edge-count criterion for degree lists (with G. Isaak) (submitted) ps pdf (4pp)

167. Spanning cycles through specified edges in bipartite graphs (with R. Zamani) (submitted) ps pdf (12pp)

166. Cycle spectra of Hamiltonian graphs (with K. Milans, D. Rautenbach, and F. Regen) (submitted) ps pdf (16pp)

165. A short proof of the Erdős-Gallai characterization of degree lists (with A. Tripathi and S. Venugopalan) Discrete Math. (accepted) ps pdf (3pp)

164. On the degree-associated reconstruction number of graphs (with M. Barrus) (submitted) ps pdf (21pp) slides

163. Ore, Berge-Tutte, and Gallai-Edmonds (submitted) ps pdf (5pp)

162. Inequalities of Nordhaus-Gaddum type for connected domination (with H. Karami, A. Khodkar, and S.M. Sheikholeslami) (submitted) ps pdf (8pp)

161. Linear discrepancy and products of chains (with J. O. Choi) (submitted) ps pdf (15pp)

160. Bounds on the k-dimension of products of special posets (with M. Baym) (submitted) ps pdf (18pp) slides

159. Forbidden subposets for fractional weak discrepancy at most k (with J. O. Choi) (accepted pending revision) ps pdf (9pp)

158. Induced Turán problems: Largest P_m-free graphs with bounded degree (with M.S. Chung and T. Jiang) (accepted pending revision) ps pdf (22pp) slides

157. Balloons, cut-edges, matchings, and total domination in regular graphs of odd degree (with S. O) J. Graph Theory, in press. ps pdf (16pp)

156. Extremal problems for Roman domination (with E.W. Chambers, B. Kinnersley, and N. Prince) SIAM J. Discrete Math., 23 (2009), 1575-1586. ps pdf (15pp)

155. Matching extendibility in hypercubes (with J. Vandenbussche) SIAM J. Discrete Math., 23 (2009), 1539-1547. ps pdf (11pp)

154. Oriented diameter of graphs with diameter 3 (with P.K. Kwok and Q. Liu) J. Combinatorial Theory (B), published online August 2009. ps pdf (12pp)

153. The pagenumber of k-trees (with J. Vandenbussche and G. Yu) SIAM J. Discrete Math., 23 (2009), 1455-1464. ps pdf (9pp)

152. Classes of 3-regular graphs that are (7,2)-edge-choosable (with D.W. Cranston) SIAM J. Discrete Math., 23 (2009), 872-881. ps pdf (12pp)

151. Chromatic number for a generalization of Cartesian product graphs (with D. Král') Electronic J. Combinatorics 16 (2009), Paper #R71, 9 pages. ps pdf (9pp)

150. Proper path-factors and interval edge-coloring of (3,4)-biregular bigraphs (with A.S. Asratian, C.J. Casselgren, and J. Vandenbussche) J. Graph Theory 61 (2009), 88-97. ps pdf (12pp) slides

149. Independence number of 2-factor-plus-triangles graphs (with J. Vandenbussche) Electronic J. Combinatorics 16 (2009), Research article #R27, 14pp. ps pdf (14pp) slides

148. Implications among linkage properties in graphs (with Q. Liu and G. Yu) J. Graph Theory 60 (2009), 327-337. ps pdf (11pp)

147. Repetition number of graphs (with Y. Caro) Electronic J. Combinatorics 16 (2009), Research article #R7, 14pp. ps pdf (15pp) slides

146. Optimal strong parity edge-coloring of complete graphs (with D. Bunde, K. Milans, and H. Wu) Combinatorica 28 (2008), 625-632. ps pdf (7pp) slides

145. Duality for semiantichains and unichain coverings in products of special posets (with Q. Liu) Order 25 (2008), 359-367. ps pdf (9pp) slides

144. Triangle-free planar graphs with minimum degree 3 have radius at least 3 (with S.-J. Kim) Discuss. Math. Graph Theory 28 (2008), 563-566. ps pdf (3pp)

143. (5,2)-coloring of sparse graphs (with O.V. Borodin, S.G. Hartke, A.O. Ivanova, and A.V. Kostochka) Siberian Electr. Math. Reports 5 (2008), 417-426. ps pdf (19pp)

142. The hub number of a graph (with T. Grauman, S.G. Hartke, A. Jobson, B. Kinnersley, L. Wiglesworth, P. Worah, and H. Wu) Info. Proc. Lett. 108 (2008) 226-228. ps pdf (6pp)

141. Long local search for maximal bipartite subgraphs (with H. Kaul) SIAM J. Discrete Math. 22 (2008), 1138-1144. ps pdf (9pp)

140. Tree-thickness and caterpillar-thickness under girth constraints (with Q. Liu) Electronic J. Combin. 15 (2008), Paper #R93. ps pdf (16pp)

139. Pebbling and optimal pebbling in graphs (with D.P. Bunde, E.W. Chambers, D.W. Cranston, and K. Milans) J. Graph Theory 57 (2008), 215-238. ps pdf (26pp) slides

138. Circular chromatic index of cartesian products of graphs (with X. Zhu) J. Graph Theory 57 (2008), 7-18. ps pdf (10pp) slides

137. Parity and strong parity edge-colorings of graphs (with D. Bunde, K. Milans, and H. Wu) Congressus Numer. 187 (2007), 193-213. ps pdf (20pp) slides

136. Some conjectures of Graffiti.pc on total domination (with E. DeLaVina, Q. Liu, R. Pepper, and B. Waller) Congressus Numer. 185 (2007), 81-95. pdf (15pp)

135. Bounds for cut-and-paste sorting of permutations (with D.W. Cranston and I.H. Sudborough) Discrete Math. 307 (2007), 2866-2870. ps pdf (6pp)

134. Improved bounds on families under k-wise set-intersection constraints (with W. Cao and K. Hwang) Graphs and Combinatorics 23 (2007), 381--386. ps pdf (6pp)

133. Extending precolorings to circular colorings (with M.O. Albertson) J. Comb. Theory (B) 96 (2006), 472-481. ps pdf (13pp)

132. Chvátal's condition cannot hold for both a graph and its complement (with A.V. Kostochka) Discuss. Math. Graph Th. 26 (2006), 73-76. ps pdf (3pp)

131. Nordaus-Gaddum-type theorems for decompositions into many parts (with Z. Füredi, A.V. Kostochka, R. Skrekovski, and M. Stiebitz) J. Graph Theory 50 (2005), 273-292. ps pdf (19pp)

130. Hypergraph extension of the Alon-Tarsi list coloring theorem (with R. Ramamurthi) Combinatorica 25 (2005), 355-366. ps pdf (13pp)

129. Precoloring extensions of Brooks' Theorem (with M.O. Albertson and A.V. Kostochka) SIAM J. Discr. Math. 18 (2004), 542-553. ps pdf (16pp)

128. The visibility number of a graph (with Y.-W. Chang, J.P. Hutchinson, M.S. Jacobson, and J. Lehel) SIAM J. Discr. Math. 18 (2004), 462-471. ps pdf (13pp)

127. Homomorphisms from sparse graphs with large girth (with O.V. Borodin, S.-J. Kim, and A.V. Kostochka) J. Comb. Theory (B) 90 (2004), 147-159. ps pdf (15pp)

126. On pattern Ramsey numbers of graphs (with R.E. Jamison) Graphs and Combinatorics 20 (2004), 333-339. ps pdf (7pp)

125. Interval numbers of powers of block graphs (with M. Chen and G.J. Chang) Discrete Math. 275 (2004), 87-96. ps pdf (14pp)

124. Graphic and protographic lists of integers (with D. Fon-Der-Flaass) Electronic J. Comb 11 (2002), \#1, Paper R4. ps pdf (5pp)

123. Maximum face-constrained colorings of plane graphs (with R. Ramamurthi). Discrete Mathematics 274 (2004), 233-240, and Electronic Notes in Discrete Math. Volume 11 (July 2002 online publication). ps pdf (8pp)

122. Edge-colorings of complete graphs that avoid polychromatic trees (with T. Jiang). Discrete Mathematics 274 (2004), 137-145, and Electronic Notes in Discrete Math. Volume 11 (July 2002 online publication). ps pdf (10pp)

121. Probabilistic methods for decomposition dimension of graphs (with M. Hagita and A. Kündgen) Graphs and Combinatorics 19 (2003), 493--503. ps pdf (10pp)

120. A list analogue of equitable coloring (with A.V. Kostochka and M.J. Pelsmajer) J. Graph Theory 44 (2003), 166-177. ps pdf (11pp)

119. On the Erdös-Simonovits-Sós Conjecture about the anti-Ramsey number of a cycle (with T. Jiang) Combinatorics, Probability, and Computing 12 (2003), 585-598. ps pdf (14pp)

118. Isometric cycles and bridged graphs (with T. Jiang and S.-J. Kim) J. Graph Theory 43(2003), 161-170. ps pdf (11pp)

117. On the existence of Hamiltonian paths in the cover graph of M(n) (with C.D. Savage and I. Shields) Discrete Mathematics 262(2003), 241-252. ps pdf (13pp)

116. Restricted edge-colorings of bicliques (with D. Mubayi) Discrete Mathematics 257(2002), 513-529. ps pdf (16pp)

115. The chromatic spectrum of mixed hypergraphs (with T. Jiang, D. Mubayi, Zs. Tuza, and V. Voloshin) Graphs and Combinatorics 18(2002), 309-318. ps pdf (11pp)

114. A Fibonacci tiling of the plane (with C. Huegy). Discrete Mathematics 249(2002), 111-116. ps pdf (4pp)

113. A proof of the two-path conjecture (with H. Fleischner, R. Molina, and K.W. Smith) Electronic J. Comb 9(2002), \#1, Note 4, 4pp. ps pdf (2pp)

112. Cevian dissections of triangles (with V.J. Matsko and J.E. Wetzel) Journal of Geometry 72(2001), 115-127. ps pdf (12pp)

111. Structural diagnosis of wiring networks: finding connected components of an unknown subgraph (with W. Shi, elaboration of #83) SIAM J. Discr. Math. 14(2001), 510-523.

110. Realizing degree imbalances in directed graphs (with D. Mubayi and T.G. Will). Discrete Mathematics 239(2001), 147-153. ps pdf (4pp)

109. Ramsey theory and bandwidth of graphs (with Z. Füredi) Graphs and Combinatorics 17(2001), 463-471. ps pdf (8pp)

108. On the number of vertices with specified eccentricity (with D. Mubayi) Graphs and Combinatorics 16(2000), 441-452. ps pdf (9pp)

107. Edge-bandwidth of theta graphs (with D. Eichhorn, D. Mubayi, and K. O'Bryant) J. Graph Theory 35(2000), 89-98. ps pdf (9pp)

106. Multiple vertex covering with specified induced subgraphs (with Z. Füredi and D. Mubayi) J. Graph Theory 34(2000), 180-190. ps pdf (9pp)

105. Connected domination and spanning trees (with Y. Caro and R. Yuster) SIAM J. Discrete Math. 13(2000), 202-211. ps pdf (12pp)

104. Perfection thickness of graphs (with H. Asari, T. Jiang, and A. Kündgen) Discrete Math. 215(2000), 263-264. ps pdf (1pp)

103. Generalized chromatic number and generalized girth (with B. Bollobás). Discrete Math. 213(2000), 29-34. ps pdf (6pp)

102. Partially Ordered Sets (with G. Brightwell). Chapter 11 in {\it Handbook of Discrete and Combinatorial Mathematics} (K.H. Rosen, editor-in-chief), (CRC Press, 2000), 717-752. (not available on-line)

101. Every outerplanar graph is a union of two interval graphs (with A.V. Kostochka). (30th SE Conf. Comb. Graph Th. Comp.) Congr. Num. 139(1999), 354-358. ps pdf (3pp)

100. Edge-bandwidth of graphs (with T. Jiang, D. Mubayi, and A. Shastri). SIAM J. Discrete Math. 12(1999), 307-316. ps pdf (13pp)

99. Coloring of trees with minimum sum of colors (with T. Jiang). J. Graph Theory 32(1999), 354-358 ps pdf (5pp)

98. Intersection representation of digraphs in trees with few leaves (with I.-J. Lin and M.K. Sen). J. Graph Theory 32(1999), 340-353. ps (pdf unavailable) (12pp)

97. A short proof that "proper = unit" (with K.P. Bogart). Discrete Math. 201(1999), 21-23. ps pdf (2pp)

96. Diagnosis of wiring networks: An optimal randomized algorithm for finding connected components of unknown graphs (with W. Shi) (elaboration of #75) SIAM J. Computing 28(1999), 1541-1551. ps pdf (12pp)

95. Rectangle number for hypercubes and complete multipartite graphs (with Y.-W. Chang). (29th SE Conf. Comb. Graph Th. Comp.) Congr. Num. 132(1998), 19-28. ps pdf (9pp)

94. The leafage of a chordal graph (with I.-J. Lin and T.A. McKee). Discuss. Math. Graph Th. 18(1998), 23-48. ps pdf (19pp)

93. Largest regular graphs with equal connectivity and independence number (with P.K. Kwok). Proc. 8th Intl. Graph Theory Conf. (Kalamazoo 1996) (Wiley, 1998), 587-589. ps pdf (3pp)

92. Line digraphs and coreflexive vertex sets (with X. Liu). Discr. Math. 188(1998), 269-277.

ps pdf (8pp)

91. Star-factors of tournaments (with G. Chen and X. Lu). J. Graph Theory 28(1998), 141-145. ps pdf (5pp)

90. Bandwidth and density for block graphs (with L.T.Q. Hung, M.M. Syslo and M.L. Weaver). Discrete Math. 189(1998), 163-176.

ps pdf (14pp)

89. Interval number and boxicity of digraphs (with Y.-W. Chang). Proc. 8th Intl. Graph Theory Conf. (Kalamazoo 1996) (Wiley, 1998), 171-179. ps pdf (9pp)

88. The bricklayer problem and the strong cycle lemma (with H. Snevily). Amer. Math. Monthly 105(1998), 131-143. ps pdf (15pp)

87. Short proofs for interval digraphs. Discrete Math. 178(1998), 287-292.

ps pdf (6pp)

86. Classes of interval digraphs and 0,1-matrices (with I.-J. Lin and M.K. Sen). Proc. 28th SE Conf., Congressus Numer. 125(1997), 201-209. ps pdf (9pp)

85. The number of dependent edges in an acyclic orientation (with D.C. Fisher, K. Fraughnaugh, and L. Langley). J. Combinatorial Theory (B) 71(1997), 73-78. ps pdf (5pp)

84. Optimal structural diagnosis of wiring networks (with W. Shi). Proc. 27th Intl. Symp. Fault-Tolerant Computing (FTCS-27) - Seattle 1997 (IEEE Press, 1997), 162-191. ps pdf (25pp)

83. Total interval number for graphs with bounded degree (with A. Kostochka). J. Graph Theory 25(1997), 79-94. ps pdf (7pp)

82. The superregular graphs. J. Graph Theory 23(1996), 289-295. ps pdf (8pp)

81. The total interval number of a graph II: Trees and complexity (with T.M. Kratzke). SIAM J. Discr. Math. 9(1996), 339-348. ps pdf (12pp)

80. Large 2P₃-free graphs with bounded degree (with M.-S. Chung). Discrete Math. 150(1996), 69-79. ps pdf (11pp)

79. The path spectrum of a graph (with M.S. Jacobson, A.E. Kézdy, E. Kubicka, G. Kubicki, J. Lehel, and C. Wang). Proc. 26th SE Conf., Congressus Numer. 112(1995), 49-64. (postscript unavailable)

78. Multitrack interval number (with A. Gyárfás). Proc. 26th SE Conf., Congressus Numer. 109(1995), 109-116. ps pdf (8pp)

77. Representing digraphs using intervals or circular arcs (with M.K. Sen and B.K. Sanyal). Discrete Math. 147(1995), 235-245. ps pdf (11pp)

76. Optimal algorithms for finding connected components of an unknown graph (with W. Shi). In Computing and Combinatorics: 1st Annual International Conference COCOON '95 (Xi'an, China). (eds. D.-Z. Du and M. Li) Lecture Notes in Computer Science 959(1995), 131-140. ps pdf (12pp)

75. Interval number of special posets and random posets (with T. Madej). Discrete Math. 144(1995), 67-74. ps pdf (8pp)

74. Parsimonious 2-multigraphs (with T.G. Will). Graph theory, Combinatorics, and Algorithms (\fIProc. 7th Intl. Conf. Graph Th. - Kalamazoo 1992) (Y. Alavi and A. Schwenk, eds.) (Wiley 1995), 1249-1258. ps pdf (10pp)

73. Interval digraphs that are indifference digraphs (with I.-J. Lin). Graph theory, Combinatorics, and Algorithms (Proc. 7th Intl. Conf. Graph Th. - Kalamazoo 1992) (Y. Alavi and A. Schwenk, eds.) (Wiley 1995), 751-765. ps pdf (15pp)

72. Maximum bandwidth under edge addition (with J.-F. Wang and B. Yao). J. Graph Theory 20(1995), 87-90. ps pdf (4pp)

Miscellaneous earlier papers

I will add versions of some of the earlier papers as I am able to. This is partly a matter of finding which old files will still run under groff. Eventually, perhaps I will make pdf of scans of the old papers.

42. Interval representations of cliques and of subset intersection graphs (with E.R. Scheinerman). In {\it Combinatorial Mathematics} (Proc. 3rd Intl. Conf. Combinatorics, New York 1985, G.S. Bloom et al, eds.) {\it Ann. N.Y. Acad. Sci.} 555(1989), 363--367. ps pdf (4pp)