Matthew Yancey

19. D. Cranston and M. Yancey, Sparse Graphs Are Near-Bipartite. SIAM J. Discrete Math 34(1) (2020), 1725-1768.

    + Presented at:

        (a) Waterloo Coloring Conference

            University of Waterloo, Waterloo, Canada, September 2019 

    + arXiv: 1903.12570

​

18. M. Yancey, Positively Curved Graphs.  Journal of Graph Theory 94(4) (2020), 539-578. 

    + Presented at:

        (a) University of Illinois Mathematics Department Graph Theory Seminar

            University of Illinois, Urbana, Illinois, September 2017

        (b) Georgia Tech School of Mathematics Combinatorics Seminar

            Georgia Tech, Atlanta, Georgia, December 2017

        (c) University of Utah Department of Mathematics Applied Mathematics Seminar

            University of Utah, Salt Lake City, Utah, April 2018

    + Answers questions from:

        (a) Y. Ollivier and C. Villani, A Curved Brunn-Minkowski Inequality on the Discrete Hypercube. SIAM J. Discrete Math. 26(3) (2012), 983-996.

        (b) N. Alon, B. Boppana, and J. Spencer, An Asymptotic Isoperimetric Inequality. Geometric and Functional Analysis 8 (1996), 411-436.

    + arXiv: 1705.09725

​

16f. A. Parker, K. Yancey, and M. Yancey, Definitions and properties of entropy and distance for regular languages. Dynamical Systems and Random Processes (2019), 139-169; Contemporary Mathematics 736.

    (Full Version of 16, which is a conference proceedings)

​

​17. K. Yancey and M. Yancey, Bipartite Communities via Spectral Partitioning. Proceedings of COCOA (2018), 123–137.

    + Presented at:

        (a) University of Montana Department of Mathematical Sciences Colloquia

            University of Montana, Missoula, Montanna, September 2015 

        (b) Special Session in AMS Spring Western Section Meeting

            UNLV, Las Vegas, Nevada, April 2015

        (c) Knots in Washington (plenary speaker)

            Georgetown University and George Washington University, Washington DC, March 201

        (d) Special Session in AMS Fall Eastern Section Meeting

            Georgetown University, Washington DC, March 2015

        (e) Worcester Polytechnic Institute Department of Mathematical Sciences Colloquia

            Worcester Polytechnic Institute, Worcester, Massachusetts, January 2016

        (f) International Conference on Combinatorial Optimization and Applications

            Atlanta, Georgia, December 2018

    + arXiv: 1412.5666

​

16. A. Parker, K. Yancey, and M. Yancey, Regular Language Distance and Entropy, Proceedings of 42 MFCS (2017), #3.

    + Presented at:

        (a) Special Session in AMS Fall Western Section Meeting

            University of Denver, Denver, Colorado, October 2016

        (b) SIAM Seminar

            Iowa State University, Ames, Iowa, March 2017

        (c) Mathematical Foundations of Computer Science

            University of Aalborg, Aalborg, Denmark, August 2017

        (d) Georgia Tech School of Mathematics Research Horizons Seminar

            Georgia Tech, Atlanta, Georgia, December 2017

    + Independent citation:

       (a) V. Havlena, Comparing Languages and Reducing Automata Used in Network Traffic Filtering.  Proceedings of Excel @ FIT (2017) #14.

       (b) M. Češka, V. Havlena, L. Holik, O. Lengál, T. Vojnar, Approximate Reduction of Finite Automata for High-Speed Network Intrusion Detection.  Proceedings of TACAS (2018), 155-175.

    + arXiv: 1602.07715 

​

15. A. V. Kostochka and M. Yancey, A Brooks-type result for sparse critical graphs, Combinatorica 38(4) (2018), 887-934.

    + Presented at:

        (a)  International Conference on Graph Theory, Combinatorics and Applications

            Zhejiang Normal University, Jinhua, China, October 2012

    + Independent citation:

        (a) L. Postle,  On the Minimum Edge-Density of 5-Critical Triangle-Free Graphs.  Electronic Notes in Discrete Mathematics 49 (2015), 667–673.

        (b) M. Stiebitz and B. Toft, Brooks Theorem (book chapter). Topics in Chromatic Graph Theory (2015), 36-55.

        (c) C. Liu and L. Postle, On the Minimum Edge-Density of 4-Critical Graphs of Girth Five. Journal of Graph Theory 86(4) (2017) 387-405.

        (d) L. Postle, Characterizing 4-critical graphs with Ore-degree at most seven, Journal of Comb. Theory, Series B. 129 (2018), 107-147.

        (e) L. Postle, On the minimum number of edges in triangle-free 5-critical graphs, European J. Combinatorics 66 (2017), 264-280.

    + arXiv: 1408.0846 

