Preprints - Douglas B. West

For additional information, see my home page, list of abstracts (ps pdf), and publication list (ps pdf). All my papers since 1995 are accessible here, plus a few earlier ones. Other earlier papers may eventually be scanned to complete this list if I can find the time. Note: URL for access by DOI is http://dx.doi.org/[DOI].

PDF Slides for Recent Invited Lectures

  • "An Introduction to the Discharging Method via Graph Coloring": slides of instructional version for Oakland University math camp (Aug 2017) and MCCC (Oct 2017); earlier more advanced slides for two talks at 3rd KIAS Combinatorics Workshop, Seoul (Mar 2014), and 44th SE Intl Conf on Combinatorics, Graph Theory, and Computing, Boca Raton, FL (Mar 2013)
  • "Ordered Ramsey Theory and Track Representations of Graphs" slides: 16th Haifa Workshop on Interdisciplinary Applications of Graphs, Combinatorics and Algorithms (Jun 2016)
  • "Fractional Separation Dimension: A Fractional Covering Problem" slides: 16th Haifa Workshop on Interdisciplinary Applications of Graphs, Combinatorics and Algorithms (Jun 2016)
  • "Coloring, Sparseness, and Girth" slides: 3rd Istanbul Design Theory, Graph Theory and Combinatorics Workshop (Jun 2016), Intl Workshop on Graph Theory and Combinatorics, Coimbatore (Dec 2015), and 8th Slovenian Conference on Graph Theory, Kranjska Gora (Jun 2015)
  • "Some Things I Don't Know" slides: Joint Math Meetings (special session), Baltimore (Jan 2014)
  • "Acquisition Parameters of Graphs" slides: Graph Theory Workshop, Jinhua, China (Dec 2013), 23rd Cumberland Conf, U. Mississippi (May 2010), and MCCCC 2009, Rochester, NY (Oct 2009)
  • "On-line Choice Number or Paintability of Graphs" slides: 44th SE Intl Conf on Combinatorics, Graph Theory, and Computing, Boca Raton, FL (Mar 2013)
  • "The Game of Revolutionaries and Spies" slides: GRASTA 2012, Banff (Oct 2012), and Zhoushan Island, China, (Dec 2012)
  • Links to slides for earlier one-hour lectures

    Preprints, with publication data and pdf slides where available

  • 241. The unit acquisition number of a graph (with F. Johnson, A. Raleigh, and P.S. Wenger) (submitted) pdf (19pp)
  • 240. Covering and packing for i-forests and matroid truncation (with G. Fan, H. Jiang, P. Li, and D. Yang) (submitted)
  • 239. Online sum-paintability: Slow-coloring of trees (with G.J. Puleo) (submitted) pdf (12pp) slides
  • 238. On-line size Ramsey number for ordered tight paths (with X. Pérez-Giménez and P. Pralat) (under revision) slides
  • 237. Online paintability: The slow-coloring game (with T. Mahoney and G.J. Puleo) (submitted) pdf (17pp) slides, older slides
  • 236. Randomly twisted hypercubes (with A. Dudek, X. Pérez-Giménez, P. Pralat, H. Qi, and X. Zhu) (submitted) pdf (11pp)
  • 235. Reconstruction from the deck of k-vertex induced subgraphs (with H. Spinoza) (submitted) pdf (22pp) slides
  • 234. Strongly connectable digraphs and non-transitive dice (with S. Joyce, A. Schaefer, and T. Zaslavsky) (submitted) pdf (8pp)
  • 233. Fractional and circular separation dimension of graphs (with S.J. Loeb) Europ. J. Combinatorics (accepted) pdf (23pp) slides
  • 232. Antipodal coloring of hypercubes (with J.I. Wise) Discussiones Math. Graph Theory (in press) pdf (13pp)
  • 231. Decomposition of regular hypergraphs (with J.O. Choi) J. Combinatorics (in press) pdf (13pp)
  • 230. The vulnerability of the diameter of enhanced hypercubes (with M. Ma and J.-M. Xu) Theoretical Comp. Sci. 694C (2017), 60-65. pdf (9pp)
  • 229. The game saturation number of a graph (with J.M. Carraher, W.B. Kinnersley, and B. Reiniger) J. Graph Theory 85 (2017), 481-495. pdf (14pp)
  • 228. An introduction to the discharging method via graph coloring (with D.W. Cranston) Discrete Math. 340 (2017), 766-793. pdf (50pp), earlier longer version (78pp)
  • 227. Bar visibility numbers for hypercubes and outerplanar digraphs (with J.I. Wise) Graphs and Combinatorics 33 (2017), 221-231. pdf (10pp)
  • 226. Uniquely t-cycle saturated graphs (with P.S. Wenger) J. Graph Theory 85 (2017), 94-106. pdf (14pp)
  • 225. Circular chromatic Ramsey number (with K.F. Jao, C. Tardif, and X. Zhu) J. Combinatorics 8 (2017), 189-208. pdf (14pp)
  • 224. Minimum degree and dominating paths (with R.J. Faudree, R.J. Gould, and M.S. Jacobson) J. Graph Theory 84 (2017), 202-213. pdf (12pp) slides
  • 223. Decomposition of sparse graphs into forests: The Nine Dragon Tree Conjecture for k≤2 (with M. Chen, S.-J. Kim, A.V. Kostochka, and X. Zhu) J. Comb. Theory (B) 122 (2017), 741-756. pdf (15pp) slides
  • 222. Coloring, sparseness, and girth (with N. Alon, A.V. Kostochka, B. Reiniger, and X. Zhu) Israel J. Mathematics 214 (2016), 315-331. pdf (13pp) slides
  • 221. A new proof that 4-connected planar graphs are Hamiltonian-connected (with X. Lu) Discussiones Math. Graph Theory 36 (2016), 555-564. pdf (9pp) slides
  • 220. To catch a falling robber (with W.B. Kinnersley and P. Pralat) Theoretical Comp. Sci. 627 (2016), 107-111. pdf (7pp)
  • 219. On r-dynamic coloring of graphs (with S. Jahanbekam, J. Kim, and S. O) Discrete Applied Mathematics 206 (2016), 65-72. pdf (13pp) slides
  • 218. Extremal problems for degree-based topological indices (with Y. Tang and B. Zhou) Discrete Applied Mathematics 203 (2016), 134-143. pdf (16pp)
  • 217. Anti-Ramsey problems for t edge-disjoint rainbow spanning subgraphs: cycles, matchings, or trees (with S. Jahanbekam) J. Graph Theory 82 (2016), 75-89. pdf (16pp)
  • 216. Cubic graphs with large ratio of independent domination number to domination number (with S. O) Graphs and Combinatorics 32 (2016), 773-776. pdf (4pp)
  • 215. Rainbow spanning subgraphs of small diameter in edge-colored complete graphs (with S. Jahanbekam) Graphs and Combinatorics 32 (2016), 707-712. pdf (6pp)
  • 214. Degree-associated reconstruction parameters of complete multipartite graphs and their complements (with M. Ma, H. Shi, and H. Spinoza) Taiwanese J. Math. 19 (2015), 1271-1284. pdf (12pp)
  • 213. Ordered Ramsey theory and track representations of graphs (with K.G. Milans and D. Stolee) J. Combinatorics 6 (2015), 445-456. pdf (9pp) slides
  • 212. Sharp bounds on the Chinese Postman Problem for 3-regular graphs and multigraphs (with S. O) Discrete Applied Mathematics 190/191 (2015), 163-168. ps pdf (10pp) slides
  • 211. The adversary degree-associated reconstruction number of double-brooms (with M. Ma and H. Shi) J. Discrete Algorithms 33 (2015), 150-159. pdf (16pp) slides
  • 210. On r-dynamic coloring of grids (with R. Kang and T. Müller) Discrete Applied Math. 186 (2015), 286-290. pdf (8pp)
  • 209. Sharp lower bounds on the fractional matching number (with R.E. Behrend and S. O) Discrete Applied Mathematics 186 (2015), 272-274. ps pdf (4pp)
  • 208. Sum-paintability of generalized theta-graphs (with J. Carraher, T. Mahoney, and G.J. Puleo) Graphs and Combinatorics 31 (2015), 1325-1334. ps pdf (10pp)
  • 207. Beyond Ohba's Conjecture: A bound on the choice number of k-chromatic graphs with n vertices (with J.A. Noel, H. Wu, and X. Zhu) Europ. J. Combinatorics 43 (2015), 295-305. ps pdf (13pp) slides
  • 206. The 1,2,3-Conjecture and 1,2-Conjecture for sparse graphs (with D.W. Cranston and S. Jahanbekam) Discussiones Math. Graph Theory 34 (2014), 769-799. ps pdf (29pp) slides
  • 205. Linear discrepancy of chain products and posets of bounded degree (with J.O. Choi and K.G. Milans) Order 31 (2014), 291-305. ps pdf (14pp) slides
  • 204. Permutation bigraphs and interval containments (with P. K. Saha, M. Basu, and M. K. Sen) Discrete Applied Math. 175 (2014), 71-78. ps pdf (15pp)
  • 203. Three topics in online list coloring (with J. Carraher, S. Loeb, T. Mahoney, G.J. Puleo, and M.-T. Tsai) J. Combinatorics 5 (2014), 115-130. ps pdf (13pp) slides
  • 202. Cutwidth of triangular grids (with L. Lin and Y. Lin) Discrete Math. 331 (2014), 89-92. pdf (7pp)
  • 201. Equicovering subgraphs of graphs and hypergraphs (with I. Choi, J. Kim, and A.N. Tebbe) Electronic J. Combinatorics 21 (2014), no. 1, Paper #P1.62, 17pp. ps pdf (15pp)
  • 200. Decomposition of cartesian products of regular graphs into isomorphic trees (with K.F. Jao and A.V. Kostochka) J. Combinatorics 4 (2013), 469-490. ps pdf (18pp)
  • 199. New lower bounds on matching numbers of general and bipartite graphs (with S. Jahanbekam) Congressus Numer. 218 (2013), 57-59. ps pdf (3pp)
  • 198. Extremal problems for game domination number (with W.B. Kinnersley and R. Zamani) SIAM J. Discrete Math. 27 (2013), 2090-2107. ps pdf (22pp)
  • 197. Decomposition of sparse graphs into forests and a graph with bounded degree (with S.-J. Kim, A.V. Kostochka, H. Wu, and X. Zhu) J. Graph Theory 74 (2013), 369-391. ps pdf (24pp) slides
  • 196. Total acquisition in graphs (with T.D. LeSaulnier, N. Prince, P.S. Wenger, and P. Worah) SIAM J. Discrete Math. 27 (2013), 1800-1819. ps pdf (24pp)
  • 195. Extremal graphs with a given number of perfect matchings (with S.G. Hartke, D. Stolee, and M. Yancey) J. Graph Theory 73 (2013), 449-468. pdf (22pp)
  • 194. Bounds on the k-dimension of products of special posets (with M. Baym) Order 30 (2013), 779-796. ps pdf (21pp) slides
  • 193. Visibility number of directed graphs (with M. Axenovich, A. Beveridge, and J.P. Hutchinson) SIAM J. Discrete Math. 27 (2013), 1429-1449. ps pdf (24pp)
  • 192. Extensions to 2-factors in bipartite graphs (with J. Vandenbussche) Electronic J. Combinatorics 20 (2013), no. 3, Paper #11, 10pp. ps pdf
  • 191. Rainbow edge-coloring and rainbow domination (with T.D. LeSaulnier) Discrete Math. 313 (2013), 2020-2025. pdf (11pp) slides
  • 190. Game matching number of graphs (with D.W. Cranston, W.B. Kinnersley, and S. O) Discrete Applied Math. 161 (2013), 1828-1836. ps pdf (15pp) slides
  • 189. Acquisition-extremal graphs (with T.D. LeSaulnier) Discrete Applied Math. 161 (2013), 1521-1529. ps pdf (15pp)
  • 188. Degree Ramsey numbers of cycles and blowups of trees (with T. Jiang and K.G. Milans) European J. Combinatorics 34 (2013), 414-423. ps pdf (14pp)
  • 187. Chain-making games in grid-like posets (with D.W. Cranston, W.B. Kinnersley, K.G. Milans, and G.J. Puleo) ps pdf (14pp) J. Combinatorics 3 (2012), 633-649.
  • 186. Revolutionaries and spies in trees and unicyclic graphs (with D.W. Cranston and C.D. Smyth) J. Combinatorics 3 (2012), 195-205. ps pdf (9pp)
  • 185. Multicolor on-line degree Ramsey numbers of trees (with W.B. Kinnersley) J. Combinatorics 3 (2012), 91-100. ps pdf (8pp)
  • 184. Locating a robber on a graph via distance queries (with J. Carraher, I. Choi, M. Delcourt, and L.H. Erickson) Theoretical Comp. Sci. 463 (2012), 54-61. ps pdf (14pp)
  • 183. Revolutionaries and Spies: Spy-good and spy-bad graphs (with J.V. Butterfield, D.W. Cranston, G. Puleo, and R. Zamani) Theoretical Comp. Sci. 463 (2012), 35-53. ps pdf (34pp) updated slides
  • 182. Cycle spectra of Hamiltonian graphs (with K. Milans, F. Pfender, D. Rautenbach, and F. Regen) J. Comb. Theory (B) 102 (2012), 869-874. ps pdf (16pp)
  • 181. The A4-structure of a graph (with M.D. Barrus) J. Graph Theory 71 (2012), 159-175. ps pdf (18pp)
  • 180. Spanning cycles through specified edges in bipartite graphs (with R. Zamani) J. Graph Theory 71 (2012), 1-17. pdf (16pp) slides
  • 179. Vertex degrees in outerplanar graphs (with K. F. Jao) J. Comb. Math. & Comb. Comput. 82 (2012), 229-239. ps pdf (10pp) slides
  • 178. Packing of graphic n-tuples (with A.H. Busch, M.J. Ferrara, S.G. Hartke, M.S. Jacobson, and H. Kaul) J. Graph Theory 70 (2012), 29-39. ps pdf (11pp)
  • 177. Overlap number of graphs (with D.W. Cranston, N. Korula, T.D. LeSaulnier, K.G. Milans, C.J. Stocker, and J. Vandenbussche) J. Graph Theory 70 (2012), 10-28. ps pdf (21pp) slides
  • 176. Degree Ramsey numbers of graphs (with W.B. Kinnersley and K.G. Milans) Combin., Probab., & Comput. 21 (2012), 229-253. ps pdf (27pp) slides
  • 175. Length thresholds for graphic lists given fixed largest and smallest entries and bounded gaps (with M.D. Barrus, S.G Hartke, and K.F. Jao) Discrete Math. 312 (2012), 1494-1501. ps pdf (14pp)
  • 174. Uniquely C4-saturated graphs (with J. Cooper, J. Lenz, T.D. LeSaulnier, and P.S. Wenger) Graphs and Combinatorics 28 (2012), 189-197. ps pdf (9pp)
  • 173. Packing of Steiner trees and S-connectors in graphs (with H. Wu) J. Combin. Th. (B) 102 (2012), 186-205. ps pdf (28pp) slides
  • 172. Connected domination number of a graph and its complement (with H. Karami, A. Khodkar, and S.M. Sheikholeslami) Graphs and Combinatorics 28 (2012), 123-131. ps pdf (9pp)
  • 171. Longest cycles in k-connected graphs with given independence number (with S. O and H. Wu) J. Combin. Th. (B) 101 (2011), 480-485. ps pdf (8pp) slides
  • 170. A short proof of the Berge-Tutte Formula and the Gallai-Edmonds Structure Theorem, European J. Combinatorics 32 (2011), 674-676. ps pdf (4pp)
  • 169. A new proof of 3-colorability of Eulerian triangulations (with M.-T. Tsai) Ars Mathematicae Contemp. 4 (2011), 73-77. ps pdf (6pp)
  • 168. On-line Ramsey Theory for bounded-degree graphs (with J. Butterfield, T. Grauman, W.B. Kinnersley, K.G. Milans, and C.J. Stocker) Electronic J. Combinatorics 18 (2011), Paper P136, 22 pages. ps pdf slides
  • 167. Acyclic sets in k-majority tournaments (with K.G. Milans and D.H. Schreiber) Electronic J. Combinatorics 18 (2011), Paper P122, 8 pages. ps pdf
  • 166. Equitable hypergraph orientations (with Y. Caro and R. Yuster) Electronic J. Combinatorics 18 (2011), Paper P121, 6 pages. ps pdf slides
  • 165. Matching and edge-connectivity in regular graphs (with Suil O) European J. Combinatorics 32 (2011), 324-329. ps pdf (8pp)
  • 164. Degree-splittability of multigraphs and caterpillars (with J.O. Choi and L. Ozkahya) Proc. 41st SE Conf., Congressus Numer. 202 (2010), 137--147. ps pdf (9pp)
  • 163. The edge-count criterion for degree lists (with G. Isaak) Electronic J. Combinatorics 17 (2010), Paper N36, 4 pages. ps pdf (4pp)
  • 162. Degree-associated reconstruction number of graphs (with M.D. Barrus) Discrete Math. 310 (2010), 2600-2612. ps pdf (21pp) slides
  • 161. Forbidden subposets for fractional weak discrepancy at most k (with J. O. Choi) European J. Combinatorics 31 (2010), 1957-1963. ps pdf (9pp)
  • 160. Rainbow matching in edge-colored graphs (with T.D. LeSaulnier, C.J. Stocker, and P.S. Wenger) Electronic J. Combinatorics 17 (2010), Paper N26, 5 pages. ps pdf (5pp) slides
  • 159. Decomposition of sparse graphs, with application to game coloring number (with M. Montassier, A. Pêcher, A. Raspaud, and X. Zhu) Discrete Math. 310 (2010), 1520-1523. ps pdf (7pp) slides
  • 158. A short proof of the Erdős-Gallai characterization of degree lists (with A. Tripathi and S. Venugopalan) Discrete Math. 310 (2010), 843-844. ps pdf (3pp)
  • 157. Balloons, cut-edges, matchings, and total domination in regular graphs of odd degree (with S. O) J. Graph Theory 64 (2010), 116-131. ps pdf (16pp)
  • 156. Oriented diameter of graphs with diameter 3 (with P.K. Kwok and Q. Liu) J. Combinatorial Theory (B) 100 (2010), 265-274. ps pdf (12pp)
  • 155. Extremal problems for Roman domination (with E.W. Chambers, W.B. Kinnersley, and N. Prince) SIAM J. Discrete Math. 23 (2009), 1575-1586. ps pdf (15pp)
  • 154. Matching extendibility in hypercubes (with J. Vandenbussche) SIAM J. Discrete Math. 23 (2009), 1539-1547. ps pdf (11pp)
  • 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, W.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 (2004), \#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 many leaves (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 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 2P3-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 (Proc. 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

    Below are preprints of earlier papers for which I was able to find old files that I could still make run under groff. There are also scans of a few requested papers that I believe are now in Open Archive, since it has been at least 20 years since they were published. In particular, I occasionally receive requests for old papers on interval number of graphs: #42,34,21,18,15,13,5. Nevertheless, when I still have a preprint I will post that and not a scan or pdf of the published version.

  • 70. Gray code enumeration of families of integer partitions (with D. Rasmussen and C.D. Savage) J. Combinatorial Theory A 70 (1995), 201-229. ps pdf (32pp)
  • 64. Gray code results for acyclic orientations (with C.D. Savage and M.B. Squire) Congressus Numerantium 96 (1993), 185-204. ps pdf (21pp)
  • 59. Vertex degrees in planar graphs (with T.G. Will). In Planar Graphs, (W.T. Trotter, ed.) DIMACS Series Discrete Math. Theor. Comp. Sci. 9 (1993), 139-149. ps pdf (21pp)
  • 58. Large P4-free graphs with bounded degree (with M.-S. Chung). J. Graph Theory 17 (1993), 109-116. downloaded pdf (8pp)
  • 51. Spanning trees with many leaves (with D.J. Kleitman). SIAM J. Discrete Math. 4 (1991), 99-106. pdf (9pp)
  • 42. Interval representations of cliques and of subset intersection graphs (with E.R. Scheinerman). In Combinatorial Mathematics (Proc. 3rd Intl. Conf. Combinatorics, New York 1985, G.S. Bloom et al, eds.) Ann. N.Y. Acad. Sci. 555 (1989), 363--367. ps pdf (4pp)
  • 34. An improved edge bound on the interval number of a graph (with J. Spinrad and G. Vijayan). J. Graph Theory 11 (1987), 447-449. pdf scan (3pp)
  • 31. Poset boxicity of graphs (with W.T. Trotter). Discrete Math. 64(1987), 105-107. pdf (3pp)
  • 21. A note on the interval number of a graph (with P. Erdős). Discrete Math. 55(1985), 129-133. pdf scan (5pp)
  • 18. Recognizing graphs with fixed interval number is NP-complete (with D.B. Shmoys). Discrete Appl. Math. 8(1984), 295-305. pdf scan (11pp)
  • 15. The interval number of a complete multipartite graph (with L.B. Hopkins and W.T. Trotter). Discrete Appl. Math. 8(1984), 163-187. pdf scan (25pp)
  • 13. The interval number of a planar graph -- three intervals suffice (with E.R. Scheinerman). J. Combinatorial Theory B 35(1983), 224-239. pdf scan (16pp)
  • 12. Gossiping without duplicate transmissions. SIAM J. Algebraic & Discrete Meth. 3(1982), 418-419. pdf (2pp)
  • 11. A class of solutions to the gossip problem, III. Discrete Math. 40(1982), 285-310. pdf (26pp)
  • 10. A class of solutions to the gossip problem, II. Discrete Math. 40(1982), 87-113. pdf (27pp)
  • 9. A class of solutions to the gossip problem, I. Discrete Math. 39(1982), 307-326. pdf (20pp)
  • 5. Extremal values of the interval number of a graph (with J.R. Griggs). SIAM J. Alg. Disc. Meth. 1(1980), 1-7. pdf scan (7pp)
  • 4. Maximum antichains of rectangular arrays (as part of G.W. Peck). J. Combinatorial Theory A 27 (1979), 397-400. pdf scan (4pp)
  • Slides for older one-hour lectures

  • "Topics in Matching: The Chinese Postman and Game Matching Problems", slides: Zhengzhou University, Zhengzhou, China (Apr 2013)
  • "Strengthening choosability results to paintability", at Cycles & Colourings 2012, High Tatras, Slovakia, September 2012 slides
  • "Two results on long cycles", at Cycles & Colourings 2010, Tatranska Strba, Slovakia, September, 2010 Fouquet-Jolivet slides, F-Hamiltonian bigraph slides
  • "Decomposition of sparse graphs", at International Conference on Recent Trends in Graph Theory and Combinatorics, Cochin, India, August, 2010 slides
  • "Degree Ramsey and On-Line Degree Ramsey Numbers", at Workshop in Graph Theory, Tiruchirappalli, India August, 2010. slides. [updated from 2009 Workshop on Graph Theory (Kaohsiung), Graph Theory 2008 (honoring Carsten Thomassen's 60th birthday), and MIGHTY XLVII.]
  • "Old and New Results on Degree Lists of Graphs", at CoNE Revisited (in memory of Michael O. Albertson), Smith College, Northampton, MA, March 27, 2010. slides
  • "Three Variations on Edge-Coloring", at 12th CID Meeting, Karpacz, Poland, September 2007, slides
  • "Coloring and List Coloring in Graphs and Hypergraphs", for Math 499, slides
  • "Circular Coloring", at Graph Theory with Altitude, May 2005, (honoring Joan Hutchinson's 60th Birthday) scanned slides (my final handwritten talk)