​

14. A. Brandt, M. Ferrara, M. Kumbhat, S. Loeb, D. Stolee, and M. Yancey, I,F-partitions of sparse graphs, European Journal of Combinatorics 57 (2016), 1–12.

    + Resolved a question from:

        (a) D. Cranston and D. West, A guide to discharging (arXiv)

    + Presented at:

        (a) Special Session in SIAM Conference on Discrete Mathematics

            UC-Denver, Denver, Colorado, June 2018

    + Independent citation:

        (a) D. Cranston and D. West, An introduction to the discharging method via graph coloring. Discrete Math. 340(4) (2017), 766-793.

​    + arXiv: 1510.03381

​

13. M. Yancey, Coloring the square of a sparse graph G with almost ∆(G) colors, Discrete Applied Mathematics 214 (2016), 211–215.

    + arXiv: 1502.03132

 

12. A. V. Kostochka and M. Yancey, Ore’s Conjecture on color-critical graphs is almost true, Journal of Combinatorial Theory, Series B 109 (2014), 73–101.

    + Presented at:

        (a) Warwick Mathematics Institute Combinatorics Seminar

            University of Warwick, Warwick, England, November 2012

        (b) University of Birmingham Combinatorics Seminar

            University of Birmingham, Birmingham, England, November 2012

        (c)  Special Session in AMS Fall Central Section Meeting

            University of Akron, Akron, Ohio, October 2012

    + Resolved a conjecture from:

        (a) T. Gallai, Kritische Graphen I,Publ. Math. Inst. Hungar. Acad. Sci.8 (1963), 165-192.

    + Independent citation:

        (a) A. Kostochka and B. Reiniger, The minimum number of edges in a 4-critical graph that is bipartite plus 3 edges. European J. Combin. 46 (2015), 89–94.

        (b) L. Postle,  On the Minimum Edge-Density of 5-Critical Triangle-Free Graphs.  Electronic Notes in Discrete Mathematics 49 (2015), 667–673.

        (c) M. Stiebitz and B. Toft, Brooks Theorem (book chapter). Topics in Chromatic Graph Theory (2015), 36-55.

        (d) D. Cranston and L. Rabern, Brooks Theorem and beyond.  Journal of Graph Theory 80(3) (2015), 199-225.

        (e) R. Hoshino and K. Kawarabayashi, The edge density of critical digraphs. Combinatorica 35(5) (2015), 619–631.

        (f) M. Stiebitz, P. Storch, and B. Toft, Decomposable and indecomposable critical hypergraphs. Journal of Combinatorics 7(2-3) (2016), 423–451.

        (g) T. Yao and G. Zhou, Constructing a Family of 4-Critical Planar Graphs with High Edge Density. Journal of Graph Theory 86(2) (2017) 244-249.

        (h) D. Cranston and L. Rabern, Edge Lower Bounds for List Critical Graphs, Via Discharging. Combinatorica 38(5) (2018), 1045-1065.

        (i) H. A. Kierstead and L. Rabern, Extracting List Colorings from Large Independent Sets, Journal of Graph Theory 86(3) (2017) 315-328.

        (j) L. Rabern, A better lower bound on the average degree of online k-list-critical graphs, Electronic J. of Combinatorics 25(1) (2018) #P1.51.

        (k) L. Postle, Characterizing 4-critical graphs with Ore-degree at most seven, Journal of Comb. Theory, Series B. 129 (2018), 107-147.

        (l) L. Postle, On the minimum number of edges in triangle-free 5-critical graphs, European J. Combinatorics 66 (2017), 264-280.

    + arXiv: 1209.1050

 

11. O. V. Borodin, Z. Dvořák, A. V. Kostochka, B. Lidický, and M. Yancey, Planar 4-critical graphs with four triangles, European J. of Combinatorics, 41 (2014), 138–151.

    + Independent citation:

        (a) I. Choi, J. Ekstein, P. Holub, B. Lidický, 3-coloring triangle-free planar graphs with a precolored 9-cycle. Combinatorial Algorithms, LNCS 8986 (2015), 98-109.

        (b) T. Jensen and B. Toft, Unsolved graph colouring problems (book chapter). Topics in Chromatic Graph Theory (2015), 327-357.

        (c) I. Choi, J. Ekstein, P. Holub, and B. Lidický, 3-coloring triangle-free planar graphs with a precolored 9-cycle. European Journal of Combinatorics, 68 (2018) 38-65.

        (d) Z. Dvořák and B. Lidický, Fine structure of 4-critical triangle-free graphs II. Planar triangle-free graphs with two precolored 4-cycles. SIAM J. Discrete Math. 31(2) (2017), 865–874.
        (e) Z. Dvořák and B. Lidický, Fine structure oF 4-critical triangle-free graphs III. General surfaces. SIAM J. Discrete Math. 32(1) (2018), 94-105.

    + arXiv: 1306.1477

 

10. A. V. Kostochka and M. Yancey, Ore’s Conjecture for k = 4 and Grotzsch Theorem, Combinatorica, 34(3) (2014), 323 – 329.

    + Presented at:

        (a)  Sandia Technical Seminar

            Sandia National Laboratories, Livermore, California February 2013

        (b) Central Michigan University Department of Mathematics Colloquia

            Central Michigan University, Mt. Pleasant, Michigan, November 2012

        (c)  Illinois State University Discrete Mathematics Seminar

            Illinois State University, Normal, Illinois, October 2012

    + Independent citation:

        (a) A. Kostochka and B. Reiniger, The minimum number of edges in a 4-critical graph that is bipartite plus 3 edges. European J. Combin. 46 (2015), 89–94.

        (b) M. Stiebitz and B. Toft, Brooks Theorem (book chapter). Topics in Chromatic Graph Theory (2015), 36-55.

        (c) C. Liu and L. Postle, On the Minimum Edge-Density of 4-Critical Graphs of Girth Five. Journal of Graph Theory 86(4) (2017) 387-405.

        (d) D. Cranston and D. West, An introduction to the discharging method via graph coloring. Discrete Math. 340(4) (2017), 766-793.

        (e) D. Cranston and L. Rabern, Edge Lower Bounds for List Critical Graphs, Via Discharging. Combinatorica 38(5) (2018), 1045-1065.

        (f) Z. Dvořák and L. Postle, Density of 5/2-critical graphs. Combinatorica 37(5) (2017), 863-886.

        (g) L. Postle, Characterizing 4-critical graphs with Ore-degree at most seven, Journal of Comb. Theory, Series B. 129 (2018), 107-147.

        (h) L. Postle, On the minimum number of edges in triangle-free 5-critical graphs, European J. Combinatorics 66 (2017), 264-280.

        (i) Z. Dvořák and B. Lidický, Fine structure of 4-critical triangle-free graphs I. Planar Graphs with Two Triangles and 3-Colorability of Chains.  SIAM J. Discrete Math. 32(3) (2018), 1775–1805.

    + arXiv: 1209.1173

 

9. O. V. Borodin, A. V. Kostochka, B. Lidický, and M. Yancey, Short proofs of coloring theorems on planar graphs, European Journal of Combinatorics, 36 (2014), 314–321.

    + Independent citation:

        (a) Z. Dvořák and B. Lidický, 4-critical graphs on surfaces without contractible (≤4)-cycles. SIAM J. Discrete Math. 28(1) (2014), 521–552.

        (b) Z. Dvořák and B. Lidický, 3-Coloring Triangle-Free Planar Graphs with a Precolored 8-Cycle. Journal of Graph Theory 80(2) (2015), 98–111.

        (c) M. Stiebitz and B. Toft, Brooks Theorem (book chapter). Topics in Chromatic Graph Theory (2015), 36-55.

        (d) C. Liu and L. Postle, On the Minimum Edge-Density of 4-Critical Graphs of Girth Five. Journal of Graph Theory 86(4) (2017) 387-405.

        (e) I. Choi, J. Ekstein, P. Holub, and B. Lidický, 3-coloring triangle-free planar graphs with a precolored 9-cycle. European Journal of Combinatorics, 68 (2018) 38-65.

    + arXiv: 1211.3981

 

8. O.V. Borodin, A.O. Ivanova, T.R. Jensen, A.V. Kostochka, and M. Yancey, Describing 3-paths in normal plane maps, Discrete Math., 313(23), (2013), 2702–2711.

    + Independent citation:

        (a) S. jendrol, M. Maceková, and R. Soták, Note on 3-paths in plane graphs of girth 4. Discrete Math. 338(9) (2015), 1643–1648.

        (b) S. jendrol, M. Maceková, and R. Soták,Describing short paths in plane graphs of girth at least 5. Discrete Math. 338(2) (2015), 149–158.

        (c) O. Borodin, A. Ivanova, and D. Woodall, Light C4 and C5 in 3-polytopes with minimum degree 5. Discrete Math. 334 (2014), 63–69.

        (d) S. jendrol, M. Maceková, M. Montassier, and R. Soták, Optimal unavoidable sets of types of 3-paths for planar graphs of given girth. Discrete Math. 339(2) (2016), 780-789.

        (e) O. Borodin and A. Ivanova, Low stars in normal plane maps with minimum degree 4 and no adjacent 4-vertices. Discrete math. 339(2) (2016), 923-930.

        (f) V. Aksenov, O. Borodin, and A. Ivanova, Weight of 3-paths in sparse plane graphs. Electronic J. of Combin. 22(3) Paper #P3.28.

        (g) V. Samodivkin, Roman domination with respect to nondegenerate graph properties: Vertex and edge removal. Australasian Journal of Combin. 63(1) (2015), 41-57.

        (h) O. Borodin and A. Ivanova, An analogue of Franklin's Theorem, Discrete Mathematics 339(10) (2016), 2553-2556.

 

7. O.V. Borodin, A.V. Kostochka, and M. Yancey, On 1-improper 2-coloring of sparse graphs, Discrete Math., 313(22) (2013), 2638–2649.

    + Presented at:

        (a) University of Illinois at Chicago Combinatorics Seminar

            University of Illinois at Chicago, Chicago, Illinois, April 2012

    + Resolved a conjecture from:

        (a) A. Kurek and A. Rucinski, Globally sparse vertex-Ramsey graphs.J. Graph Theory18(1) (1994),7381.

    + Independent citation:

        (a) M. Montassier and P. Ochem, Near-colorings: non-colorable graphs and NP-completeness. Electron. J. Combin. 22 (2015), Paper #P1.57. 

        (b) I. Choi and A. Raspaud, Planar graphs with girth at least 5 are (3,5)-colorable. Discrete Math. 338(4) (2015), 661–667.

        (c) L. Esperet and P. Ochem, Islands in graphs on surfaces. SIAM J. Discrete Math. 30(1) (2016), 206–219.

        (d) J. Kim, A. Kostochka, X. Zhu, Improper coloring of sparse graphs with a given girth, II: Constructions. Journal of Graph Theory 81(4) (2016) 403-413.
        (e) M. Kopreski and G. Yu, Maximum average degree and relaxed coloring. Discrete Math.  340(10) (2017) 2528-2530.
        (f) H. Choi, I. Choi, J. Jeong, and G. Suh, (1, k)-Coloring of Graphs with Girth at Least Five on a Surface. Journal of Graph Theory 84(4) (2017), 521-535.
        (g) M. Axenovich, T. Ueckerdt, and P. Weiner, Splitting Planar Graphs of Girth 6 into Two Linear Forests with Short Paths Journal of Graph Theory 85(3) (2017), 601-618.
        (h) M. Zhang, M. Chen, and Y. Wang, A sufficient condition for planar graphs with girth 5 to be (1, 7)-colorable. Journal of Combinatorial Optimization 33(3) (2017), 847-865.
        (i) J. Czap, S. Jendrol’, and J. Valiska, WORM colorings of planar graphs. Discussiones Mathematicae - Graph Theory 37(2) (2017), 353–368.
        (j) B. Mohar, B. Reed, D. Wood, Colourings with bounded monochromatic components in graphs of given circumference.  Australasian Journal of Combinatorics 69(2) (2017), 236-242.

        (k) R. Belmonte, M. Lampis, V. Mitsou, Parameterized (approximate) defective coloring. Proceedings of 35 STACS (2018), #10

        (l) A. Glebov, Splitting a planar graph of girth 5 into two forests with trees of small diameter.  Disc. Math. 341(7) (2018), 2058-2067.

        (m) C. Lima, D. Rautenbach, U. Souza, J. Szwarcfiter, Bipartizing with a Matching.  Proceedings of COCOA (2018), 198-213.

 

6. S.G. Hartke, D. Stolee, D. West, and M. Yancey, On extremal graphs with a given number of perfect matchings. Journal of Graph Theory, 7(4) (2013), 449-468.

    + Independent citation:

        (a) X. Wang, W. Shang, and J. Yuan, On Graphs with a Unique Perfect Matching. Graphs and Combinatorics 31(5) (2015), 1765-1777.

 

5. A.V. Kostochka and M. Yancey, On Coloring of Sparse Graphs, proceedings of the 8th Computer Science Symposium in Russia, in Lecture Notes in Computer Science 7913, Springer (2013), 49–63.

    + Independent citation:

        (a) J. Conrad, C. Chamberland, N. P. Breuckmann, and B. M. Terhal, The small stellated dodecahedron code and friends. Phil. Trans. R. Soc. A 376 (2017).

​

4. A.V. Kostochka, F. Pfender, and M. Yancey, Large Rainbow Matchings in Large Edge-Colored Graphs. arXiv:1204.3193v1

    + Resolved a conjecture from:

        (a) G. Wang, Rainbow matchings in properly edge colored graphs.Electron. J. Combin.18 (2011),Paper #P162.

    + Independent citation:

        (a) Allan Lo and Ta Sheng Tan, A note on large rainbow matchings in edge-coloured graphs, Graphs and Combinatorics 30 (2014), 389-393

        (b) Allan Lo, Existences of rainbow matchings and rainbow matching covers, Discrete Math. 338(11) (2015), 2119-2124.

        (c) T. LeSaulnier and D West, Rainbow edge-coloring and rainbow domination, Discrete Math. 313(11) (2013), 2020–2025.

    + arXiv: 1204.3193

 

3. A.V. Kostochka, M. Yancey, Large Rainbow Matchings in Edge-Colored Graphs, Combinatorics, Probability and Computing 21, 1-2 (2012), 255–263.

    + Presented at:

        (a) Special Session in AMS Fall Central Section Meeting

            University of Nebraska at Lincoln, Lincoln, Nebraska, October 2011

    + Resolved a conjecture from:

        (a) G. Wang and H. Li, Heterochromatic matchings in edge-colored graphs. Electron. J. Combin.15(2008), Paper #R138.

    + Independent citation:

        (a) Allan Lo and Ta Sheng Tan, A note on large rainbow matchings in edge-coloured graphs, Graphs and Combinatorics 30 (2014), 389-393

        (b) Jennifer Diemunsch, Michael Ferrara, Allan Lo, Casey Moffatt, Florian Pfender and Paul Wenger, Rainbow matchings of size \delta(G) in properly edge-colored graphs, Electronic J. of Combin. 19 (2012), #P52

        (c) Allan Lo, Existences of rainbow matchings and rainbow matching covers, Discrete Math., 338(11) (2015), 2119-2124.

        (d) F. Pfender and V. Le, Complexity results for rainbow matchings, Theoretical Computer Science 524 (2014), 27-33.

        (e) J. Babu, L. Chandran, and D. Rajendraprasad, Heterochromatic paths in edge colored graphs without small cycles and heterochromatic-triangle-free graphs. European J. Combin. 48 (2015), 110–126.

        (f) J. Babu, L. Chandran, and K. Vaidyanathan,  Rainbow matchings in strongly edge-colored graphs. Discrete Math. 338(7) (2015), 1191–1196.

        (g) R. Glebov, B. Sudakov, and T. Szabó,  How many colors guarantee a rainbow matching? Electron. J. Combin. 21 (2014), Paper #P1.27.

        (h) M. Axenovich, K. Knauer, J. Stumpp, and T. Ueckerdt,  Online and size anti-Ramsey numbers. J. Comb. 5(1) (2014), 87–114.

        (i) D. Koltar and R. Ziv, Large matchings in bipartite graphs have a rainbow matching. European J. Combin. 38 (2014), 97–101.

        (j) G. Wang, J. Zhang, and G. Liu, Existence of rainbow matchings in properly edge-colored graphs. Front. Math. China 7(3) (2012), 543–550.

        (k) T. LeSaulnier and D West, Rainbow edge-coloring and rainbow domination, Discrete Math. 313(11) (2013), 2020–2025.

        (l) I. Dejter, Rainbow tetrahedra in cayley graphs. Discussiones Mathematicae - Graph Theory 35(4) (2015) 733-754.

        (m) C. Qu, G. Wang, and G. Yan, Orthogonal matchings revisited. Discrete Math. 228(11) (2015) 2080-2088.

        (n) G. Wang, G. Yan, and X. Yu, Existence of rainbow matchings in strongly edge-colored graphs, Discrete Mathematics 339(10) (2016), 2457-2460.

 

2. N. Calkin, K. James, S. Purvis, S. Race, K. Schneider, and M. Yancey, Counting kings: as easy as λ1, λ2, λ3,..., Congr. Numer. 183 (2006), 83–95.

 

1. N. Calkin, K. James, S. Purvis, S. Race, K. Schneider, and M. Yancey, Counting kings: explicit formulas, recurrence relations, and generating functions! Oh my! Congr. Numer. 182 (2006), 41–51.

    + Independent citation:

        (a) D. DeFord, Enumerating tilings of rectangles by squares with recurrence relations. J. Comb. 6(3) (2015), 339–351.