Graph-theory open problems
989 / 989 rows OPG: open 57partial 137solved 19disproved 13unclear 1 arXiv: open 553partial 132solved 58disproved 14unclear 5 OPG 227 arXiv 762
Title Source Status Subject / attribution Authors Imp. Posted
Caccetta-Häggkvist Conjecture opg open Graph Theory » Directed Graphs Caccetta, L.; Häggkvist, Roland ★★★★ 2013-02-28
5-flow conjecture opg partial Graph Theory » Coloring » Nowhere-zero flows Tutte, William T. ★★★★ 2007-03-07
Cycle double cover conjecture opg partial Graph Theory » Basic Graph Theory » Cycles Seymour, Paul D.; Szekeres, George ★★★★ 2007-03-07
Reconstruction conjecture opg partial Graph Theory Kelly, Paul J.; Ulam, Stanislaw M. ★★★★ 2007-10-18
The Berge-Fulkerson conjecture opg partial Graph Theory » Basic Graph Theory » Matchings Berge, Claude; Fulkerson, Delbert R. ★★★★ 2007-03-07
3-Edge-Coloring Conjecture opg partial Graph Theory Arthur; Hoffmann-Ostenhof ★★★ 2020-04-28
Monochromatic vertex colorings inherited from Perfect Matchings opg partial Graph Theory ★★★ 2019-03-04
Multicolour Erdős--Hajnal Conjecture opg partial Graph Theory » Extremal Graph Theory Erdos, Paul; Hajnal, Andras ★★★ 2019-10-10
Sidorenko's Conjecture opg partial Graph Theory Sidorenko, A. ★★★ 2019-10-10
3-Decomposition Conjecture opg partial Graph Theory Arthur; Hoffmann-Ostenhof ★★★ 2017-01-24
Cycle Double Covers Containing Predefined 2-Regular Subgraphs opg partial Graph Theory Arthur; Hoffmann-Ostenhof ★★★ 2017-06-21
Monochromatic reachability in arc-colored digraphs opg open Graph Theory » Directed Graphs Sands, Bill; Sauer, Norbert W.; Woodrow, Robert E. ★★★ 2017-04-04
Acyclic list colouring of planar graphs. opg partial Graph Theory » Coloring » Vertex coloring Borodin, Oleg V.; Fon-Der-Flasss, D. G.; Kostochka, Alexandr V.; Raspaud, André; Sopena, Eric ★★★ 2013-03-07
Are almost all graphs determined by their spectrum? opg partial Graph Theory ★★★ 2013-03-26
Decomposing a connected graph into paths. opg partial Graph Theory » Basic Graph Theory » Paths Gallai, Tibor ★★★ 2013-03-04
Decomposing an even tournament in directed paths. opg partial Graph Theory » Directed Graphs » Tournaments Alspach, Brian; Mason, David W.; Pullman, Norman J. ★★★ 2013-02-26
Directed path of length twice the minimum outdegree opg partial Graph Theory » Directed Graphs Thomassé, Stéphan ★★★ 2013-02-28
Erdős–Faber–Lovász conjecture EP #19 opg partial Graph Theory » Coloring » Vertex coloring Erdos, Paul; Faber, Vance; Lovasz, Laszlo ★★★ 2013-08-22
Hoàng-Reed Conjecture opg open Graph Theory » Directed Graphs Hoang, Chinh T.; Reed, Bruce A. ★★★ 2013-03-11
Long directed cycles in diregular digraphs opg open Graph Theory » Directed Graphs Jackson, Bill ★★★ 2013-03-01
Oriented trees in n-chromatic digraphs opg partial Graph Theory » Directed Graphs Burr, S. A. ★★★ 2013-02-25
Splitting a digraph with minimum outdegree constraints opg partial Graph Theory » Directed Graphs Alon, Noga ★★★ 2013-03-01
The Bollobás-Eldridge-Catlin Conjecture on graph packing opg partial Graph Theory » Extremal Graph Theory ★★★ 2013-03-23
Ádám's Conjecture opg disproved Graph Theory » Directed Graphs Ádám, András ★★★ 2013-03-01
Vertex Coloring of graph fractional powers opg disproved Graph Theory Iradmusa, Moharram ★★★ 2011-04-23
Beneš Conjecture (graph-theoretic form) opg open Graph Theory Beneš, Václav E. ★★★ 2010-04-17
Strong 5-cycle double cover conjecture opg partial Graph Theory » Basic Graph Theory » Cycles Arthur; Hoffmann-Ostenhof ★★★ 2010-08-03
Are different notions of the crossing number the same? opg partial Graph Theory » Topological Graph Theory » Crossing numbers Pach, János; Tóth, Géza ★★★ 2009-11-03
Crossing numbers and coloring opg partial Graph Theory » Topological Graph Theory » Crossing numbers Albertson, Michael O. ★★★ 2009-09-04
Graphs with a forbidden induced tree are chi-bounded opg partial Graph Theory » Coloring » Vertex coloring Gyarfas, Andras ★★★ 2009-05-16
Shannon capacity of the seven-cycle opg partial Graph Theory ★★★ 2009-02-19
Shuffle-Exchange Conjecture (graph-theoretic form) opg open Graph Theory Beneš, Václav E.; Folklore; Stone, Harold S. ★★★ 2009-10-30
Characterizing (aleph_0,aleph_1)-graphs opg partial Graph Theory » Infinite Graphs Diestel, Reinhard; Leader, Imre ★★★ 2008-06-26
Cores of strongly regular graphs opg solved Graph Theory » Algebraic Graph Theory Cameron, Peter J.; Kazanidis, Priscila A. ★★★ 2008-06-16
Degenerate colorings of planar graphs opg partial Graph Theory » Topological Graph Theory » Coloring Borodin, Oleg V. ★★★ 2008-05-21
Edge list coloring conjecture opg open Graph Theory » Coloring » Edge coloring ★★★ 2008-09-25
Edge Reconstruction Conjecture opg open Graph Theory Harary, Frank ★★★ 2008-05-23
Goldberg's conjecture opg solved Graph Theory » Coloring » Edge coloring Goldberg, Mark K. ★★★ 2008-10-04
Hamiltonicity of Cayley graphs opg partial Graph Theory » Basic Graph Theory » Cycles Rapaport-Strasser, E. ★★★ 2008-09-25
Hedetniemi's Conjecture opg disproved Graph Theory » Coloring » Vertex coloring Hedetniemi, Stephen T. ★★★ 2008-05-25
Monochromatic reachability or rainbow triangles opg partial Graph Theory » Directed Graphs » Tournaments Sands, Bill; Sauer, Norbert W.; Woodrow, Robert E. ★★★ 2008-07-15
Nearly spanning regular subgraphs opg open Graph Theory » Basic Graph Theory Alon, Noga; Mubayi, Dhruv ★★★ 2008-05-22
Non-edges vs. feedback edge sets in digraphs opg partial Graph Theory » Directed Graphs Chudnovsky, Maria; Seymour, Paul D.; Sullivan, Blair ★★★ 2008-07-08
Partial List Coloring opg partial Graph Theory » Coloring » Vertex coloring Albertson, Michael O.; Grossman, Sara; Haas, Ruth ★★★ 2008-05-05
Partial List Coloring opg partial Graph Theory » Coloring » Vertex coloring Iradmusa, Moharram ★★★ 2008-05-12
Seagull problem opg partial Graph Theory » Basic Graph Theory » Minors Seymour, Paul D. ★★★ 2008-01-06
Seymour's r-graph conjecture opg solved Graph Theory » Coloring » Edge coloring Seymour, Paul D. ★★★ 2008-10-03
Total Colouring Conjecture opg partial Graph Theory » Coloring Behzad, M. ★★★ 2008-06-04
(m,n)-cycle covers opg partial Graph Theory » Basic Graph Theory » Cycles Celmins, Uldis A.; Preissmann, Myriam ★★★ 2007-03-07
3-flow conjecture opg partial Graph Theory » Coloring » Nowhere-zero flows Tutte, William T. ★★★ 2007-03-07
4-flow conjecture opg partial Graph Theory » Coloring » Nowhere-zero flows Tutte, William T. ★★★ 2007-03-07
57-regular Moore graph? opg open Graph Theory » Algebraic Graph Theory Hoffman, Alan J.; Singleton, Robert R. ★★★ 2007-03-18
Barnette's Conjecture opg partial Graph Theory » Basic Graph Theory » Cycles Barnette, David W. ★★★ 2007-06-12
Bouchet's 6-flow conjecture opg partial Graph Theory » Coloring » Nowhere-zero flows Bouchet, Andre ★★★ 2007-03-07
Chords of longest cycles opg partial Graph Theory » Basic Graph Theory » Cycles Thomassen, Carsten ★★★ 2007-11-12
Coloring and immersion opg partial Graph Theory » Coloring » Vertex coloring Abu-Khzam, Faisal N.; Langston, Michael A. ★★★ 2007-09-04
Coloring the Odd Distance Graph opg solved Graph Theory » Coloring » Vertex coloring Rosenfeld, Moshe ★★★ 2007-10-03
Consecutive non-orientable embedding obstructions opg open Graph Theory » Topological Graph Theory » Genus ★★★ 2007-03-27
Decomposing eulerian graphs opg partial Graph Theory » Basic Graph Theory » Cycles ★★★ 2007-03-07
Faithful cycle covers opg open Graph Theory » Basic Graph Theory » Cycles Seymour, Paul D. ★★★ 2007-03-07
Graceful Tree Conjecture opg partial Graph Theory » Coloring » Labeling ★★★ 2007-07-13
Grunbaum's Conjecture opg disproved Graph Theory » Topological Graph Theory » Coloring Grunbaum, Branko ★★★ 2007-04-04
Hamiltonian cycles in line graphs opg partial Graph Theory » Basic Graph Theory » Cycles Thomassen, Carsten ★★★ 2007-07-24
Hamiltonian paths and cycles in vertex transitive graphs opg partial Graph Theory » Algebraic Graph Theory Lovasz, Laszlo ★★★ 2007-03-18
Highly connected graphs with no K_n minor opg partial Graph Theory » Basic Graph Theory » Minors Thomas, Robin ★★★ 2007-03-10
Jaeger's modular orientation conjecture opg disproved Graph Theory » Coloring » Nowhere-zero flows Jaeger, Francois ★★★ 2007-03-07
Jorgensen's Conjecture opg partial Graph Theory » Basic Graph Theory » Minors Jorgensen, Leif K. ★★★ 2007-03-10
Linial-Berge path partition duality opg partial Graph Theory » Coloring Berge, Claude; Linial, Nathan ★★★ 2007-03-27
Mapping planar graphs to odd cycles opg partial Graph Theory » Coloring » Homomorphisms Jaeger, Francois ★★★ 2007-06-24
Pebbling a cartesian product opg partial Graph Theory Graham, Ronald L. ★★★ 2007-09-24
Pentagon problem opg open Graph Theory » Coloring » Homomorphisms Nesetril, Jaroslav ★★★ 2007-03-24
Petersen coloring conjecture opg partial Graph Theory » Coloring » Edge coloring Jaeger, Francois ★★★ 2007-03-07
r-regular graphs are not uniquely hamiltonian. opg partial Graph Theory » Basic Graph Theory » Cycles Sheehan, John ★★★ 2007-07-24
Ramsey properties of Cayley graphs opg partial Graph Theory » Algebraic Graph Theory Alon, Noga ★★★ 2007-06-10
Reed's omega, delta, and chi conjecture opg partial Graph Theory » Coloring » Vertex coloring Reed, Bruce A. ★★★ 2007-05-22
Ryser's conjecture opg partial Graph Theory » Hypergraphs Ryser, Herbert J. ★★★ 2007-03-19
Seymour's Second Neighbourhood Conjecture opg partial Graph Theory » Directed Graphs Seymour, Paul D. ★★★ 2007-10-09
Seymour's self-minor conjecture opg partial Graph Theory » Infinite Graphs Seymour, Paul D. ★★★ 2007-05-22
Strong colorability opg partial Graph Theory » Coloring » Vertex coloring Aharoni, Ron; Alon, Noga; Haxell, Penny E. ★★★ 2007-03-27
Strong matchings and covers opg disproved Graph Theory » Infinite Graphs Aharoni, Ron ★★★ 2007-10-23
The circular embedding conjecture opg partial Graph Theory » Basic Graph Theory » Cycles Haggard, Gary ★★★ 2007-03-07
The Crossing Number of the Complete Bipartite Graph opg partial Graph Theory » Topological Graph Theory » Crossing numbers Turan, Paul ★★★ 2007-05-11
The Crossing Number of the Complete Graph opg partial Graph Theory » Topological Graph Theory » Crossing numbers ★★★ 2007-05-11
The Erdös-Hajnal Conjecture EP #61 opg partial Graph Theory » Extremal Graph Theory Erdos, Paul; Hajnal, Andras ★★★ 2007-03-18
Triangle free strongly regular graphs opg open Graph Theory » Algebraic Graph Theory ★★★ 2007-05-28
Unfriendly partitions opg partial Graph Theory » Infinite Graphs Cowan, Robert H.; Emerson, William R. ★★★ 2007-10-22
Unions of triangle free graphs opg open Graph Theory » Infinite Graphs Erdos, Paul; Hajnal, Andras ★★★ 2007-06-04
Universal highly arc transitive digraphs opg solved Graph Theory » Infinite Graphs Cameron, Peter J.; Praeger, Cheryl E.; Wormald, Nicholas C. ★★★ 2007-10-21
Universal point sets for planar graphs opg partial Graph Theory » Topological Graph Theory » Drawings Mohar, Bojan ★★★ 2007-05-22
Woodall's Conjecture opg partial Graph Theory » Directed Graphs Woodall, Douglas R. ★★★ 2007-04-05
Chromatic number of $\frac{3}{3}$-power of graph opg partial Graph Theory ★★ 2023-04-20
Circular flow number of regular class 1 graphs opg disproved Graph Theory » Coloring » Nowhere-zero flows Steffen, Eckhard ★★ 2015-08-05
Circular flow numbers of $r$-graphs opg disproved Graph Theory Steffen, Eckhard ★★ 2015-08-06
Cycles in Graphs of Large Chromatic Number opg partial Graph Theory » Coloring » Vertex coloring Brewster, Richard C.; McGuinness, Sean; Moore, Benjamin; Noel, Jonathan A. ★★ 2015-09-20
Chromatic Number of Common Graphs opg solved Graph Theory Hatami, H; Hladký, J.; Kráľ, D.; Norine, S.; Razborov, A. ★★ 2014-08-15
Forcing a 2-regular minor opg solved Graph Theory » Basic Graph Theory » Minors Reed, Bruce A.; Wood, David R. ★★ 2014-03-16
Fractional Hadwiger opg open Graph Theory Harvey, Daniel J.; Reed, Bruce A.; Seymour, Paul D.; Wood, David R. ★★ 2014-03-16
List Colourings of Complete Multipartite Graphs with 2 Big Parts opg partial Graph Theory » Coloring » Vertex coloring Allagan, Julian ★★ 2014-04-12
List Hadwiger Conjecture opg partial Graph Theory » Coloring » Vertex coloring Kawarabayashi, Ken-ichi; Mohar, Bojan ★★ 2014-07-07
2-colouring a graph without a monochromatic maximum clique opg partial Graph Theory » Coloring » Vertex coloring Hoang, Chinh T.; McDiarmid, Colin ★★ 2013-08-25
4-connected graphs are not uniquely hamiltonian opg open Graph Theory » Basic Graph Theory » Cycles Fleischner, Herbert ★★ 2013-03-11
Almost all non-Hamiltonian 3-regular graphs are 1-connected opg open Graph Theory » Basic Graph Theory Haythorpe, Michael ★★ 2013-08-23
Antidirected trees in digraphs opg partial Graph Theory » Directed Graphs Addario-Berry, Louigi; Havet, Frédéric; Linhares Sales, Claudia; Reed, Bruce A.; Thomassé, Stéphan ★★ 2013-02-26
Arc-disjoint directed cycles in regular directed graphs opg open Graph Theory » Directed Graphs Alon, Noga; McDiarmid, Colin; Molloy, Michael ★★ 2013-05-17
Arc-disjoint out-branching and in-branching opg partial Graph Theory » Directed Graphs Thomassen, Carsten ★★ 2013-03-02
Arc-disjoint strongly connected spanning subdigraphs opg partial Graph Theory Bang-Jensen, Joergen; Yeo, Anders ★★ 2013-03-02
Bounding the on-line choice number in terms of the choice number opg solved Graph Theory » Coloring » Vertex coloring Zhu, Xuding ★★ 2013-04-11
Choice Number of k-Chromatic Graphs of Bounded Order opg partial Graph Theory » Coloring » Vertex coloring Noel, Jonathan A. ★★ 2013-02-02
Choosability of Graph Powers opg open Graph Theory » Coloring » Vertex coloring Noel, Jonathan A. ★★ 2013-07-13
Coloring the union of degenerate graphs opg open Graph Theory » Coloring Tarsi, Michael ★★ 2013-03-03
Colouring the square of a planar graph opg partial Graph Theory » Coloring » Vertex coloring Wegner ★★ 2013-03-13
Complexity of the H-factor problem. opg partial Graph Theory » Extremal Graph Theory Kühn, Daniella; Osthus, Deryk ★★ 2013-03-05
Cyclic spanning subdigraph with small cyclomatic number opg open Graph Theory » Directed Graphs Bondy, J. Adrian ★★ 2013-06-02
Decomposing an eulerian graph into cycles with no two consecutives edges on a prescribed eulerian tour. opg open Graph Theory » Basic Graph Theory » Cycles Sabidussi, Gert ★★ 2013-03-04
Decomposing an eulerian graph into cycles. opg partial Graph Theory » Basic Graph Theory » Cycles Hajós, G. ★★ 2013-03-04
Decomposing k-arc-strong tournament into k spanning strong digraphs opg partial Graph Theory » Directed Graphs » Tournaments Bang-Jensen, Joergen; Yeo, Anders ★★ 2013-03-15
Do any three longest paths in a connected graph have a vertex in common? opg partial Graph Theory Gallai, Tibor ★★ 2013-03-03
Earth-Moon Problem opg partial Graph Theory » Coloring » Vertex coloring Ringel, G. ★★ 2013-03-06
Edge-disjoint Hamilton cycles in highly strongly connected tournaments. opg solved Graph Theory » Directed Graphs » Tournaments Thomassen, Carsten ★★ 2013-03-08
Erdős-Posa property for long directed cycles opg solved Graph Theory » Directed Graphs Havet, Frédéric; Maia, Ana Karolinna ★★ 2013-06-25
Every 4-connected toroidal graph has a Hamilton cycle opg open Graph Theory » Topological Graph Theory Grunbaum, Branko; Nash-Williams, Crispin, St. J. A. ★★ 2013-03-07
Every prism over a 3-connected planar graph is hamiltonian. opg disproved Graph Theory » Basic Graph Theory » Cycles Kaiser, Tomás; Král, Daniel; Rosenfeld, Moshe; Ryjácek, Zdenek; Voss, Heinz-Jürgen ★★ 2013-03-11
Hamilton cycle in small d-diregular graphs opg partial Graph Theory » Directed Graphs Jackson, Bill ★★ 2013-03-08
Hamilton decomposition of prisms over 3-connected cubic planar graphs opg partial Graph Theory » Basic Graph Theory » Cycles Alspach, Brian; Rosenfeld, Moshe ★★ 2013-03-12
Imbalance conjecture opg partial Graph Theory Kozerenko, Sergiy ★★ 2013-09-24
Kriesell's Conjecture opg partial Graph Theory » Basic Graph Theory » Connectivity Kriesell, Matthias ★★ 2013-08-25
Large acyclic induced subdigraph in a planar oriented graph. opg partial Graph Theory » Directed Graphs Harutyunyan, Ararat ★★ 2013-06-25
Large induced forest in a planar graph. opg partial Graph Theory » Topological Graph Theory Abertson, Michael O.; Berman, David M. ★★ 2013-03-04
List chromatic number and maximum degree of bipartite graphs opg partial Graph Theory » Coloring » Vertex coloring Alon, Noga ★★ 2013-03-12
List Total Colouring Conjecture opg open Graph Theory » Coloring Borodin, Oleg V.; Kostochka, Alexandr V.; Woodall, Douglas R. ★★ 2013-08-29
Lovász Path Removal Conjecture opg open Graph Theory Lovasz, Laszlo ★★ 2013-03-04
Minimum number of arc-disjoint transitive subtournaments of order 3 in a tournament opg open Graph Theory Yuster, Raphael ★★ 2013-05-21
Odd-cycle transversal in triangle-free graphs opg partial Graph Theory » Extremal Graph Theory Erdos, Paul; Faudree, Ralph; Pach, János; Spencer, Joel ★★ 2013-03-06
Partition of a cubic 3-connected graphs into paths of length 2. opg open Graph Theory » Basic Graph Theory » Paths Kelmans, Alexander K. ★★ 2013-03-04
Partitionning a tournament into k-strongly connected subtournaments. opg solved Graph Theory » Directed Graphs » Tournaments Thomassen, Carsten ★★ 2013-03-15
PTAS for feedback arc set in tournaments opg solved Graph Theory » Graph Algorithms Ailon, Nir; Alon, Noga ★★ 2013-03-15
Signing a graph to have small magnitude eigenvalues opg partial Graph Theory Bilu, Yonatan; Linial, Nathan ★★ 2013-03-24
Simultaneous partition of hypergraphs opg open Graph Theory » Hypergraphs Kühn, Daniella; Osthus, Deryk ★★ 2013-03-06
Stable set meeting all longest directed paths. opg open Graph Theory Laborde, Jean-Marie; Payan, Charles; Xuong N.H. ★★ 2013-03-01
Strong edge colouring conjecture opg partial Graph Theory » Coloring » Edge coloring Erdos, Paul; Nesetril, Jaroslav ★★ 2013-03-01
Subdivision of a transitive tournament in digraphs with large outdegree. opg partial Graph Theory » Directed Graphs Mader, W. ★★ 2013-03-04
Subgraph of large average degree and large girth. opg partial Graph Theory » Basic Graph Theory Thomassen, Carsten ★★ 2013-03-05
Switching reconstruction conjecture opg open Graph Theory Stanley, Richard P. ★★ 2013-03-07
Switching reconstruction of digraphs opg partial Graph Theory Bondy, J. Adrian; Mercier, Fabien ★★ 2013-03-07
Triangle-packing vs triangle edge-transversal. opg partial Graph Theory » Extremal Graph Theory Tuza, Zsolt ★★ 2013-03-06
Turán number of a finite family. opg partial Graph Theory Erdos, Paul; Simonovits, Miklos ★★ 2013-03-05
Turán's problem for hypergraphs opg open Graph Theory » Hypergraphs Turan, Paul ★★ 2013-03-12
Weighted colouring of hexagonal graphs. opg partial Graph Theory » Coloring » Vertex coloring McDiarmid, Colin; Reed, Bruce A. ★★ 2013-03-13
Chromatic number of random lifts of complete graphs opg partial Graph Theory » Probabilistic Graph Theory Amit, Linial, Matousek ★★ 2012-09-03
Forcing a $K_6$-minor opg partial Graph Theory » Basic Graph Theory » Minors Barát ,János; Joret, Gwenaël; Wood, David R. ★★ 2012-01-16
Minimal graphs with a prescribed number of spanning trees opg partial Graph Theory Azarija, Jernej; Skrekovski, Riste ★★ 2012-04-22
The Borodin-Kostochka Conjecture opg partial Graph Theory Borodin, Oleg V.; Kostochka, Alexandr V. ★★ 2012-09-10
Extremal problem on the number of tree endomorphism opg solved Graph Theory » Extremal Graph Theory Zhicong Lin ★★ 2011-03-01
Good Edge Labelings opg partial Graph Theory » Coloring » Labeling Araújo, Julio; Cohen, Nathann; Giroire, Frédéric; Havet, Frédéric ★★ 2011-06-30
Matching cut and girth opg partial Graph Theory ★★ 2011-11-30
Algorithm for graph homomorphisms opg partial Graph Theory » Coloring » Homomorphisms Fomin, Fedor V.; Heggernes, Pinar; Kratsch, Dieter ★★ 2010-07-08
Approximation ratio for k-outerplanar graphs opg partial Graph Theory Bentz, Cedric ★★ 2010-04-18
Approximation Ratio for Maximum Edge Disjoint Paths problem opg partial Graph Theory Bentz, Cedric ★★ 2010-04-18
Exact colorings of graphs opg partial Graph Theory Erickson, Martin ★★ 2010-06-29
Finding k-edge-outerplanar graph embeddings opg open Graph Theory Bentz, Cedric ★★ 2010-04-18
Odd cycles and low oddness opg open Graph Theory ★★ 2010-01-15
Star chromatic index of complete graphs opg open Graph Theory Dvorak, Zdenek; Mohar, Bojan; Samal, Robert ★★ 2010-11-16
Star chromatic index of cubic graphs opg partial Graph Theory Dvorak, Zdenek; Mohar, Bojan; Samal, Robert ★★ 2010-11-16
3-Colourability of Arrangements of Great Circles opg partial Graph Theory » Topological Graph Theory » Coloring Felsner, Stefan; Hurtado, Ferran; Noy, Marc; Streinu, Ileana ★★ 2009-01-19
A gold-grabbing game opg partial Graph Theory » Graph Algorithms Rosenfeld, Moshe ★★ 2009-10-02
Are vertex minor closed classes chi-bounded? opg solved Graph Theory » Coloring » Vertex coloring Geelen, Jim ★★ 2009-05-16
Asymptotic Distribution of Form of Polyhedra opg open Graph Theory » Basic Graph Theory Rüdinger, Andreas ★★ 2009-05-09
Book Thickness of Subdivisions opg disproved Graph Theory Blankenship, Robin; Oporowski, Bogdan ★★ 2009-01-19
Bounding the chromatic number of triangle-free graphs with fixed maximum degree opg open Graph Theory » Coloring » Vertex coloring Kostochka, Alexandr V.; Reed, Bruce A. ★★ 2009-04-17
Does the chromatic symmetric function distinguish between trees? opg partial Graph Theory » Algebraic Graph Theory Stanley, Richard P. ★★ 2009-02-25
Domination in cubic graphs opg open Graph Theory » Basic Graph Theory Reed, Bruce A. ★★ 2009-08-19
Domination in plane triangulations opg partial Graph Theory » Topological Graph Theory Matheson, Lesley R.; Tarjan, Robert E. ★★ 2009-05-04
Double-critical graph conjecture opg partial Graph Theory » Coloring » Vertex coloring Erdos, Paul; Lovasz, Laszlo ★★ 2009-01-18
Friendly partitions opg partial Graph Theory » Basic Graph Theory DeVos, Matt ★★ 2009-11-08
Number of Cliques in Minor-Closed Classes opg solved Graph Theory Wood, David R. ★★ 2009-10-12
4-regular 4-chromatic graphs of high girth opg open Graph Theory » Coloring Grunbaum, Branko ★★ 2008-06-18
Circular colouring the orthogonality graph opg open Graph Theory » Coloring » Vertex coloring DeVos, Matt; Ghebleh, Mohammad; Goddyn, Luis A.; Mohar, Bojan; Naserasr, Reza ★★ 2008-09-23
Coloring random subgraphs opg partial Graph Theory » Probabilistic Graph Theory Bukh, Boris ★★ 2008-06-18
Complete bipartite subgraphs of perfect graphs opg open Graph Theory » Basic Graph Theory Fox, Jacob ★★ 2008-06-17
Counting 3-colorings of the hex lattice opg open Graph Theory » Coloring » Vertex coloring Thomassen, Carsten ★★ 2008-07-05
Crossing sequences opg partial Graph Theory » Topological Graph Theory » Crossing numbers Archdeacon, Dan; Bonnington, C. Paul; Siran, Jozef ★★ 2008-07-30
Frankl's union-closed sets conjecture opg partial Graph Theory » Hypergraphs Frankl, Peter ★★ 2008-09-25
Negative association in uniform forests opg partial Graph Theory » Probabilistic Graph Theory Pemantle, Robin ★★ 2008-06-30
Random stable roommates opg partial Graph Theory » Basic Graph Theory » Matchings Mertens, Stephan ★★ 2008-02-26
5-local-tensions opg open Graph Theory » Topological Graph Theory » Coloring DeVos, Matt ★★ 2007-06-22
A generalization of Vizing's Theorem? opg open Graph Theory » Coloring » Edge coloring Rosenfeld, Moshe ★★ 2007-04-11
A homomorphism problem for flows opg partial Graph Theory » Coloring » Nowhere-zero flows DeVos, Matt ★★ 2007-03-07
Acyclic edge-colouring opg partial Graph Theory » Coloring » Edge coloring Fiamcik, Jozef ★★ 2007-03-07
Antichains in the cycle continuous order opg solved Graph Theory » Coloring » Nowhere-zero flows DeVos, Matt ★★ 2007-05-12
Circular coloring triangle-free subcubic planar graphs opg open Graph Theory » Coloring » Vertex coloring Ghebleh, Mohammad; Zhu, Xuding ★★ 2007-06-20
Cores of Cayley graphs opg partial Graph Theory » Coloring » Homomorphisms Samal, Robert ★★ 2007-03-06
Drawing disconnected graphs on surfaces opg partial Graph Theory » Topological Graph Theory » Crossing numbers DeVos, Matt; Mohar, Bojan; Samal, Robert ★★ 2007-05-12
Geodesic cycles and Tutte's Theorem opg open Graph Theory » Basic Graph Theory » Cycles Georgakopoulos, Agelos; Sprüssel, Philipp ★★ 2007-08-04
Graham's conjecture on tree reconstruction opg partial Graph Theory » Basic Graph Theory Graham, Ronald L. ★★ 2007-03-18
Half-integral flow polynomial values opg open Graph Theory » Algebraic Graph Theory Mohar, Bojan ★★ 2007-05-31
Hamiltonian cycles in line graphs of infinite graphs opg partial Graph Theory » Infinite Graphs Georgakopoulos, Agelos ★★ 2007-07-24
Hamiltonian cycles in powers of infinite graphs opg open Graph Theory » Infinite Graphs Georgakopoulos, Agelos ★★ 2007-07-24
Highly arc transitive two ended digraphs opg disproved Graph Theory » Infinite Graphs Cameron, Peter J.; Praeger, Cheryl E.; Wormald, Nicholas C. ★★ 2007-10-29
Infinite uniquely hamiltonian graphs opg partial Graph Theory » Infinite Graphs Mohar, Bojan ★★ 2007-07-24
Jones' conjecture opg partial Graph Theory » Basic Graph Theory » Cycles Kloks, Ton; Lee, Chuan-Min; Liu, Jiping ★★ 2007-10-09
Laplacian Degrees of a Graph opg solved Graph Theory » Algebraic Graph Theory Guo, Ji-Ming ★★ 2007-06-22
Linear Hypergraphs with Dimension 3 opg open Graph Theory » Topological Graph Theory » Drawings de Fraysseix, Hubert; Ossona de Mendez, Patrice; Rosenstiehl, Pierre ★★ 2007-09-26
List colorings of edge-critical graphs opg open Graph Theory » Coloring » Edge coloring Mohar, Bojan ★★ 2007-06-12
Matchings extend to Hamiltonian cycles in hypercubes opg partial Graph Theory » Basic Graph Theory » Matchings Ruskey, Frank; Savage, Carla ★★ 2007-09-28
Oriented chromatic number of planar graphs opg partial Graph Theory » Coloring » Vertex coloring ★★ 2007-08-04
Packing T-joins opg partial Graph Theory » Coloring » Edge coloring DeVos, Matt ★★ 2007-03-07
Partitioning edge-connectivity opg open Graph Theory » Basic Graph Theory » Connectivity DeVos, Matt ★★ 2007-03-07
Real roots of the flow polynomial opg disproved Graph Theory » Coloring » Nowhere-zero flows Welsh, Dominic J. A. ★★ 2007-03-07
The Bermond-Thomassen Conjecture opg partial Graph Theory » Directed Graphs Bermond, Jean-Claude; Thomassen, Carsten ★★ 2007-10-01
The Crossing Number of the Hypercube opg partial Graph Theory » Topological Graph Theory » Crossing numbers Erdos, Paul; Guy, Richard K. ★★ 2007-05-11
The intersection of two perfect matchings opg partial Graph Theory » Basic Graph Theory » Matchings Macajova, Edita; Skoviera, Martin ★★ 2007-08-30
The three 4-flows conjecture opg open Graph Theory » Coloring » Nowhere-zero flows DeVos, Matt ★★ 2007-03-07
The Two Color Conjecture opg partial Graph Theory » Directed Graphs Neumann-Lara, Victor ★★ 2007-03-26
Three-chromatic (0,2)-graphs opg open Graph Theory » Coloring Payan, Charles ★★ 2007-09-07
Unit vector flows opg partial Graph Theory » Coloring » Nowhere-zero flows Jain, Kamal ★★ 2007-03-07
Universal Steiner triple systems opg partial Graph Theory » Coloring » Edge coloring Grannell, Mike; Griggs, Terry; Knor, Martin; Skoviera, Martin ★★ 2007-10-05
Weak pentagon problem opg partial Graph Theory » Coloring » Homomorphisms Samal, Robert ★★ 2007-07-13
What is the smallest number of disjoint spanning trees made a graph Hamiltonian opg unclear Graph Theory » Extremal Graph Theory Goldengorin ★★ 2007-09-10
¿Are critical k-forests tight? opg disproved Graph Theory » Hypergraphs Strausz, Ricardo ★★ 2007-09-01
Weak saturation of the cube in the clique opg open Graph Theory » Extremal Graph Theory Morrison, Natasha; Noel, Jonathan A. ★ 2016-04-06
Melnikov's valency-variety problem opg open Graph Theory » Coloring » Vertex coloring Melnikov, L. S. ★ 2013-03-03
Circular choosability of planar graphs opg open Graph Theory » Coloring » Homomorphisms Mohar, Bojan ★ 2012-08-23
Mixing Circular Colourings opg partial Graph Theory » Coloring » Vertex coloring Brewster, Richard C.; Noel, Jonathan A. ★ 2012-09-22
Covering powers of cycles with equivalence subgraphs opg open Graph Theory ★ 2011-07-07
Obstacle number of planar graphs opg partial Graph Theory Alpert, Hanna; Koch, Christina; Laison, Joshua D. ★ 2011-11-23
End-Devouring Rays opg solved Graph Theory » Infinite Graphs Georgakopoulos, Agelos ★ 2008-02-03
What is the largest graph of positive curvature? opg solved Graph Theory » Topological Graph Theory » Planar graphs DeVos, Matt; Mohar, Bojan ★ 2007-03-10
3-colouring diameter-2 graphs quasi-polynomial time arxiv open Carla Groenland; Hidde Koerts; Sophie Spirkl 2026-01-19
4/3 constant in arithmetic progression packing arxiv open Noga Alon; Michał Dębski; Jarosław Grytczuk; Jakub Przybyło 2026-03-03
5-Flow Reconfiguration Connectivity arxiv open Louis Esperet; Kevin Hendrey; Aurélie Lagoutte; Margaux Marseloo; Sergey Norin; Raphael Steiner 2026-05-04
Anticoncentration bound for random spanning trees arxiv open Veronica Bitonti; Lukas Michel; Alex Scott 2026-03-18
AP packing asymptotics for k near √n arxiv open Noga Alon; Michał Dębski; Jarosław Grytczuk; Jakub Przybyło 2026-03-03
Arithmetic triangle removal lemma with restricted differences arxiv open David Conlon; Jacob Fox; Huy Tuan Pham 2026-05-13
Asymptotic regimes of Mₖ(n) packing progressions arxiv open Noga Alon; Michał Dębski; Jarosław Grytczuk; Jakub Przybyło 2026-03-03
Bounded domination-to-2-independence ratio characterization arxiv open Marthe Bonamy; Zdeněk Dvořák; Lukas Michel; David Mikšaník 2026-01-21
Circular drawing characterization via forbidden type arxiv open Eli Berger; Daniel Carter; Paul Seymour 2026-01-19
Circumference equivalence vertex transitive digraphs arxiv open Matija Bucić; Kevin Hendrey; Bojan Mohar; Raphael Steiner; Liana Yepremyan 2026-02-18
Coloring triangle-free degenerate graphs via LLL arxiv open Domagoj Bradač; Jacob Fox; Raphael Steiner; Benny Sudakov; Shengtong Zhang 2026-01-21
Colour-balanced error bounds for k≥3 spanning forests arxiv open Emma Hogan; Alex Scott; Dmitry Tsarev 2026-04-10
Colour-balanced Hamilton cycle bounds in complete graphs arxiv open Emma Hogan; Alex Scott; Dmitry Tsarev 2026-04-10
Complexity of C-FAS for paths and matchings arxiv open Pierre Aboulker; Guillaume Aubian; Raul Lopes 2026-01-23
Constant bound on colour-balanced perfect matching imbalance arxiv open Emma Hogan; Alex Scott; Dmitry Tsarev 2026-04-10
Crossing-free path cover lower bound cn arxiv open Adrian Dumitrescu; János Pach; Morteza Saghafian; Alex Scott 2026-01-10
Cycle lengths in vertex-transitive digraphs arxiv open Matija Bucić; Kevin Hendrey; Bojan Mohar; Raphael Steiner; Liana Yepremyan 2026-02-18
Density bound for S-difference-free sets arxiv open David Conlon; Jacob Fox; Huy Tuan Pham 2026-05-13
Directed tree-width linear constant in regular digraphs arxiv open Raphael Steiner 2026-04-26
Exponential order of K_r-free degenerate χ=d+1 graphs arxiv open Domagoj Bradač; Jacob Fox; Raphael Steiner; Benny Sudakov; Shengtong Zhang 2026-01-21
FPT approximation for tournament forest-ordering arxiv open Pierre Aboulker; Guillaume Aubian; Raul Lopes 2026-01-23
Fractional chromatic number of K_r-free d-degenerate graphs arxiv open Domagoj Bradač; Jacob Fox; Raphael Steiner; Benny Sudakov; Shengtong Zhang 2026-01-21
Limit of c_r/r in regular digraphs arxiv open Raphael Steiner 2026-04-26
Linear perimeter gap in vertex-transitive digraphs arxiv open Matija Bucić; Kevin Hendrey; Bojan Mohar; Raphael Steiner; Liana Yepremyan 2026-02-18
Longest cycles intersection in vertex transitive digraphs arxiv open Matija Bucić; Kevin Hendrey; Bojan Mohar; Raphael Steiner; Liana Yepremyan 2026-02-18
Minimum zig-zag path cover of complete geometric graphs arxiv open Adrian Dumitrescu; János Pach; Morteza Saghafian; Alex Scott 2026-01-10
Non-isomorphic spanning trees count lower bound arxiv open Veronica Bitonti; Lukas Michel; Alex Scott 2026-03-18
Non-transitive tournament color-avoiding path bound arxiv open Jacob Fox; Benny Sudakov; Yuval Wigderson 2026-01-21
Pivot Gray code for all spanning trees arxiv open Marthe Bonamy; Michael Hoffmann; Clément Legrand-Duchesne; Günter Rote 2026-03-30
Polynomial Nikiforov universality for graphs arxiv open Tung Nguyen; Alex Scott; Paul Seymour 2026-04-18
Prime AP packing asymptotic n³/ln n arxiv open Noga Alon; Michał Dębski; Jarosław Grytczuk; Jakub Przybyło 2026-03-03
s-convex Tverberg partition number arxiv partial Noga Alon; Shakhar Smorodinsky 2026-02-27
Sub-exponential vertex threshold for degenerate coloring arxiv open Domagoj Bradač; Jacob Fox; Raphael Steiner; Benny Sudakov; Shengtong Zhang 2026-01-21
Sub-linear χ_f for K_r-free degenerate graphs arxiv open Domagoj Bradač; Jacob Fox; Raphael Steiner; Benny Sudakov; Shengtong Zhang 2026-01-21
Sublinear cop number vs treedepth arxiv open Prosenjit Bose; Louis Esperet; Jędrzej Hodor; Gwenaël Joret; Piotr Micek; Clément Rambaud 2026-02-07
Superlinear monotone path cover for dense point sets arxiv open Adrian Dumitrescu; János Pach; Morteza Saghafian; Alex Scott 2026-01-10
Trivial lower bound tight for AP packing arxiv open Noga Alon; Michał Dębski; Jarosław Grytczuk; Jakub Przybyło 2026-03-03
Unavoidable induced subgraphs of large treewidth arxiv disproved Maria Chudnovsky; Sepehr Hajebi; Sophie Spirkl 2026-02-18
γ(G) ≤ h(α₂(G)) graph class characterization arxiv open Marthe Bonamy; Zdeněk Dvořák; Lukas Michel; David Mikšaník 2026-01-21
χ = χ_ℓ = χ_DP threshold for ω = Δ−1 arxiv open Zdeněk Dvořák; Ross J. Kang; David Mikšaník 2026-03-15
χ-boundedness of sun-free graphs arxiv open Sepehr Hajebi; Sophie Spirkl 2026-03-08
ℤₖ-connectivity implying ℤ_k-flow reconfiguration arxiv open Louis Esperet; Kevin Hendrey; Aurélie Lagoutte; Margaux Marseloo; Sergey Norin; Raphael Steiner 2026-05-04
√k bound for bipartite matching discrepancy arxiv open Emma Hogan; Alex Scott; Dmitry Tsarev 2026-04-10
4-color bound for cubic 2-homogeneous coloring arxiv open János Barát; Zdeněk Dvořák; Penny Haxell; František Kardoš; Borut Lužar; Alfréd Onderko; Jozef Rajník; Roman Soták; Nikolay Ulyanov 2025-11-04
4-colorability of cycles union K₄s arxiv open János Barát; Zdeněk Dvořák; Penny Haxell; František Kardoš; Borut Lužar; Alfréd Onderko; Jozef Rajník; Roman Soták; Nikolay Ulyanov 2025-11-04
4-colorability with one crossing, degree ≥ 5 arxiv open Zdeněk Dvořák; Bernard Lidický; Bojan Mohar 2025-04-14
6-regular critical graph without critical edge arxiv open Ema Skottova; Raphael Steiner 2025-08-12
Active path characterisation in complete graphs arxiv open Zdeněk Dvořák; Beatriz Martins; Stéphan Thomassé; Nicolas Trotignon 2025-10-10
Active vertices in optimal lollipop cycle arxiv open Zdeněk Dvořák; Beatriz Martins; Stéphan Thomassé; Nicolas Trotignon 2025-10-10
Almost-ℤ₂²- and ℤ₄-connectedness of bicritical snarks arxiv open János Barát; Zdeněk Dvořák; Penny Haxell; František Kardoš; Borut Lužar; Alfréd Onderko; Jozef Rajník; Roman Soták; Nikolay Ulyanov 2025-11-04
Arc-reversal induced saturation in tournaments arxiv open Marthe Bonamy; Carla Groenland; Tom Johnston; Natasha Morrison; Alex Scott 2025-09-01
Avoidable orientations of C₄ arxiv open Micha Christoph; Barnabás Janzer; Kalina Petrova; Raphael Steiner 2025-10-13
Characterisation of maximum circular sorting permutations arxiv disproved Ron M. Adin; Noga Alon; Yuval Roichman 2025-08-06
Characterization of bounded γ/ρ graph classes arxiv partial Marthe Bonamy; Mónika Csikós; Anna Gujgiczer; Yelena Yuditsky 2025-03-07
Characterization of Eulerian-avoidable digraphs arxiv open Micha Christoph; Barnabás Janzer; Kalina Petrova; Raphael Steiner 2025-10-13
Clique Ramsey minimizer K_t-Ramsey graphs arxiv partial Jacob Fox; Jonathan Tidor; Shengtong Zhang 2025-10-01
Coarse Menger conjecture for bounded genus arxiv solved Tung Nguyen; Alex Scott; Paul Seymour 2025-09-10
Coarse Menger for surface-embedded graphs arxiv partial Tung Nguyen; Alex Scott; Paul Seymour 2025-09-08
Coarse Menger separation with distance 2 arxiv partial Tung Nguyen; Alex Scott; Paul Seymour 2025-08-20
Complexity gap between induced disjoint paths variants arxiv open Pierre Aboulker; Édouard Bonnet; Timothé Picavet; Nicolas Trotignon 2025-02-07
Constant domination-packing ratio per graph class arxiv partial Marthe Bonamy; Mónika Csikós; Anna Gujgiczer; Yelena Yuditsky 2025-03-07
Counterexamples in d-regular edge-colorable graphs arxiv solved Alexander Clow; Penny Haxell; Bojan Mohar 2025-06-10
Cycle orientations in high chromatic high out-degree digraphs arxiv solved Hidde Koerts; Benjamin Moore; Sophie Spirkl 2025-03-25
C₄ Eulerian-avoidability in orientations arxiv open Micha Christoph; Barnabás Janzer; Kalina Petrova; Raphael Steiner 2025-10-13
Degree-four vertex in 5-critical crossing graphs arxiv open Zdeněk Dvořák; Bernard Lidický; Bojan Mohar 2025-04-14
Degree-four vertex in non-4-colorable C₀ graphs arxiv open Zdeněk Dvořák; Bernard Lidický; Bojan Mohar 2025-04-14
Diamond generation of bichromatic-forbidding 4-candidates arxiv open Zdeněk Dvořák; Bernard Lidický; Bojan Mohar 2025-04-14
Digraph H-subgraph via χ and out-degree arxiv open Hidde Koerts; Benjamin Moore; Sophie Spirkl 2025-03-25
Directed chromatic threshold for digraph subgraphs arxiv open Hidde Koerts; Benjamin Moore; Sophie Spirkl 2025-03-25
Disconnectedness of H-free graphs adjacency structure arxiv open Marthe Bonamy; Carla Groenland; Tom Johnston; Natasha Morrison; Alex Scott 2025-09-01
Dom-Enum in co-bipartite H-free incomparability graphs arxiv open Marthe Bonamy; Oscar Defrain; Piotr Micek; Lhouari Nourine 2025-11-26
Dom-Enum polynomial in Sₜ-free incomparability graphs arxiv open Marthe Bonamy; Oscar Defrain; Piotr Micek; Lhouari Nourine 2025-11-26
Edge-colored induced saturation in infinite clique arxiv open Marthe Bonamy; Carla Groenland; Tom Johnston; Natasha Morrison; Alex Scott 2025-09-01
Erdős–Pósa for anti-complete (X,Y)-paths arxiv open Robert Hickingbotham; Gwenaël Joret 2025-12-19
Expected faces in G(n,p) random embedding logarithmic arxiv open Jesse Campion Loth; Kevin Halasz; Tomáš Masařík; Bojan Mohar; Robert Šámal 2025-04-09
Expected faces logarithmic for all G(n,p) arxiv open Jesse Campion Loth; Kevin Halasz; Tomáš Masařík; Bojan Mohar; Robert Šámal 2025-04-09
Exponential bound on optimal tea-sharing sequence length arxiv open J. Pascal Gollin; Kevin Hendrey; Hao Huang; Tony Huynh; Bojan Mohar; Sang-il Oum; Ningyuan Yang; Wei-Hsuan Yu; Xuding Zhu 2025-09-22
Finite exceptions to 2-homogeneous cubic coloring arxiv open János Barát; Zdeněk Dvořák; Penny Haxell; František Kardoš; Borut Lužar; Alfréd Onderko; Jozef Rajník; Roman Soták; Nikolay Ulyanov 2025-11-04
Fractional 19/7-colorability of subcubic triangle-free graphs arxiv open Zdeněk Dvořák; Bernard Lidický; Luke Postle 2025-03-28
Generic d-norm distinct distances lower bound arxiv open Noga Alon; Rom Pinchasi 2025-11-07
Georgakopoulos–Papasoglu conjecture for trees and planar graphs arxiv open Tung Nguyen; Alex Scott; Paul Seymour 2025-09-13
Giant component threshold in hypercube percolation arxiv open Paul Balister; Tom Johnston; Michael Savery; Alex Scott 2025-06-23
Height function characterizing non-avoidable digraphs arxiv open Micha Christoph; Barnabás Janzer; Kalina Petrova; Raphael Steiner 2025-10-13
Induced C_{2t}-saturation edge-addition existence arxiv open Xinyue Fan; Sahab Hajebi; Sepehr Hajebi; Sophie Spirkl 2025-06-02
Induced saturation for infinite k-uniform hypergraphs arxiv open Marthe Bonamy; Carla Groenland; Tom Johnston; Natasha Morrison; Alex Scott 2025-09-01
Induced-saturated infinite tournament existence arxiv open Marthe Bonamy; Carla Groenland; Tom Johnston; Natasha Morrison; Alex Scott 2025-09-01
Infinite 3-edge-colourable edge-transitive cubic graphs arxiv solved Alexander Clow; Penny Haxell; Bojan Mohar 2025-06-10
Infinite family with no finite induced-saturated graphs arxiv open Marthe Bonamy; Carla Groenland; Tom Johnston; Natasha Morrison; Alex Scott 2025-09-01
Intersectionwise χ-guarding class characterization arxiv open Aristotelis Chaniotis; Hidde Koerts; Sophie Spirkl 2025-03-31
Isometric quasi-isometry in bounded tree-width arxiv partial Tung Nguyen; Alex Scott; Paul Seymour 2025-09-05
Kempe equivalence of colorings in Kₜ-minor-free graphs arxiv open Marthe Bonamy; Marc Heinrich; Clément Legrand-Duchesne; Jonathan Narboni 2025-03-13
Linear chords in minimum-degree-3 cycles arxiv partial Zdeněk Dvořák; Beatriz Martins; Stéphan Thomassé; Nicolas Trotignon 2025-10-10
Local limit of random wooded triangulations arxiv open Louigi Addario-Berry; Emma Hogan; Lukas Michel; Alex Scott 2025-11-10
Log-concave genus distribution for triangulations arxiv open Bojan Mohar 2025-12-27
Logarithmic expected faces in dense graphs arxiv open Jesse Campion Loth; Kevin Halasz; Tomáš Masařík; Bojan Mohar; Robert Šámal 2025-04-09
Lovász matching number in Cayley line hypergraphs arxiv disproved Alexander Clow; Penny Haxell; Bojan Mohar 2025-06-10
Matching number drop by k(r−1) deletions arxiv open Alexander Clow; Penny Haxell; Bojan Mohar 2025-06-10
Maximum edge density of spectrally symmetric graphs arxiv open Saieed Akbari; Jonathan Aloni; Maxwell Levit; Bojan Mohar; Steven Xia 2025-12-08
Merge-width characterised by FO-transduction neighbourhood complexity arxiv open Marthe Bonamy; Colin Geniet 2025-06-16
Minimum lazy transpositions in 2-uniformity networks arxiv open Carla Groenland; Tom Johnston; Jamie Radcliffe; Alex Scott 2025-10-23
Minimum negative p-energy at path graphs arxiv partial Saieed Akbari; Hitesh Kumar; Bojan Mohar; Shivaramakrishna Pragada 2025-06-20
Minimum transpositions in t-reachable networks arxiv open Carla Groenland; Tom Johnston; Jamie Radcliffe; Alex Scott 2025-10-23
MIS quasipolynomial time for planar induced-minor-free arxiv open Édouard Bonnet; Julien Duron; Colin Geniet; Stéphan Thomassé; Alexandra Wesolek 2025-12-31
Modular chromatic index of 0ₖ-graphs arxiv open Gaétan Berthe; Marthe Bonamy; Fábio Botler; Gaia Carenini; Lucas Colucci; Arthur Dumas; Fatemeh Ghasemi; Pedro Mariano Viana Neto 2025-12-05
Monochromatic non-nested matching in 2-edge-colored Kₘ arxiv partial János Barát; Zdeněk Dvořák; Penny Haxell; František Kardoš; Borut Lužar; Alfréd Onderko; Jozef Rajník; Roman Soták; Nikolay Ulyanov 2025-11-04
Monotonicity of all-swaps graph diameter arxiv open Ron M. Adin; Noga Alon; Yuval Roichman 2025-08-06
Non-antidirected paths at semidegree k/2 arxiv open Irena Penev; S Taruni; Stéphan Thomassé; Ana Trujillo-Negrete; Mykhaylo Tyomkyn 2025-03-29
Non-orientable embedding faces below orientable arxiv open Jesse Campion Loth; Kevin Halasz; Tomáš Masařík; Bojan Mohar; Robert Šámal 2025-04-09
Non-orientable random embedding faces of Kₙ arxiv open Jesse Campion Loth; Kevin Halasz; Tomáš Masařík; Bojan Mohar; Robert Šámal 2025-04-09
Non-realizable colorings for X-rooted Kₖ-minor-free graphs arxiv open Zdeněk Dvořák; Jan M. Swart 2025-04-10
Non-zero P_G coefficient in random 4-regular graphs arxiv open János Barát; Zdeněk Dvořák; Penny Haxell; František Kardoš; Borut Lužar; Alfréd Onderko; Jozef Rajník; Roman Soták; Nikolay Ulyanov 2025-11-04
NP-characterization of weightable digraphs arxiv partial Paul Seymour 2025-02-09
NP-hardness of Circuit Distance for polytopes arxiv open Alexander E. Black; Christian Nöbel; Raphael Steiner 2025-10-02
O(ℓ√log ℓ) bound for cyclic Kℓ-minors arxiv open Zdeněk Dvořák; Beatriz Martins; Stéphan Thomassé; Nicolas Trotignon 2025-10-10
Odd cycle orientations avoidable in digraphs arxiv open Micha Christoph; Barnabás Janzer; Kalina Petrova; Raphael Steiner 2025-10-13
Open: $f(\mathrm{OPT})$-approximation for largest (general) complete minor arxiv open Romain Bourneuf; Julien Cocquet; Chaoliang Tang; Stéphan Thomassé 2025-05-09
Optimal χ-to-χᵈ ratio in K_{d+1} blowups arxiv open Sergey Norin; Raphael Steiner 2025-04-02
Partition polytope diameter ⌈4κ₁/3⌉ bound arxiv open Steffen Borgwardt; Zdeněk Dvořák; Bryce Frederickson; Abigail Nix; Youngho Yoo 2025-07-28
Planar crossing-free drawing in annulus arxiv open Paul Seymour 2025-02-09
Polynomial 3-graph Ramsey numbers via blowup characterization arxiv open David Conlon; Jacob Fox; Benjamin Gunby; Xiaoyu He; Dhruv Mubayi; Andrew Suk; Jacques Verstraëte; Hung-Hsun Hans Yu 2025-10-29
Polynomial size even-cycle induced saturation arxiv open Xinyue Fan; Sahab Hajebi; Sepehr Hajebi; Sophie Spirkl 2025-06-02
Polynomial tree-α bound in K_{t,t}-free graphs arxiv open Noga Alon; Martin Milanič; Paweł Rzążewski 2025-11-05
Positive square energy lower bound s⁺(G) ≥ n arxiv open Saieed Akbari; Hitesh Kumar; Bojan Mohar; Shivaramakrishna Pragada; Shengtong Zhang 2025-06-08
Positive square energy of maximal planar graphs arxiv open Saieed Akbari; Hitesh Kumar; Bojan Mohar; Shivaramakrishna Pragada; Shengtong Zhang 2025-06-08
Positive square energy ≥ n for large clique arxiv open Saieed Akbari; Hitesh Kumar; Bojan Mohar; Shivaramakrishna Pragada; Shengtong Zhang 2025-06-08
Primality characterization of cyclic swap diameter arxiv partial Ron M. Adin; Noga Alon; Yuval Roichman 2025-08-06
q-color triangle Ramsey numbers of Kₙ arxiv open Jacob Fox; Jonathan Tidor; Shengtong Zhang 2025-10-01
Quasi-isometry distortion improvement for subdivision-closed classes arxiv open Tung Nguyen; Alex Scott; Paul Seymour 2025-10-02
Quasi-minor gap infimum for Kₜ arxiv open Marthe Bonamy; Marc Heinrich; Clément Legrand-Duchesne; Jonathan Narboni 2025-03-13
Rainbow cycles in non-abelian additive structure arxiv open Noga Alon; Matija Bucić; Lisa Sauermann; Dmitrii Zakharov; Or Zamir 2025-02-26
Schnyder wood limit of UIHPT arxiv open Louigi Addario-Berry; Emma Hogan; Lukas Michel; Alex Scott 2025-11-10
Schnyder woods existence on half-plane triangulations arxiv open Louigi Addario-Berry; Emma Hogan; Lukas Michel; Alex Scott 2025-11-10
Scol bounded by bramble number in polynomial expansion arxiv open Nicolas Bousquet; Wouter Cames van Batenburg; Louis Esperet; Gwenaël Joret; Piotr Micek 2025-09-15
Second phase transition in r-neighbourhood shotgun assembly arxiv partial Tom Johnston; Gal Kronenberg; Alexander Roberts; Alex Scott 2025-06-23
Sharp threshold for r-reconstructibility in G(n,p) arxiv open Tom Johnston; Gal Kronenberg; Alexander Roberts; Alex Scott 2025-06-23
Signs model minimises Q₃ connectivity arxiv open Paul Balister; Tom Johnston; Michael Savery; Alex Scott 2025-06-23
Sparse graph cut chromatic threshold arxiv disproved Guillaume Aubian; Marthe Bonamy; Romain Bourneuf; Oscar Fontaine; Lucas Picasarri-Arrieta 2025-10-02
Square energy sign in unicyclic odd-cycle graphs arxiv open Saieed Akbari; Hitesh Kumar; Bojan Mohar; Shivaramakrishna Pragada; Shengtong Zhang 2025-06-08
Strong 6-edge-coloring of diamond-free claw-free cubics arxiv open János Barát; Zdeněk Dvořák; Penny Haxell; František Kardoš; Borut Lužar; Alfréd Onderko; Jozef Rajník; Roman Soták; Nikolay Ulyanov 2025-11-04
Subcubic H-ISC planarity dichotomy arxiv open Pierre Aboulker; Édouard Bonnet; Timothé Picavet; Nicolas Trotignon 2025-02-07
Sumset small-doubling covering structure arxiv open Noga Alon; Huy Tuan Pham 2025-09-02
s⁺(G) = n characterizes bipartite unicyclic graphs arxiv open Saieed Akbari; Hitesh Kumar; Bojan Mohar; Shivaramakrishna Pragada; Shengtong Zhang 2025-06-08
s⁺(G) and s⁻(G) Extremal Characterization via Trees arxiv open Saieed Akbari; Hitesh Kumar; Bojan Mohar; Shivaramakrishna Pragada; Shengtong Zhang 2025-06-08
Tower-height lower bound for s-tightly connected k-graphs arxiv open David Conlon; Jacob Fox; Benjamin Gunby; Xiaoyu He; Dhruv Mubayi; Andrew Suk; Jacques Verstraëte; Hung-Hsun Hans Yu 2025-10-29
Tree-independence number via induced biclique number arxiv open Noga Alon; Martin Milanič; Paweł Rzążewski 2025-11-05
Unimodal genus distribution arxiv open Bojan Mohar 2025-12-27
½-flow-pair existence in bridgeless graphs arxiv open János Barát; Zdeněk Dvořák; Penny Haxell; František Kardoš; Borut Lužar; Alfréd Onderko; Jozef Rajník; Roman Soták; Nikolay Ulyanov 2025-11-04
χ-boundedness of radius-1 merge-width graphs arxiv open Marthe Bonamy; Colin Geniet 2025-06-16
χ-boundedness via odd cycle exclusion arxiv solved Hidde Koerts; Benjamin Moore; Sophie Spirkl 2025-03-25
2-subcube partition asymptotics in hypercube Q_d arxiv open Noga Alon; Jozsef Balogh; Vladimir N. Potapov 2024-11-07
3-colorability of K₃-minor-free hypergraphs arxiv open Raphael Steiner 2024-04-19
4/7 clustering exponent tight for strong products arxiv open Rutger Campbell; J. Pascal Gollin; Kevin Hendrey; Thomas Lesgourgues; Bojan Mohar; Youri Tamitegama; Jane Tan; David R. Wood 2024-07-31
5-choosability equals 5-colorability on torus arxiv open Zdeněk Dvořák; Félix Moreno Peñarrubia 2024-07-26
5-choosability equals 6-criticality on torus arxiv open Zdeněk Dvořák; Félix Moreno Peñarrubia 2024-07-26
Acyclic high-chromatic subgraph existence in tournaments arxiv open Jacob Fox; Matthew Kwan; Benny Sudakov 2024-05-30
Acyclic number Θ(√(n log n)) oriented triangle-free arxiv open Pierre Aboulker; Frédéric Havet; François Pirot; Juliette Schabanel 2024-03-04
Acyclic subgraph chromatic number in tournaments arxiv open Jacob Fox; Matthew Kwan; Benny Sudakov 2024-05-30
Adaptive gap for Δ-degree graph reconstruction arxiv open Lukas Michel; Alex Scott 2024-04-04
Alon-Tarsi orientation with half out-degree arxiv open Peter Bradshaw; Yaobin Chen; Hao Ma; Bojan Mohar; Hehui Wu 2024-06-20
Anti-Sidorenko orientation of every tree arxiv partial Jacob Fox; Zoe Himwich; Nitya Mani; Yunkun Zhou 2024-02-13
Blow-up closure of linear unavoidability arxiv partial Pierre Aboulker; Frédéric Havet; William Lochet; Raul Lopes; Lucas Picasarri-Arrieta; Clément Rambaud 2024-10-31
Bounded tree-α in (even hole, diamond)-free graphs arxiv partial Tara Abrishami; Bogdan Alecu; Maria Chudnovsky; Sepehr Hajebi; Sophie Spirkl; Kristina Vušković 2024-02-22
Bounded unvd ratio under vertex deletion arxiv open Pierre Aboulker; Frédéric Havet; William Lochet; Raul Lopes; Lucas Picasarri-Arrieta; Clément Rambaud 2024-10-31
Chromatic number of Kₜ-minor-free hypergraphs arxiv open Raphael Steiner 2024-04-19
Clustered chromatic number for odd-H-minor-free graphs arxiv open Robert Hickingbotham; Dong Yeap Kang; Sang-il Oum; Raphael Steiner; David R. Wood 2024-10-18
Constant-factor approximation for RFCPP arxiv open Stéphane Bessy; Stéphan Thomassé; Laurent Viennot 2024-01-11
Convex drawings via pseudocircular characterization arxiv open Helena Bergold; Stefan Felsner; Manfred Scheucher; Felix Schröder; Raphael Steiner 2024-07-27
Cop number √(n/k) bound for k-uniform hypergraphs arxiv open Joshua Erde; Mihyun Kang; Florian Lehner; Bojan Mohar; Dominik Schmid 2024-04-11
Edge-width four torus 5-choosability arxiv open Zdeněk Dvořák; Félix Moreno Peñarrubia 2024-07-26
ESₗ(n) joint dependence on ℓ arxiv open David Conlon; Jacob Fox; Xiaoyu He; Dhruv Mubayi; Andrew Suk; Jacques Verstraete 2024-05-06
Exponential unavoidability of tree k-extensions arxiv open Pierre Aboulker; Frédéric Havet; William Lochet; Raul Lopes; Lucas Picasarri-Arrieta; Clément Rambaud 2024-10-31
Finite H-family distinguishing random graphs arxiv open Emma Hogan; Alex Scott; Youri Tamitegama; Jane Tan 2024-02-29
f₂(d) asymptotic bound in hypercube partitions arxiv open Noga Alon; Jozsef Balogh; Vladimir N. Potapov 2024-11-07
Genus approximation hardness in spherical density regime arxiv open Yifan Jing; Bojan Mohar 2024-08-27
H-coloring graph polynomial determination arxiv open Emma Hogan; Alex Scott; Youri Tamitegama; Jane Tan 2024-02-29
Hereditary Turán theory in (c,t)-sparse graphs arxiv open Jacob Fox; Rajko Nenadov; Huy Tuan Pham 2024-06-08
Hypercube partition ratio growth rates arxiv partial Noga Alon; Jozsef Balogh; Vladimir N. Potapov 2024-11-07
Hypercube partitions and matchings counting arxiv open Noga Alon; Jozsef Balogh; Vladimir N. Potapov 2024-11-07
Induced Turán number for C_{2ℓ} in sparse graphs arxiv solved Jacob Fox; Rajko Nenadov; Huy Tuan Pham 2024-06-08
Joined Union Decomposition of Cayley Graphs arxiv partial Maria Chudnovsky; Michal Cizek; Logan Crew; Ján Mináč; Tung T. Nguyen; Sophie Spirkl; Nguyên Duy Tân 2024-01-11
k-extensions preserve linear unavoidability arxiv open Pierre Aboulker; Frédéric Havet; William Lochet; Raul Lopes; Lucas Picasarri-Arrieta; Clément Rambaud 2024-10-31
Left-maximal DFS-tree complexity in digraphs arxiv open Stéphane Bessy; Stéphan Thomassé; Laurent Viennot 2024-01-11
log R₂(2,n) polynomial in log M₂(n) arxiv open António Girão; Gal Kronenberg; Alex Scott 2024-12-31
Logarithmic treewidth of (even hole, Kₜ)-free graphs arxiv solved Tara Abrishami; Bogdan Alecu; Maria Chudnovsky; Sepehr Hajebi; Sophie Spirkl; Kristina Vušković 2024-02-22
Matching reducing Alon-Tarsi number to ½Δ arxiv open Peter Bradshaw; Yaobin Chen; Hao Ma; Bojan Mohar; Hehui Wu 2024-06-20
Maximum dichromatic number of oriented triangle-free graphs arxiv open Pierre Aboulker; Frédéric Havet; François Pirot; Juliette Schabanel 2024-03-04
MIS tractability in bounded-iocp graphs arxiv open Marthe Bonamy; Édouard Bonnet; Hugues Déprés; Louis Esperet; Colin Geniet; Claire Hilaire; Stéphan Thomassé; Alexandra Wesolek 2024-02-16
Monochromatic linear subspace two-coloring over 𝔽₂ⁿ arxiv open David Conlon; Jacob Fox; Huy Tuan Pham; Liana Yepremyan 2024-12-30
Multicolor Ramsey tower-exponent 3-graphs arxiv open Domagoj Bradač; Jacob Fox; Benny Sudakov 2024-04-29
MWIS polynomial-time on even-hole-free graphs arxiv open Maria Chudnovsky; Peter Gartland; Sepehr Hajebi; Daniel Lokshtanov; Sophie Spirkl 2024-07-12
No critical prism-canvas at spacing ≥ 5 arxiv open Zdeněk Dvořák; Félix Moreno Peñarrubia 2024-07-26
O(log n) forward cover for strong digraphs arxiv open Stéphane Bessy; Stéphan Thomassé; Laurent Viennot 2024-01-11
Off-diagonal tripartite Ramsey 2^O(n log n) bound arxiv open David Conlon; Jacob Fox; Benjamin Gunby; Xiaoyu He; Dhruv Mubayi; Andrew Suk; Jacques Verstraete 2024-04-02
Optimal balanced bi-tree size constant arxiv open Stéphane Bessy; Stéphan Thomassé; Laurent Viennot 2024-01-11
Optimal constant for tree blow-up unavoidability arxiv open Pierre Aboulker; Frédéric Havet; William Lochet; Raul Lopes; Lucas Picasarri-Arrieta; Clément Rambaud 2024-10-31
Optimal FCPP approximation ratio in digraphs arxiv open Stéphane Bessy; Stéphan Thomassé; Laurent Viennot 2024-01-11
Optimal randomised non-adaptive MIS reconstruction arxiv open Lukas Michel; Alex Scott 2024-04-04
Optimal size of (1,r)-cover-free families arxiv open Lukas Michel; Alex Scott 2024-04-04
Pair-complexity lower bound for 3-graph Ramsey arxiv open David Conlon; Jacob Fox; Benjamin Gunby; Xiaoyu He; Dhruv Mubayi; Andrew Suk; Jacques Verstraete 2024-04-02
Polynomial close Rödl property for hereditary families arxiv open Matija Bucić; Jacob Fox; Huy Tuan Pham 2024-04-19
Polynomial MIS in 𝒪_k-free graphs arxiv open Marthe Bonamy; Édouard Bonnet; Hugues Déprés; Louis Esperet; Colin Geniet; Claire Hilaire; Stéphan Thomassé; Alexandra Wesolek 2024-02-16
Polynomial pure pairs for ordered graphs H arxiv open Alex Scott; Paul Seymour; Sophie Spirkl 2024-02-06
Polynomial unavoidability in bounded average degree digraphs arxiv open Pierre Aboulker; Frédéric Havet; William Lochet; Raul Lopes; Lucas Picasarri-Arrieta; Clément Rambaud 2024-10-31
Polynomial η-bound for P₅-free graphs arxiv open Sepehr Hajebi; Yanjia Li; Sophie Spirkl 2024-01-16
Polynomial η-boundedness of M_t-free graphs arxiv solved Sepehr Hajebi; Yanjia Li; Sophie Spirkl 2024-01-16
Polynomial-time Coloring on even-hole-free graphs arxiv open Maria Chudnovsky; Peter Gartland; Sepehr Hajebi; Daniel Lokshtanov; Sophie Spirkl 2024-07-12
Precise asymptotic of f(n,r,s) for s ≤ √r/log r arxiv open Noga Alon; Matija Bucić; Micha Christoph; Michael Krivelevich 2024-06-10
Primeness of Cayley graphs over finite rings arxiv partial Maria Chudnovsky; Michal Cizek; Logan Crew; Ján Mináč; Tung T. Nguyen; Sophie Spirkl; Nguyên Duy Tân 2024-01-11
Primeness of tensor products of complete graphs arxiv open Maria Chudnovsky; Michal Cizek; Logan Crew; Ján Mináč; Tung T. Nguyen; Sophie Spirkl; Nguyên Duy Tân 2024-01-11
Pure pair in triangle-free 3-blockade arxiv open Alex Scott; Paul Seymour; Sophie Spirkl 2024-02-06
Purely exponential off-diagonal 3-graph Ramsey rate arxiv open David Conlon; Jacob Fox; Benjamin Gunby; Xiaoyu He; Dhruv Mubayi; Andrew Suk; Jacques Verstraete 2024-04-02
Rainbow stacking universality for odd Kₙ arxiv open Noga Alon; Colin Defant; Noah Kravitz 2024-05-23
Sharp threshold for rainbow stacking of edge-colorings arxiv open Noga Alon; Colin Defant; Noah Kravitz 2024-05-23
Square energy ⁴⁄₅n lower bound arxiv open Saieed Akbari; Hitesh Kumar; Bojan Mohar; Shivaramakrishna Pragada 2024-09-26
Strong 2-kernel size bound in split digraphs arxiv open Tung Nguyen; Alex Scott; Paul Seymour 2024-09-08
Strong transversal property forest characterization arxiv open Alex Scott; Paul Seymour; Sophie Spirkl 2024-02-06
Subexponential gap for dimension-2 subcube partitions arxiv open Noga Alon; Jozsef Balogh; Vladimir N. Potapov 2024-11-07
Subexponential Ramsey bound for linear 3-graphs arxiv open David Conlon; Jacob Fox; Benjamin Gunby; Xiaoyu He; Dhruv Mubayi; Andrew Suk; Jacques Verstraete 2024-04-02
Super-polynomial growth of 3-uniform complete Ramsey arxiv open David Conlon; Jacob Fox; Benjamin Gunby; Xiaoyu He; Dhruv Mubayi; Andrew Suk; Jacques Verstraete 2024-04-02
Superexponential growth of R₂(2,n) arxiv open António Girão; Gal Kronenberg; Alex Scott 2024-12-31
Tight bounds for hypercube λ(d,s) arxiv partial Noga Alon; Maria Axenovich; John Goldwasser 2024-10-27
Tight clustering bound in treewidth-path strong product arxiv partial Rutger Campbell; J. Pascal Gollin; Kevin Hendrey; Thomas Lesgourgues; Bojan Mohar; Youri Tamitegama; Jane Tan; David R. Wood 2024-07-31
Tower height for k-uniform Ramsey growth rate arxiv partial Domagoj Bradač; Jacob Fox; Benny Sudakov 2024-04-29
Transition threshold between f and g arxiv open Noga Alon; Matija Bucić; Micha Christoph; Michael Krivelevich 2024-06-10
Twin-width bound for K_{t,t}-free O_k-free graphs arxiv open Marthe Bonamy; Édouard Bonnet; Hugues Déprés; Louis Esperet; Colin Geniet; Claire Hilaire; Stéphan Thomassé; Alexandra Wesolek 2024-02-16
Unavoidability rate of k-extensions in tournaments arxiv open Pierre Aboulker; Frédéric Havet; William Lochet; Raul Lopes; Lucas Picasarri-Arrieta; Clément Rambaud 2024-10-31
Unavoidable language in padded strings arxiv open Bogdan Alecu; Maria Chudnovsky; Sepehr Hajebi; Sophie Spirkl 2024-11-26
Universality for bounded-density graph families arxiv open Noga Alon; Natalie Dodson; Carmen Jackson; Rose McCarty; Rajko Nenadov; Lani Southern 2024-01-11
η-boundedness for H-free graphs arxiv partial Sepehr Hajebi; Yanjia Li; Sophie Spirkl 2024-01-16
η-boundedness for two-star unions arxiv open Sepehr Hajebi; Yanjia Li; Sophie Spirkl 2024-01-16
η-boundedness of Pₜ-free graphs arxiv open Sepehr Hajebi; Yanjia Li; Sophie Spirkl 2024-01-16
λ(d,1) asymptotic limit 1/e hypercube arxiv open Noga Alon; Maria Axenovich; John Goldwasser 2024-10-27
χ(G) bound via spectral radius for triangle-free graphs arxiv open Anders Martinsson; Raphael Steiner 2024-12-31
χ-ζ gap 3 for ω < 5 graphs arxiv open Raphael Steiner 2024-08-20
2-extremal digraph characterization via χ and λ arxiv open Pierre Aboulker; Guillaume Aubian; Pierre Charbit 2023-09-13
4-coloring extension via well-separated long faces arxiv open Zdeněk Dvořák; Benjamin Moore; Michaela Seifrtová; Robert Šámal 2023-12-20
Binary vectors with cube-length forbidden symmetric difference arxiv open Noga Alon 2023-02-06
Binomial sampling gap for independence ratio arxiv partial Noga Alon; Ehud Friedgut; Gil Kalai; Guy Kindler 2023-08-21
Boundary rigidity of k-dimensional cube complexes arxiv partial John Haslegrave; Alex Scott; Youri Tamitegama; Jane Tan 2023-09-08
Bounded-size ω→-witness subtournament arxiv partial Pierre Aboulker; Guillaume Aubian; Pierre Charbit; Raul Lopes 2023-10-06
BST Rotation Distance Computational Complexity arxiv solved Jean Cardinal; Raphael Steiner 2023-11-06
BST-ordering bound for tournament clique number arxiv unclear Pierre Aboulker; Guillaume Aubian; Pierre Charbit; Raul Lopes 2023-10-06
Characterisation of ℓ-holed graphs ℓ ∈ {4,5,6} arxiv open Linda Cook; Jake Horsfield; Myriam Preissmann; Cléophée Robin; Paul Seymour; Ni Luh Dewi Sintiari; Nicolas Trotignon; Kristina Vušković 2023-12-21
Chordal modulator characterization for even-hole-free graphs arxiv partial Tara Abrishami; Bogdan Alecu; Maria Chudnovsky; Sepehr Hajebi; Sophie Spirkl 2023-01-28
Clean H-free classes from finite families arxiv partial Tara Abrishami; Bogdan Alecu; Maria Chudnovsky; Sepehr Hajebi; Sophie Spirkl 2023-11-07
Cleanness of t-clock-free graphs arxiv open Maria Chudnovsky; Sepehr Hajebi; Sophie Spirkl 2023-11-09
Connectivity code of torus graphs C_t × C_s arxiv open Noga Alon 2023-09-06
Cycle in out-neighbourhood for high-χ graphs arxiv open António Girão; Kevin Hendrey; Freddie Illingworth; Florian Lehner; Lukas Michel; Michael Savery; Raphael Steiner 2023-12-04
Dense linear subhypergraph with quadratic edges arxiv open Jacob Fox; Maya Sankar; Michael Simkin; Jonathan Tidor; Yunkun Zhou 2023-12-31
D₅-free condition necessity in strong EH-property arxiv open Maria Chudnovsky; Alex Scott; Paul Seymour; Sophie Spirkl 2023-08-08
Even-edge graphs and H-code density arxiv partial Noga Alon 2023-02-06
Existence of limit n(2,d)/d² arxiv open Noga Alon; Jarosław Grytczuk; Andrzej P. Kisielewicz; Krzysztof Przesławski 2023-03-03
Fixed-k vertex-critical edge-robustness chromatic arxiv partial Anders Martinsson; Raphael Steiner 2023-10-19
Flash-rainbow tournament edge-coloring formula arxiv open António Girão; Freddie Illingworth; Lukas Michel; Michael Savery; Alex Scott 2023-06-01
Flip Distance Complexity for Rectangulations arxiv open Jean Cardinal; Raphael Steiner 2023-11-06
Forests are multibounding chromatic bound arxiv open Tung Nguyen; Alex Scott; Paul Seymour 2023-03-21
Fractional independence in Kneser Hamming powers arxiv open Noga Alon; Ehud Friedgut; Gil Kalai; Guy Kindler 2023-08-21
Girth-preserving χ-boundedness for triangle-free F arxiv open António Girão; Freddie Illingworth; Emil Powierski; Michael Savery; Alex Scott; Youri Tamitegama; Jane Tan 2023-09-18
Grassmannian subvariety for claw-free incomparability graphs arxiv open Logan Crew; Oliver Pechenik; Sophie Spirkl 2023-05-18
H-minor-free choosability equal to v−1 arxiv open Olivier Fischer; Raphael Steiner 2023-04-09
Happy triples extremal bound for l < k/2 arxiv open Patrick Hompe; Zishen Qu; Sophie Spirkl 2023-09-11
High chromatic number forcing high degeneracy out-neighbourhood arxiv open António Girão; Kevin Hendrey; Freddie Illingworth; Florian Lehner; Lukas Michel; Michael Savery; Raphael Steiner 2023-12-04
Induced Menger separation with bounded degree arxiv open Kevin Hendrey; Sergey Norin; Raphael Steiner; Jérémie Turcotte 2023-09-14
Infinitely Many k-ω-critical Tournaments arxiv unclear Pierre Aboulker; Guillaume Aubian; Pierre Charbit; Raul Lopes 2023-10-06
k-Coloring dichotomy for H-free graphs arxiv open Maria Chudnovsky; Sepehr Hajebi; Sophie Spirkl 2023-11-09
K₄ graph-code density vanishing arxiv partial Noga Alon 2023-02-06
Large dom implies ω̄-cluster in tournaments arxiv solved Pierre Aboulker; Guillaume Aubian; Pierre Charbit; Raul Lopes 2023-10-06
Linear disjoint edges in complete topological graphs arxiv open Jacob Fox; Janos Pach; Andrew Suk 2023-12-02
Linear face bound in random graph embeddings arxiv open Jesse Campion Loth; Bojan Mohar 2023-03-30
Linear graph-code cardinality bounds for even H arxiv partial Noga Alon 2023-02-06
Linear pure pair in sparse H-free graphs arxiv open Alex Scott; Paul Seymour; Sophie Spirkl 2023-10-29
Linear rainbow path cover of edge-colored graphs arxiv open Marthe Bonamy; Fábio Botler; François Dross; Tássio Naia; Jozef Skokan 2023-10-10
Linear strongly-separating path system constant arxiv open Marthe Bonamy; Fábio Botler; François Dross; Tássio Naia; Jozef Skokan 2023-10-10
Local clique number bounds global in tournaments arxiv unclear Pierre Aboulker; Guillaume Aubian; Pierre Charbit; Raul Lopes 2023-10-06
Maximum D(n,k) asymptotics in IS reconfiguration arxiv open Nicolas Bousquet; Bastien Durain; Théo Pierron; Stéphan Thomassé 2023-01-05
Mixed blowup coloring of K_{r(k)-1}[2] arxiv open Jacob Fox; Yuval Wigderson 2023-06-27
Multi-color √m graph Ramsey bound arxiv open Domagoj Bradač; Jacob Fox; Benny Sudakov 2023-08-21
MWIS QPTAS in subdivision-of-forest-free graphs arxiv open Maria Chudnovsky; Marcin Pilipczuk; Michał Pilipczuk; Stéphan Thomassé 2023-11-14
n(2,d) asymptotic limit ½ arxiv partial Noga Alon; Jarosław Grytczuk; Andrzej P. Kisielewicz; Krzysztof Przesławski 2023-03-03
n^{1/4} tight bound for non-averaging sets arxiv solved David Conlon; Jacob Fox; Huy Tuan Pham 2023-11-02
Nondominating broom copy in χ-bounded graphs arxiv open Maria Chudnovsky; Alex Scott; Paul Seymour; Sophie Spirkl 2023-03-22
NP-hardness of square root for planar graphs arxiv open Zdeněk Dvořák; Benjamin Moore; Abhiruk Lahiri 2023-07-13
Odd-intersection edge coloring of Kₙ arxiv partial Noga Alon 2023-02-06
Odd-Δ planar linear arboricity with matching arxiv partial Marthe Bonamy; Jadwiga Czyżewska; Łukasz Kowalik; Michał Pilipczuk 2023-02-26
p-Centered coloring bound for minor-free graphs arxiv solved Vida Dujmović; Robert Hickingbotham; Jędrzej Hodor; Gweanël Joret; Hoang La; Piotr Micek; Pat Morin; Clément Rambaud; David R. Wood 2023-07-06
p-Goodness Threshold Not Tight for Books arxiv open Jacob Fox; Xiaoyu He; Yuval Wigderson 2023-07-14
Parameterized complexity of separable index arxiv open Édouard Bonnet; Romain Bourneuf; Colin Geniet; Stéphan Thomassé 2023-08-06
Pendant edges suffice for k-critical bonbons arxiv open Jacob Fox; Yuval Wigderson 2023-06-27
Polite integers in Ramsey multiplicity arxiv open Jacob Fox; Yuval Wigderson 2023-06-27
Polynomial 3-coloring for path-component-free graphs arxiv open Maria Chudnovsky; Sepehr Hajebi; Sophie Spirkl 2023-11-09
Polynomial bound for C₄-free average degree arxiv open Xiying Du; António Girão; Zach Hunter; Rose McCarty; Alex Scott 2023-11-01
Polynomial degree-bounding for hereditary degree-bounded classes arxiv solved Xiying Du; António Girão; Zach Hunter; Rose McCarty; Alex Scott 2023-11-01
Polynomial dichromatic boundedness under substitution closure arxiv open Pierre Aboulker; Guillaume Aubian; Pierre Charbit; Raul Lopes 2023-10-06
Polynomial separable index for pattern-avoiding permutations arxiv open Édouard Bonnet; Romain Bourneuf; Colin Geniet; Stéphan Thomassé 2023-08-06
Polynomial utw bound for minor-free classes arxiv open Vida Dujmović; Robert Hickingbotham; Jędrzej Hodor; Gweanël Joret; Hoang La; Piotr Micek; Pat Morin; Clément Rambaud; David R. Wood 2023-07-06
Polynomial τ_d-boundedness implies polynomial bound arxiv open Alex Scott; Paul Seymour 2023-01-10
Polynomial χ-bound for path-induced rooted tree arxiv open Tung Nguyen; Alex Scott; Paul Seymour 2023-02-17
Polynomial χ-bound via τ_d for path-free graphs arxiv partial Alex Scott; Paul Seymour 2023-01-10
Polynomial χ-boundedness for forest-free graphs arxiv partial Alex Scott; Paul Seymour 2023-01-10
Polynomial χ-boundedness for H-free forest classes arxiv partial Maria Chudnovsky; Alex Scott; Paul Seymour; Sophie Spirkl 2023-03-22
Polynomial χ-bounding in Gyárfás-Sumner arxiv partial Tung Nguyen; Alex Scott; Paul Seymour 2023-02-17
Polynomial-time precoloring extension in planar near-Eulerian-triangulations arxiv open Zdeněk Dvořák; Benjamin Moore; Michaela Seifrtová; Robert Šámal 2023-12-20
Positive gap in hat-problem success probability arxiv open Noga Alon; Ehud Friedgut; Gil Kalai; Guy Kindler 2023-08-21
Prescribed Ramsey growth rate approximation arxiv open Isabel Ahme; Alex Scott 2023-11-03
Product structure open problem for sublinear separators arxiv partial Zdeněk Dvořák; David R. Wood 2023-09-27
Product structure with bounded tree-depth separators arxiv open Zdeněk Dvořák; David R. Wood 2023-09-27
Profile and Neighborhood Complexity of Planar Graphs arxiv open Gwenaël Joret; Clément Rambaud 2023-12-19
Profile complexity of K_t-minor-free graphs arxiv solved Gwenaël Joret; Clément Rambaud 2023-12-19
Protrusive ordering not witnessed by 5 points arxiv solved Noga Alon; Colin Defant; Noah Kravitz; Daniel G. Zhu 2023-08-09
Ramsey bound for 3-uniform sparse hypergraphs arxiv open Jacob Fox; Maya Sankar; Michael Simkin; Jonathan Tidor; Yunkun Zhou 2023-12-31
Random Graph Correspondence Chromatic Number Θ(n/log n) arxiv open Zdenek Dvorak; Liana Yepremyan 2023-07-27
Regularity-free proof of Nikiforov–Rousseau goodness theorem arxiv open Jacob Fox; Xiaoyu He; Yuval Wigderson 2023-07-14
Scott–Seymour property for random tournaments arxiv open António Girão; Kevin Hendrey; Freddie Illingworth; Florian Lehner; Lukas Michel; Michael Savery; Raphael Steiner 2023-12-04
Set-coloring Ramsey number equals A_q(r,s)+1 arxiv open David Conlon; Jacob Fox; Huy Tuan Pham; Yufei Zhao 2023-08-14
Sharpness of treedepth O(thb) bound arxiv open Meike Hatzel; Gwenaël Joret; Piotr Micek; Marcin Pilipczuk; Torsten Ueckerdt; Bartosz Walczak 2023-11-06
Sign-pattern bound r-dependence gap arxiv open Noga Alon; Colin Defant; Noah Kravitz; Daniel G. Zhu 2023-08-09
Simultaneous ω-ordering and χ-ordering in tournaments arxiv unclear Pierre Aboulker; Guillaume Aubian; Pierre Charbit; Raul Lopes 2023-10-06
Strong EH-property via backedge forest tournaments arxiv open Maria Chudnovsky; Alex Scott; Paul Seymour; Sophie Spirkl 2023-08-08
Stronger coherence condition for pure pairs arxiv open Alex Scott; Paul Seymour; Sophie Spirkl 2023-10-29
Super-cubic diameter of 4-configuration graph arxiv open Nicolas Bousquet; Bastien Durain; Théo Pierron; Stéphan Thomassé 2023-01-05
Threshold (1+ε)/n for Ω(n) distance reconstruction arxiv solved António Girão; Freddie Illingworth; Lukas Michel; Emil Powierski; Alex Scott 2023-01-26
Top-k eigenvalue limit points of d-regular graphs arxiv solved Noga Alon; Fan Wei 2023-10-13
Topological-minor exclusion product structure arxiv open Vida Dujmović; Robert Hickingbotham; Jędrzej Hodor; Gweanël Joret; Hoang La; Piotr Micek; Pat Morin; Clément Rambaud; David R. Wood 2023-07-06
Turán exponent of Latin square hypergraphs arxiv open Jacob Fox; Maya Sankar; Michael Simkin; Jonathan Tidor; Yunkun Zhou 2023-12-31
Turán Exponent via d_max for k-partite Hypergraphs arxiv open Jacob Fox; Maya Sankar; Michael Simkin; Jonathan Tidor; Yunkun Zhou 2023-12-31
Vanishing hat-success probability for intersecting families arxiv open Noga Alon; Ehud Friedgut; Gil Kalai; Guy Kindler 2023-08-21
Vanishing success probability for monotone hat strategies arxiv open Noga Alon; Ehud Friedgut; Gil Kalai; Guy Kindler 2023-08-21
Zero-count gap for sums of square-root polynomials arxiv open Noga Alon; Colin Defant; Noah Kravitz; Daniel G. Zhu 2023-08-09
Δ(1,1,H) hero transfer under K₁+F arxiv open Pierre Aboulker; Guillaume Aubian; Pierre Charbit 2023-12-11
Δ(1,2,2) hero in oriented complete multipartite graphs arxiv disproved Pierre Aboulker; Guillaume Aubian; Pierre Charbit 2023-12-11
Δ(1,2,2) hero status in {K₁+P⃗₂}-free digraphs arxiv open Alvaro Carbonero; Hidde Koerts; Benjamin Moore; Sophie Spirkl 2023-06-07
Δ(1,m,m') hero status for degree-4 oriented stars arxiv open Alvaro Carbonero; Hidde Koerts; Benjamin Moore; Sophie Spirkl 2023-06-07
χ threshold for tournament out-neighbourhood 3-coloring arxiv open António Girão; Kevin Hendrey; Freddie Illingworth; Florian Lehner; Lukas Michel; Michael Savery; Raphael Steiner 2023-12-04
χ-boundedness of matchings in ordered graphs arxiv open Pierre Aboulker; Guillaume Aubian; Pierre Charbit; Raul Lopes 2023-10-06
χ-finite families characterizing dichromatic boundedness arxiv open Alvaro Carbonero; Hidde Koerts; Benjamin Moore; Sophie Spirkl 2023-06-07
χ̄-boundedness closed under substitution arxiv open Pierre Aboulker; Guillaume Aubian; Pierre Charbit; Raul Lopes 2023-10-06
χ̄-boundedness for bounded twin-width tournaments arxiv open Pierre Aboulker; Guillaume Aubian; Pierre Charbit; Raul Lopes 2023-10-06
χ⃗-binding tournaments with forest backedge graphs arxiv open Pierre Aboulker; Guillaume Aubian; Pierre Charbit; Raul Lopes 2023-10-06
→χ-bounding ordering for bounded-twin-width tournaments arxiv unclear Pierre Aboulker; Guillaume Aubian; Pierre Charbit; Raul Lopes 2023-10-06
3-flowability via K⁺₃,ₙ₋₃-free subcontraction arxiv open Christoph Hertrich; Felix Schröder; Raphael Steiner 2022-08-26
3-uniform Ramsey K⁴⁻ vs star Θ(n²/log n) arxiv open David Conlon; Jacob Fox; Xiaoyu He; Dhruv Mubayi; Andrew Suk; Jacques Verstraete 2022-10-07
5-Coloring complexity for P₄+rP₃-free graphs arxiv solved Sepehr Hajebi; Yanjia Li; Sophie Spirkl 2022-08-30
7-choosability for K₄,₄- and K₃,₅-minor-free graphs arxiv open Raphael Steiner 2022-01-22
Actual diameter of arithmetic hyperbolic surfaces arxiv open Raphael S. Steiner 2022-07-26
All graphs self-isolating arxiv open Maria Chudnovsky; Alex Scott; Paul Seymour; Sophie Spirkl 2022-02-18
Asymmetric and classical Sidorenko property equivalence arxiv open Jacob Fox; Zoe Himwich; Nitya Mani; Yunkun Zhou 2022-10-30
Bipartite-missing hereditary ex(G(n,p), P) sharp asymptotics arxiv partial Noga Alon; Michael Krivelevich; Wojciech Samotij 2022-10-23
Bounded treewidth for (C₄, diamond, theta, prism)-free graphs arxiv open Tara Abrishami; Maria Chudnovsky; Sepehr Hajebi; Sophie Spirkl 2022-10-21
Characterisation of poly-χ-bounded hereditary classes arxiv open Maria Chudnovsky; Alex Scott; Paul Seymour; Sophie Spirkl 2022-02-18
Closure of good trees under disjoint union arxiv partial Maria Chudnovsky; Alex Scott; Paul Seymour; Sophie Spirkl 2022-02-18
Complexity of 2-F-PFC for star-pruned oriented trees arxiv open Helena Bergold; Winfried Hochstättler; Raphael Steiner 2022-06-07
Counting perfect matchings #P-hard for α=2 graphs arxiv solved Nicolas El Maalouly; Raphael Steiner 2022-07-13
d(s) asymptotics in minimum-outdegree subdigraphs arxiv open Raphael Steiner 2022-10-23
Delineation of unit segment graphs by twin-width arxiv partial Édouard Bonnet; Dibyayan Chakraborty; Eun Jung Kim; Noleen Köhler; Raul Lopes; Stéphan Thomassé 2022-04-01
Dense minor edge density improvement arxiv partial Sergey Norin; Paul Seymour 2022-06-01
Dichromatic construction size in C₃ arxiv open Pierre Aboulker; Nicolas Bousquet; Rémi de Verclos 2022-02-02
Directed forcing characterization via homomorphism arxiv open Jacob Fox; Zoe Himwich; Nitya Mani; Yunkun Zhou 2022-10-30
Directed Sidorenko property for K₂-homomorphic bipartite arxiv open Jacob Fox; Zoe Himwich; Nitya Mani; Yunkun Zhou 2022-10-30
Directed surplus in random ℬ-free orientations arxiv open Jacob Fox; Zoe Himwich; Nitya Mani 2022-04-19
Equivalent growth of N_DFL and 1/δ_TRL arxiv open Jacob Fox; Yufei Zhao 2022-01-13
Exact formula for U_t(n) lazy transpositions arxiv partial Carla Groenland; Tom Johnston; Jamie Radcliffe; Alex Scott 2022-08-13
Exact threshold Ramsey multiplicity for paths arxiv open David Conlon; Jacob Fox; Benny Sudakov; Fan Wei 2022-08-07
Explicit group construction with infinite twin-width arxiv open Édouard Bonnet; Colin Geniet; Romain Tessera; Stéphan Thomassé 2022-07-15
Exponential constant in list Ramsey numbers arxiv open Jacob Fox; Xiaoyu He; Sammy Luo; Max Wenqiang Xu 2022-01-23
Genus coefficient in Z₃-flow-critical density arxiv open Zdeněk Dvořák; Bojan Mohar 2022-12-04
Geometric anti-concentration for nonzero vectors arxiv partial Jacob Fox; Matthew Kwan; Hunter Spink 2022-06-14
Grid Ramsey number rectangle vs clique arxiv open David Conlon; Jacob Fox; Xiaoyu He; Dhruv Mubayi; Andrew Suk; Jacques Verstraete 2022-10-07
Implicit representation for sub-polynomial speed hereditary families arxiv open Noga Alon 2022-01-02
Infinite family of 4-vertex-critical arrangement graphs arxiv open Man-Kwun Chiu; Stefan Felsner; Manfred Scheucher; Felix Schröder; Raphael Steiner; Birgit Vogtenhuber 2022-05-17
K⁴₃ Ramsey equals G_{2×2} Graded Ramsey Order arxiv open David Conlon; Jacob Fox; Xiaoyu He; Dhruv Mubayi; Andrew Suk; Jacques Verstraete 2022-10-07
K₅ minor via degree bounds in bipartite graphs arxiv open Maria Chudnovsky; Alex Scott; Paul Seymour; Sophie Spirkl 2022-04-21
K₆ minor from minimum degree five in bipartite graphs arxiv open Maria Chudnovsky; Alex Scott; Paul Seymour; Sophie Spirkl 2022-04-21
K₆ minor in 6-regular graphs arxiv open Maria Chudnovsky; Alex Scott; Paul Seymour; Sophie Spirkl 2022-04-21
Linear K_{r-1}-free subgraph in K_r-free segment graphs arxiv open Jacob Fox; Janos Pach; Andrew Suk 2022-10-25
Linear-growth graphs as tree boxtimes clique subgraphs arxiv open Rutger Campbell; Marc Distel; J. Pascal Gollin; Daniel J. Harvey; Kevin Hendrey; Robert Hickingbotham; Bojan Mohar; David R. Wood 2022-10-25
List chromatic number bound for K_{s,t}-minor-free graphs arxiv open Raphael Steiner 2022-01-22
List Ramsey exact value for chromatic families arxiv open Jacob Fox; Xiaoyu He; Sammy Luo; Max Wenqiang Xu 2022-01-23
List Total Coloring χ″ℓ ≤ Δ+2 arxiv open Marthe Bonamy; Théo Pierron; Éric Sopena 2022-12-09
List-choosability of K_{s,t}-minor-free graphs arxiv open Raphael Steiner 2022-01-22
Logarithmic treewidth via four forbidden families arxiv open Tara Abrishami; Maria Chudnovsky; Sepehr Hajebi; Sophie Spirkl 2022-09-07
M_{F_{2c}}(n) gap for odd n arxiv open Noga Alon; Anna Gujgiczer; János Körner; Aleksa Milojević; Gábor Simonyi 2022-04-01
Near-acyclic r-free digraphs for r > 2n/3 arxiv solved Jacob Fox; Zoe Himwich; Nitya Mani 2022-04-19
NP-hardness of List-k-Coloring on rP₃-free graphs arxiv solved Sepehr Hajebi; Yanjia Li; Sophie Spirkl 2022-08-30
O(1/√n) bound for o-minimal Littlewood-Offord arxiv partial Jacob Fox; Matthew Kwan; Hunter Spink 2022-06-14
p(n) range for hereditary subgraph concentration arxiv open Noga Alon; Michael Krivelevich; Wojciech Samotij 2022-10-23
Parameters governing acyclic digraph Ramsey growth arxiv partial Jacob Fox; Xiaoyu He; Yuval Wigderson 2022-01-21
Planar graph r-th weak coloring number O(r² log r) arxiv partial Gwenaël Joret; Piotr Micek 2022-03-25
Polynomial saving in bipartite hereditary ex arxiv solved Noga Alon; Michael Krivelevich; Wojciech Samotij 2022-10-23
Polynomial χ-boundedness for forest-free graphs arxiv partial Alex Scott; Paul Seymour; Sophie Spirkl 2022-10-02
Polynomial χ-boundedness for H-free forests arxiv partial Maria Chudnovsky; Alex Scott; Paul Seymour; Sophie Spirkl 2022-02-18
Polynomial χ-boundedness for odd-cycle k-multihole graphs arxiv open Maria Chudnovsky; Alex Scott; Paul Seymour; Sophie Spirkl 2022-02-18
Property (*) range extension to d = o(n/log n) arxiv open Jacob Fox; Sammy Luo; Huy Tuan Pham 2022-07-27
R(n;r,s) vs R'(n;r,s) near Turán density equality arxiv partial David Conlon; Jacob Fox; Xiaoyu He; Dhruv Mubayi; Andrew Suk; Jacques Verstraete 2022-06-22
R-burnability of trees with bounded growth arxiv open Paul Bastide; Marthe Bonamy; Anthony Bonato; Pierre Charbit; Shahin Kamali; Théo Pierron; Mikaël Rabie 2022-03-04
Smallest K_{s,t}-minor Woodall counterexample arxiv partial Raphael Steiner 2022-01-22
Sufficiency of E, R, T for Generic Multiplicity Matrices arxiv solved Noga Alon; Noah Kravitz; Kevin O'Bryant 2022-12-10
Tight asymptotic dimension bound for intersection graphs arxiv open Zdeněk Dvořák; Sergey Norin 2022-10-04
Tightness of cᵣ upper bound for r ≥ 3 arxiv open David Conlon; Jacob Fox; Huy Tuan Pham 2022-09-22
Turán extremal problem for H-free bounded matching arxiv partial Noga Alon; Peter Frankl 2022-10-26
Twin-width approximation for unordered graphs arxiv partial Édouard Bonnet; Eun Jung Kim; Amadeus Reinald; Stéphan Thomassé 2022-05-31
Twin-width of matrices over infinite fields arxiv open Édouard Bonnet; Ugo Giocanti; Patrice Ossona de Mendez; Stéphan Thomassé 2022-09-24
Twin-width vs Queue Number Separation arxiv open Édouard Bonnet; Colin Geniet; Romain Tessera; Stéphan Thomassé 2022-07-15
Uniform twin-width strictly stronger than twin-width arxiv open Édouard Bonnet; Colin Geniet; Romain Tessera; Stéphan Thomassé 2022-07-15
δ≥6, Δ≤8 forces K_6 minor arxiv open Maria Chudnovsky; Alex Scott; Paul Seymour; Sophie Spirkl 2022-04-21
ε-restricted union cover for H-free graphs arxiv open Maria Chudnovsky; Alex Scott; Paul Seymour; Sophie Spirkl 2022-08-03
χ-boundedness for odd-cycle-free digraphs arxiv open Alvaro Carbonero; Patrick Hompe; Benjamin Moore; Sophie Spirkl 2022-09-15
χ-boundedness with clique number 3 and triangle-free subgraphs arxiv open Alvaro Carbonero; Patrick Hompe; Benjamin Moore; Sophie Spirkl 2022-09-15
√n log n implicit labels for hereditary families arxiv open Noga Alon 2022-01-02
4-coloring extension for near-triangulations arxiv partial Zdeněk Dvořák; Bernard Lidický 2021-10-25
Asymmetric Krivelevich–Alon choosability for bipartite graphs arxiv open Noga Alon; Stijn Cambie; Ross J. Kang 2021-08-30
Chromatic number of G_{m,t} is Θ(t²) arxiv open Noga Alon 2021-04-04
Clique algorithm optimality in active clustering arxiv open Quentin Lutz; Élie de Panafieu; Alex Scott; Maya Stein 2021-10-27
Complexity of Σ-k-dicolourability k∈{4,5} arxiv open Pierre Aboulker; Frédéric Havet; Kolja Knauer; Clément Rambaud 2021-11-16
Connected k-domination no-kernel at twin-width 4 arxiv open Édouard Bonnet; Eun Jung Kim; Amadeus Reinald; Stéphan Thomassé; Rémi Watrigant 2021-09-14
Convex unit distance realizability of G_k arxiv open Mateusz Skomra; Stéphan Thomassé 2021-06-02
Dictator-to-XOR Lipschitz inverse gap arxiv open Tom Johnston; Alex Scott 2021-12-10
Edges covered by k vertex neighborhoods arxiv open Jacob Fox; Zoe Himwich; Nitya Mani 2021-03-19
Erdős–Hajnal property for {C₈, C̄₈} arxiv open Maria Chudnovsky; Alex Scott; Paul Seymour; Sophie Spirkl 2021-02-09
Exact exponent constant for tournament path powers arxiv open Nemanja Draganić; François Dross; Jacob Fox; António Girão; Frédéric Havet; Dániel Korándi; William Lochet; David Munhá Correia; Alex Scott; Benny Sudakov 2021-02-16
Exact m(n,k) for H-free k-colorability arxiv open Jacob Fox; Zoe Himwich; Nitya Mani 2021-03-19
Exponential sunflower bound for bounded VC-dimension arxiv partial Jacob Fox; Janos Pach; Andrew Suk 2021-03-25
F-counting lemma in C₄-free graphs arxiv open David Conlon; Jacob Fox; Benny Sudakov; Yufei Zhao 2021-06-06
FO minimization PTAS in treewidth-fragile classes arxiv open Zdeněk Dvořák 2021-10-09
FO-definable maximization in nowhere-dense classes arxiv open Zdeněk Dvořák 2021-10-09
FPT FO model checking superclass of twin-width arxiv partial Édouard Bonnet; Eun Jung Kim; Stéphan Thomassé; Rémi Watrigant 2021-10-25
Friends-and-Strangers FS(X,Y) isolated-vertex cutoff coincidence arxiv solved Noga Alon; Colin Defant; Noah Kravitz 2021-06-15
Grid arithmetic progression discrepancy tightness arxiv partial Jacob Fox; Max Wenqiang Xu; Yunkun Zhou 2021-10-28
Hat guessing number bounded by degeneracy arxiv open Noga Alon; Jeremy Chizewer 2021-07-21
Hat guessing number growth in G(n,1/2) arxiv partial Noga Alon; Jeremy Chizewer 2021-07-21
Hat guessing number under universal vertex addition arxiv open Noga Alon; Jeremy Chizewer 2021-07-21
Horizontal uniformity of runsort permuton density arxiv open Noga Alon; Colin Defant; Noah Kravitz 2021-06-28
Irregular spanning subgraph with minimum degree bound arxiv partial Noga Alon; Fan Wei 2021-08-06
Isolated-vertex threshold for FS(X,Y) connectivity arxiv partial Noga Alon; Colin Defant; Noah Kravitz 2021-06-15
k-planar partition bound tightness for convex sets arxiv open Oswin Aichholzer; Johannes Obenaus; Joachim Orthaber; Rosna Paul; Patrick Schnider; Raphael Steiner; Tim Taubner; Birgit Vogtenhuber 2021-12-15
Known forests for Esperet's polynomial χ-boundedness arxiv disproved Alex Scott; Paul Seymour; Sophie Spirkl 2021-07-25
Linear expected faces in random orientable embeddings arxiv solved Jesse Campion Loth; Kevin Halasz; Tomáš Masařík; Bojan Mohar; Robert Šámal 2021-10-06
Linearity of g(q) in divisible subdivisions arxiv solved Noga Alon; Michael Krivelevich 2021-06-29
MIS vs. Min Dominating Set approximability gap arxiv partial Édouard Bonnet; Colin Geniet; Eun Jung Kim; Stéphan Thomassé; Rémi Watrigant 2021-02-12
n/polylog(n) bound for ordered pure pairs arxiv open Alex Scott; Paul Seymour; Sophie Spirkl 2021-01-10
Near-uniform degree distribution in regular spanning subgraphs arxiv partial Noga Alon; Fan Wei 2021-08-06
O(√n) balanced separator for U_t arxiv open Tony Huynh; Bojan Mohar; Robert Šámal; Carsten Thomassen; David R. Wood 2021-09-01
Odd cycle Ramsey multiplicity exact formula arxiv open David Conlon; Jacob Fox; Benny Sudakov; Fan Wei 2021-09-20
Optimal asymmetric list sizes in bipartite graphs arxiv open Noga Alon; Stijn Cambie; Ross J. Kang 2021-08-30
Optimal degree bounds for c-crossing-critical graphs arxiv open Drago Bokal; Zdeněk Dvořák; Petr Hliněný; Jesús Leaños; Bojan Mohar; Tilo Wiedera 2021-05-05
Order of fₖ(N; s, t) in hypergraph Turán arxiv open Jacob Fox; Xiaoyu He 2021-03-18
Pervasiveness of forests of lanterns arxiv open Maria Chudnovsky; Alex Scott; Paul Seymour 2021-05-21
Petersen and dodecahedral countability in C₄-free arxiv open David Conlon; Jacob Fox; Benny Sudakov; Yufei Zhao 2021-06-06
Planar near-cubic 5-distance coloring cone membership arxiv open Zdeněk Dvořák; Bernard Lidický 2021-10-25
Polynomial bound for x₁+x₂+2x₃=x₄+3x₅ sets arxiv open David Conlon; Jacob Fox; Benny Sudakov; Yufei Zhao 2021-09-25
Polynomial expansion implies bounded twin-width arxiv open Édouard Bonnet; Eun Jung Kim; Stéphan Thomassé; Rémi Watrigant 2021-10-25
Polynomial Kempe connectivity in degenerate graphs arxiv open Marthe Bonamy; Vincent Delecroix; Clément Legrand-Duchesne 2021-12-04
Polynomial minimal separators via k-creature exclusion arxiv disproved Tara Abrishami; Maria Chudnovsky; Cemil Dibek; Stéphan Thomassé; Nicolas Trotignon; Kristina Vušković 2021-12-28
Polynomial weak coloring numbers for thin intersection graphs arxiv open Zdeněk Dvořák; Jakub Pekárek; Torsten Ueckerdt; Yelena Yuditsky 2021-04-07
PTAS for weighted Minimum Vertex Cover in fragile classes arxiv open Zdeněk Dvořák; Abhiruk Lahiri 2021-05-04
q-divisible subdivision f(H,q) growth rate arxiv solved Noga Alon; Michael Krivelevich 2021-06-29
Quadratic lower bound for map isomorphism arxiv open Ken-ichi Kawarabayashi; Bojan Mohar; Roman Nedela; Peter Zeman 2021-01-07
Ramsey rate for link hypergraphs via odd girth arxiv open Jacob Fox; Xiaoyu He 2021-03-18
Randomized star-contraction clique minor strategy arxiv open M. Bucić; J. Fox; B. Sudakov 2021-02-08
Sharp rank bounds for powers-of-two matrices arxiv open Noga Alon; Jozsef Solymosi 2021-09-01
Sharpness of h(n,k,Kᵣ) upper bound arxiv open Jacob Fox; Zoe Himwich; Nitya Mani 2021-03-19
Sharpness of n^{3/2} bound for C₅-free triangle-free arxiv open David Conlon; Jacob Fox; Benny Sudakov; Yufei Zhao 2021-09-25
Subexponential lower bound for triangle-free planar 3-colorings arxiv open Zdeněk Dvořák; Luke Postle 2021-08-28
Sublinear separators imply fractional treewidth-fragility arxiv open Zdeněk Dvořák 2021-10-09
Superlinear lower bound for map isomorphism arxiv open Ken-ichi Kawarabayashi; Bojan Mohar; Roman Nedela; Peter Zeman 2021-01-07
Tight bound on odd-wheel-free k-colorability arxiv open Jacob Fox; Zoe Himwich; Nitya Mani 2021-03-19
Unavoidability characterization via Kelly minors arxiv open Tony Huynh; Gwenaël Joret; Piotr Micek; Michał T. Seweryn; Paul Wollan 2021-04-06
Unavoidable minor characterization for poset covers arxiv open Tony Huynh; Gwenaël Joret; Piotr Micek; Michał T. Seweryn; Paul Wollan 2021-04-06
Universal ladder-bumping constant N₀ arxiv open Tony Huynh; Gwenaël Joret; Piotr Micek; Michał T. Seweryn; Paul Wollan 2021-04-06
Weak diameter 2-coloring near non-triangular faces arxiv open Zdeněk Dvořák; Sergey Norin 2021-11-13
Zombie number increase via subdivision arxiv open Valentin Bartier; Laurine Bénéteau; Marthe Bonamy; Hoang La; Jonathan Narboni 2021-06-03
Zombie number invariance under leaf attachment arxiv open Valentin Bartier; Laurine Bénéteau; Marthe Bonamy; Hoang La; Jonathan Narboni 2021-06-03
χ_ISC strict inequality for non-complete graphs arxiv open Marthe Bonamy; Kitty Meeks 2021-01-06
χ_ℓ ≤ 2t for K_t-minor-free graphs arxiv open Raphael Steiner 2021-10-18
Binary focal family upper bound non-tightness arxiv partial Noga Alon; Ron Holzman 2020-10-12
Bounded Expansion via Hall Ratio in Shallow Minors arxiv open Zdeněk Dvořák; Patrice Ossona de Mendez; Hehui Wu 2020-01-30
Bounded queue-number for layered treewidth graphs arxiv open Vida Dujmović; David Eppstein; Gwenaël Joret; Pat Morin; David R. Wood 2020-06-04
Bounded treewidth for degree-t theta-triangle-free graphs arxiv solved Marcin Pilipczuk; Ni Luh Dewi Sintiari; Stéphan Thomassé; Nicolas Trotignon 2020-10-27
Bounded treewidth for even-hole K₄ diamond-free graphs arxiv partial Marcin Pilipczuk; Ni Luh Dewi Sintiari; Stéphan Thomassé; Nicolas Trotignon 2020-10-27
Bounded twin-width for polynomial expansion classes arxiv open Édouard Bonnet; Colin Geniet; Eun Jung Kim; Stéphan Thomassé; Rémi Watrigant 2020-06-17
Bounded-degree even-hole-free tree-width arxiv solved Pierre Aboulker; Isolde Adler; Eun Jung Kim; Ni Luh Dewi Sintiari; Nicolas Trotignon 2020-08-12
Circular F-colourability complexity dichotomy arxiv partial Winfried Hochstättler; Felix Schröder; Raphael Steiner 2020-01-09
Cliquewidth of triangle, S₁,₂,₃-free graphs arxiv open Marcin Pilipczuk; Ni Luh Dewi Sintiari; Stéphan Thomassé; Nicolas Trotignon 2020-10-27
Coloring abundance predicts reflexivity in cubic graphs arxiv open Fiachra Knox; Bojan Mohar; Nathan Singer 2020-04-14
Combinatorial MIS algorithm for perfect graphs arxiv partial Maria Chudnovsky; Marcin Pilipczuk; Michał Pilipczuk; Stéphan Thomassé 2020-01-16
Combinatorial MWIS algorithm for perfect graphs arxiv partial Tara Abrishami; Maria Chudnovsky; Marcin Pilipczuk; Paweł Rzążewski; Paul Seymour 2020-03-11
Complexity of fractional dichromatic number ≤ p arxiv open Winfried Hochstättler; Felix Schröder; Raphael Steiner 2020-01-09
Conflict k-colouring on surfaces of genus g arxiv open Zdeněk Dvořák; Louis Esperet; Ross J. Kang; Kenta Ozeki 2020-10-09
Crossing number of Kₙ minus t-matching arxiv open Bojan Mohar 2020-09-07
Degree-weighted independence vs Hall ratio gap arxiv solved Zdeněk Dvořák; Patrice Ossona de Mendez; Hehui Wu 2020-01-30
Directed Kneser graph existence for b-tuple colourings arxiv open Winfried Hochstättler; Felix Schröder; Raphael Steiner 2020-01-09
Distant precoloring extension in plane triangle-free graphs arxiv open Zdenek Dvorak; Daniel Kral; Robin Thomas 2020-04-15
Edge-EP property for planar J-expansions arxiv open Wouter Cames van Batenburg; Gwenaël Joret; Arthur Ulmer 2020-06-08
Even directed circuit in oriented matroids arxiv open Karl Heuer; Raphael Steiner; Sebastian Wiederrecht 2020-10-18
Exact value of separator exponent b_ε arxiv open Zdeněk Dvořák 2020-07-07
Expansion-corruption detection gap in networks arxiv open Noga Alon; Elchanan Mossel; Robin Pemantle 2020-03-12
Exponential flows in 3-edge-connected oriented graphs arxiv open Matt DeVos; Rikke Langhede; Bojan Mohar; Robert Šámal 2020-05-19
Extremal mutually annihilating pairs in exterior algebra arxiv open Alex Scott; Elizabeth Wilmer 2020-07-14
Extremal self-annihilating subspaces in exterior algebra arxiv open Alex Scott; Elizabeth Wilmer 2020-07-14
Fixed-ℓ long odd hole detection complexity arxiv open Maria Chudnovsky; Alex Scott; Paul Seymour 2020-09-06
Forest-filleting of coherent ideals arxiv open Maria Chudnovsky; Alex Scott; Paul Seymour; Sophie Spirkl 2020-06-02
FPT Algorithm for MWIS in (Long-Hole, k-Prism)-Free Graphs arxiv open Maria Chudnovsky; Marcin Pilipczuk; Michał Pilipczuk; Stéphan Thomassé 2020-01-16
FPT on H_{t,t}-free graphs for Grundy Coloring arxiv open Pierre Aboulker; Édouard Bonnet; Eun Jung Kim; Florian Sikora 2020-01-11
Fractional vertex-arboricity ≤ 2 planar graphs arxiv open Marthe Bonamy; František Kardoš; Tom Kelly; Luke Postle 2020-09-25
Grundy Coloring FPT on K_{t,t}-free graphs arxiv solved Pierre Aboulker; Édouard Bonnet; Eun Jung Kim; Florian Sikora 2020-01-11
Hat guessing number graph parameter bounds arxiv partial Noga Alon; Omri Ben-Eliezer; Chong Shangguan; Itzhak Tamo 2020-01-15
Hat guessing number of complete bipartite graphs arxiv open Noga Alon; Omri Ben-Eliezer; Chong Shangguan; Itzhak Tamo 2020-01-15
Heavy path extension for long odd holes arxiv open Maria Chudnovsky; Alex Scott; Paul Seymour 2020-09-06
Heroic sets for bounded dichromatic number arxiv partial Pierre Aboulker; Pierre Charbit; Reza Naserasr 2020-09-28
Heroic triple characterization via transitive tournaments arxiv partial Pierre Aboulker; Pierre Charbit; Reza Naserasr 2020-09-28
Heroic triple with oriented forest and K_k arxiv partial Pierre Aboulker; Pierre Charbit; Reza Naserasr 2020-09-28
Hoppers existence for large Euler genus arxiv open Bojan Mohar; Petr Škoda 2020-02-01
Independence ratio of Mycielski graphs arxiv open Marthe Bonamy; Pierre Charbit; Oscar Defrain; Gwenaël Joret; Aurélie Lagoutte; Vincent Limouzy; Lucas Pastor; Jean-Sébastien Sereni 2020-03-23
Induced wall in bounded-degree high tree-width graphs arxiv solved Pierre Aboulker; Isolde Adler; Eun Jung Kim; Ni Luh Dewi Sintiari; Nicolas Trotignon 2020-08-12
K₃ polynomial anticomplete pair property arxiv open Maria Chudnovsky; Jacob Fox; Alex Scott; Paul Seymour; Sophie Spirkl 2020-12-07
Largest symmetric intersecting families set-intersecting arxiv open Sean Eberhard; Jeff Kahn; Bhargav Narayanan; Sophie Spirkl 2020-07-31
Linear anticomplete pairs in sparse H-free graphs arxiv partial Maria Chudnovsky; Jacob Fox; Alex Scott; Paul Seymour; Sophie Spirkl 2020-12-07
Linear diameter of 6-recoloring, girth-5 planar graphs arxiv partial Zdeněk Dvořák; Carl Feghali 2020-06-16
Linear diameter of planar graph reconfigurations arxiv partial Zdeněk Dvořák; Carl Feghali 2020-02-13
Linear-time 3-coloring output on surfaces arxiv open Zdenek Dvorak; Daniel Kral; Robin Thomas 2020-11-05
List Ramsey R_ℓ(K_{1,2}, k) parity gap arxiv open N. Alon; M. Bucić; T. Kalvari; E. Kuperwasser; T. Szabó 2020-08-12
List vs ordinary Ramsey number equality for Kᵣ arxiv open N. Alon; M. Bucić; T. Kalvari; E. Kuperwasser; T. Szabó 2020-08-12
Local concentration of subgraph counts in G(n,p) arxiv partial Jacob Fox; Matthew Kwan; Lisa Sauermann 2020-11-18
Maximum symmetric intersecting family in [k]^n arxiv open Sean Eberhard; Jeff Kahn; Bhargav Narayanan; Sophie Spirkl 2020-07-31
Minimal complement count T(n) square-root growth arxiv open Noga Alon; Noah Kravitz; Matt Larson 2020-12-30
Minimal heroic tournament set classification arxiv open Pierre Aboulker; Pierre Charbit; Reza Naserasr 2020-09-28
MIS approximation exponent in H-free graphs arxiv open Édouard Bonnet; Stéphan Thomassé; Xuan Thang Tran; Rémi Watrigant 2020-04-25
MIS complexity for (even hole, K₄)-free graphs arxiv open Marcin Pilipczuk; Ni Luh Dewi Sintiari; Stéphan Thomassé; Nicolas Trotignon 2020-10-27
MIS complexity for S_{i,j,k}-free graphs with P₇ arxiv partial Marcin Pilipczuk; Ni Luh Dewi Sintiari; Stéphan Thomassé; Nicolas Trotignon 2020-10-27
MIS sub-polynomial approximation in H-free graphs arxiv open Édouard Bonnet; Stéphan Thomassé; Xuan Thang Tran; Rémi Watrigant 2020-04-25
Moderate deviation rates in sparse G(n,m) arxiv partial Christina Goldschmidt; Simon Griffiths; Alex Scott 2020-02-10
MWIS complexity in P₇-free graphs arxiv partial Tara Abrishami; Maria Chudnovsky; Marcin Pilipczuk; Paweł Rzążewski; Paul Seymour 2020-03-11
n^{5/2} threshold for 3-graph homeomorphs arxiv partial Peter Keevash; Jason Long; Bhargav Narayanan; Alex Scott 2020-04-06
Near-sunflower exponential bound for k-uniform families arxiv open Noga Alon; Ron Holzman 2020-10-12
Neighbour sum distinguishing edge colouring Δ+O(1) bound arxiv open Gwenaël Joret; William Lochet 2020-07-22
NP-completeness of circular F-coloring arxiv partial Winfried Hochstättler; Felix Schröder; Raphael Steiner 2020-01-09
One-sided sublinear separator expansion equality arxiv open Zdeněk Dvořák 2020-07-07
Optimal solid maximal supplement bound in abelian groups arxiv open Noga Alon; Noah Kravitz; Matt Larson 2020-12-30
Outerplanar strongly perfect graph characterization arxiv open Maria Chudnovsky; Cemil Dibek; Paul Seymour 2020-03-04
Parameterized complexity of Partial Grundy Coloring arxiv solved Pierre Aboulker; Édouard Bonnet; Eun Jung Kim; Florian Sikora 2020-01-11
Pentagon contact representation algorithm termination arxiv open Stefan Felsner; Hendrik Schrezenmaier; Raphael Steiner 2020-04-13
Poly-time excess-3 induced st-path detection arxiv open Maria Chudnovsky; Alex Scott; Paul Seymour 2020-09-06
Polynomial algorithm for fixed-k induced detours arxiv open Eli Berger; Paul Seymour; Sophie Spirkl 2020-05-26
Polynomial detection of holes mod 3 arxiv open Linda Cook; Paul Seymour 2020-09-12
Polynomial gain on symmetric intersecting vector families arxiv open Sean Eberhard; Jeff Kahn; Bhargav Narayanan; Sophie Spirkl 2020-07-31
Polynomial-time 4-colorability on fixed surfaces arxiv open Zdenek Dvorak; Daniel Kral; Robin Thomas 2020-08-04
Probabilistic barrier for adjacent distinguishing Δ+2 arxiv open Gwenaël Joret; William Lochet 2020-07-22
Proper-incident short rainbow cycle bound arxiv open Matt DeVos; Matthew Drescher; Daryl Funk; Sebastián González Hermosillo de la Maza; Krystal Guo; Tony Huynh; Bojan Mohar; Amanda Montejano 2020-05-07
Q(s,r) asymptotics for growing s and r arxiv open Noga Alon; Ryan Alweiss 2020-02-26
Sharpness of ¼g cop-number exponent arxiv open Peter Bradshaw; Seyyed Aliasghar Hosseini; Bojan Mohar; Ladislav Stacho 2020-05-21
Short rainbow circuits in rank-(n-1) matroids arxiv partial Matt DeVos; Matthew Drescher; Daryl Funk; Sebastián González Hermosillo de la Maza; Krystal Guo; Tony Huynh; Bojan Mohar; Amanda Montejano 2020-05-07
Shortest even hole detection arxiv solved Linda Cook; Paul Seymour 2020-09-12
Small hereditary class twin-width converse arxiv disproved Édouard Bonnet; Colin Geniet; Eun Jung Kim; Stéphan Thomassé; Rémi Watrigant 2020-06-17
Sparse pairs in H-free ε-bounded graphs arxiv partial Maria Chudnovsky; Jacob Fox; Alex Scott; Paul Seymour; Sophie Spirkl 2020-12-07
Symmetry of biconstrained ψ function arxiv open Maria Chudnovsky; Patrick Hompe; Alex Scott; Paul Seymour; Sophie Spirkl 2020-12-07
T(p) upper bound for prime groups arxiv open Noga Alon; Noah Kravitz; Matt Larson 2020-12-30
Tame representation for polynomial strong coloring numbers arxiv open Zdenek Dvorak; Rose McCarty; Sergey Norin 2020-01-06
Tame representation impossible for bounded col_r graphs arxiv open Zdenek Dvorak; Rose McCarty; Sergey Norin 2020-01-06
Threshold for minimal complements in finite groups arxiv open Noga Alon; Noah Kravitz; Matt Larson 2020-12-30
Tight bound characterisation of φ(x,y) arxiv open Maria Chudnovsky; Patrick Hompe; Alex Scott; Paul Seymour; Sophie Spirkl 2020-12-07
Unavoidable G-dependence in blowup Ramsey prefactor arxiv solved Jacob Fox; Sammy Luo; Yuval Wigderson 2020-04-06
ε-t-net size and computation arxiv open Noga Alon; Bruno Jartoux; Chaya Keller; Shakhar Smorodinsky; Yelena Yuditsky 2020-03-16
χ-bounded hereditary class without polynomial bound arxiv solved Marthe Bonamy; Michał Pilipczuk 2020-07-07
χ_f to Hall ratio gap growth rate arxiv partial Zdeněk Dvořák; Patrice Ossona de Mendez; Hehui Wu 2020-01-30
√d log n bound for degenerate single-conflict chromatic number arxiv solved Zdeněk Dvořák; Louis Esperet; Ross J. Kang; Kenta Ozeki 2020-10-09
1-ball reconstruction threshold gap in Qₙ arxiv open Michał Przykucki; Alexander Roberts; Alex Scott 2019-07-16
1/e upper bound on ind(k,ℓ) arxiv solved Noga Alon; Dan Hefetz; Michael Krivelevich; Mykhaylo Tyomkyn 2019-11-01
11/3 non-tight fractional chromatic bound for {C₄,C₅}-free planar arxiv partial Zdeněk Dvořák; Xiaolan Hu 2019-07-14
2-approximation for Cluster Vertex Deletion arxiv solved Samuel Fiorini; Gwenaël Joret; Oliver Schaudt 2019-02-22
3-colourability complexity of P_t-free graphs arxiv partial Carla Groenland; Karolina Okrasa; Pawel Rzążewski; Alex Scott; Paul Seymour; Sophie Spirkl 2019-03-22
Asymmetric out-degree girth bound for bipartite digraphs arxiv open Paul Seymour; Sophie Spirkl 2019-07-24
Avoidable non-path family existence arxiv partial Marthe Bonamy; Oscar Defrain; Meike Hatzel; Jocelyn Thiebaut 2019-08-10
Behrend-style sets avoiding mixed-sign affine patterns arxiv open Jacob Fox; Ashwin Sah; Mehtaab Sawhney; David Stoner; Yufei Zhao 2019-07-02
Bipartite Caccetta–Häggkvist short cycle arxiv partial Paul Seymour; Sophie Spirkl 2019-07-24
Characterization of (CC) for coloring parameters arxiv open Zdeněk Dvořák; Jakub Pekárek; Jean-Sébastien Sereni 2019-02-26
Clique-Width Boundedness for Five Open Pairs arxiv open Marthe Bonamy; Nicolas Bousquet; Konrad K. Dabrowski; Matthew Johnson; Daniël Paulusma; Théo Pierron 2019-09-03
Combinatorial MIS algorithm on perfect graphs arxiv open Edin Husic; Stephan Thomasse; Nicolas Trotignon 2019-10-06
Disjoint avoidable Pₖ pairs existence arxiv disproved Marthe Bonamy; Oscar Defrain; Meike Hatzel; Jocelyn Thiebaut 2019-08-10
Disproportionate bipartition of measures on S¹ arxiv open Logan Crew; Bhargav Narayanan; Sophie Spirkl 2019-09-16
Disproportionate division requires 2n−2 cuts arxiv open Logan Crew; Bhargav Narayanan; Sophie Spirkl 2019-09-16
Erdős–Pósa constant dependence on |H| arxiv open Wouter Cames van Batenburg; Tony Huynh; Gwenaël Joret; Jean-Florent Raymond 2019-10-23
Exponential constant in r(n,m) for 𝔽₃ⁿ subspaces arxiv open Jacob Fox; Huy Tuan Pham 2019-11-21
FPT candidates for H-free MIS nearly all tractable arxiv open Édouard Bonnet; Nicolas Bousquet; Stéphan Thomassé; Rémi Watrigant 2019-09-18
FPT MIS in P(t,t,t,t)-free graphs arxiv open Édouard Bonnet; Nicolas Bousquet; Stéphan Thomassé; Rémi Watrigant 2019-09-18
Fractional chromatic number of {C₄,C₅}-free planar graphs arxiv partial Zdeněk Dvořák; Xiaolan Hu 2019-07-14
fvs–face-packing ratio in planar graphs arxiv open Marthe Bonamy; François Dross; Tomáš Masařík; Wojciech Nadara; Marcin Pilipczuk; Michał Pilipczuk 2019-12-03
GI complexity dichotomy for (H₁,H₂)-free graphs arxiv open Marthe Bonamy; Nicolas Bousquet; Konrad K. Dabrowski; Matthew Johnson; Daniël Paulusma; Théo Pierron 2019-09-03
Graph Isomorphism FPT by Clique-Width arxiv open Marthe Bonamy; Nicolas Bousquet; Konrad K. Dabrowski; Matthew Johnson; Daniël Paulusma; Théo Pierron 2019-09-03
Independence number lower bound in K_{t+1}-minor-free graphs arxiv open Zdeněk Dvořák; Liana Yepremyan 2019-07-30
Induced arithmetic removal for higher complexity patterns arxiv open Jacob Fox; Jonathan Tidor; Yufei Zhao 2019-11-08
Induced arithmetic removal over abelian groups arxiv open Jacob Fox; Jonathan Tidor; Yufei Zhao 2019-11-08
Inducibility upper bound 1/e for non-trivial graphs arxiv solved Noga Alon; Dan Hefetz; Michael Krivelevich; Mykhaylo Tyomkyn 2019-11-01
Largest minor-closed class dichromatic number 2 arxiv open Raphael Steiner 2019-06-30
LB and QLB constant-factor equivalence for posets arxiv open Jean Cardinal; Gwenaël Joret; Jérémie Roland 2019-02-18
Mandache corner bound for all abelian groups arxiv solved Jacob Fox; Ashwin Sah; Mehtaab Sawhney; David Stoner; Yufei Zhao 2019-07-02
MIS complexity in even-hole-free graphs arxiv partial Maria Chudnovsky; Stéphan Thomassé; Nicolas Trotignon; Kristina Vušković 2019-12-24
MIS dichotomy for path- and claw-subdivision-free graphs arxiv partial Édouard Bonnet; Nicolas Bousquet; Stéphan Thomassé; Rémi Watrigant 2019-09-18
MIS FPT in Pℓ(t)-free Graphs arxiv open Édouard Bonnet; Nicolas Bousquet; Stéphan Thomassé; Rémi Watrigant 2019-09-18
MIS parameterized complexity in H-free graphs arxiv partial Édouard Bonnet; Nicolas Bousquet; Stéphan Thomassé; Rémi Watrigant 2019-09-18
Mixed-parity components in disconnected 4-coloring complexes arxiv open Bojan Mohar; Nathan Singer 2019-12-16
MR_t(s,k) bound for Ks-free graphs arxiv open Zdeněk Dvořák; Liana Yepremyan 2019-07-30
Optimal cycle count bound via edge number arxiv open Zdeněk Dvořák; Natasha Morrison; Jonathan A. Noel; Sergey Norin; Luke Postle 2019-07-28
Optimal threshold for ℤᵈ lattice list-colorability arxiv open Noga Alon; Raimundo Briceño; Nishant Chandgotia; Alexander Magazinov; Yinon Spinka 2019-12-25
Polynomial clique/independent set in bounded VC-dimension graphs arxiv solved Jacob Fox; Janos Pach; Andrew Suk 2019-12-05
Polynomial minimal separators in (prism,pyramid,theta,turtle)-free graphs arxiv solved Maria Chudnovsky; Stéphan Thomassé; Nicolas Trotignon; Kristina Vušković 2019-12-24
Polynomial minimal separators in odd-hole-free graphs arxiv partial Maria Chudnovsky; Stéphan Thomassé; Nicolas Trotignon; Kristina Vušković 2019-12-24
Polynomial recognition of Switchable graphs arxiv open Marthe Bonamy; Nicolas Bousquet; Marc Heinrich; Takehiro Ito; Yusuke Kobayashi; Arnaud Mary; Moritz Mühlenthaler; Kunihiro Wasa 2019-04-12
Polynomial δ-ε dependence for complexity 1 systems arxiv open Jacob Fox; Jonathan Tidor; Yufei Zhao 2019-11-08
Polynomial-time bounded sub-determinant integer programs arxiv partial Michele Conforti; Samuel Fiorin; Tony Huynh; Gwenaël Joret; Stefan Weltge 2019-08-17
Polynomial-time MIS on Pₜ-free graphs arxiv partial Carla Groenland; Karolina Okrasa; Pawel Rzążewski; Alex Scott; Paul Seymour; Sophie Spirkl 2019-03-22
Prime p-entropic matroids are F_p-representable arxiv open Emmanuel Abbe; Sophie Spirkl 2019-09-26
PTAS for monotone FO optimization via local search arxiv partial Zdeněk Dvořák 2019-01-07
Quantum ergodicity failure in narrow spectral windows arxiv open Noga Alon; Shirshendu Ganguly; Nikhil Srivastava 2019-08-10
Stable set for bounded ocp, unbounded genus arxiv open Michele Conforti; Samuel Fiorin; Tony Huynh; Gwenaël Joret; Stefan Weltge 2019-08-17
T-decomposition by leaf count of trees arxiv open Tereza Klimošová; Stéphan Thomassé 2019-07-26
Tower height bounds for nₚ(α,β) at small primes arxiv open Jacob Fox; Huy Tuan Pham 2019-11-21
Triangle count bound via book number in dense graphs arxiv partial David Conlon; Jacob Fox; Benny Sudakov 2019-10-20
Widespread multigraph conjecture arxiv open Alex Scott; Paul Seymour 2019-08-27
α equals IR in multipartite direct products arxiv open Noga Alon; Colin Defant 2019-04-04
Θ(√m) excess for hypergraph r-cuts arxiv disproved David Conlon; Jacob Fox; Matthew Kwan; Benny Sudakov 2019-06-27
χ-boundedness for H-subdivision-free graphs arxiv open Alex Scott; Paul Seymour 2019-08-27
χ-boundedness of binary matroids excluding I_s and PG(1,2) arxiv partial Marthe Bonamy; Frantisek Kardos; Tom Kelly; Peter Nelson; Luke Postle 2019-11-13
χ₂-boundedness via J-subdivision-free graphs arxiv open Alex Scott; Paul Seymour 2019-08-27
3-colourability of ternary graphs arxiv open Maria Chudnovsky; Alex Scott; Paul Seymour; Sophie Spirkl 2018-09-28
4-hole in controlled triangle-free graphs arxiv open Alex Scott; Paul Seymour 2018-02-12
5/6 bound induced 2-degenerate triangle-free planar arxiv open Zdeněk Dvořák; Tom Kelly 2018-02-19
Algebraic connectivity supremum for graph-complement pairs arxiv partial B. Afshari; S. Akbari; M. J. Moghaddamzadeh; B. Mohar 2018-06-18
Alteration method generalization for r̃(m,n) arxiv partial David Conlon; Jacob Fox; Andrey Grinshpun; Xiaoyu He 2018-11-04
Bounded-gap sets are constricting arxiv open Alex Scott; Paul Seymour 2018-02-12
Capture time bounds for genus-g graphs arxiv open Anthony Bonato; Bojan Mohar 2018-04-22
Clique count bound for Kₜ-immersion-free graphs arxiv open Jacob Fox; Fan Wei 2018-08-07
Clique or dense bipartite subgraph in high-degree graphs arxiv partial Louis Esperet; Ross J. Kang; Stéphan Thomassé 2018-12-04
Clustered chromatic number via treedepth bound arxiv partial Sergey Norin; Alex Scott; Paul Seymour; David R. Wood 2018-07-29
Consecutive hole lengths for bounded clique number arxiv open Alex Scott; Paul Seymour 2018-12-04
Consecutive holes in bounded clique number graphs arxiv open Alex Scott; Paul Seymour 2018-02-12
Constant-size separator M in bounded expansion arxiv open Zdeněk Dvořák 2018-02-09
Constricting set with density zero arxiv open Alex Scott; Paul Seymour 2018-02-12
Cop number dichotomy for outerplanar graphs arxiv open Anthony Bonato; Bojan Mohar 2018-04-22
Cop number partition of planar graphs arxiv open Anthony Bonato; Bojan Mohar 2018-04-22
Dense bipartite subgraph in triangle-free graphs arxiv solved Louis Esperet; Ross J. Kang; Stéphan Thomassé 2018-12-04
Diagonal and off-diagonal online random Ramsey growth rates arxiv open David Conlon; Jacob Fox; Andrey Grinshpun; Xiaoyu He 2018-11-04
Diameter-free bound for Euclidean Ramsey partition arxiv open David Conlon; Jacob Fox 2018-03-20
EGZ constant growth in (ℤ/kℤ)ⁿ fixed k arxiv open Jacob Fox; Lisa Sauermann 2018-04-17
Erdős–Pósa O(k log k) bound for planar H-minors arxiv solved Pierre Aboulker; Samuel Fiorini; Tony Huynh; Gwenaël Joret; Jean-Florent Raymond; Ignasi Sau 2018-07-05
Euclidean Ramsey unit-distance vs isometric copy arxiv partial David Conlon; Jacob Fox 2018-03-20
Exact exponent of maximal cliques in c-closed graphs arxiv open Jacob Fox; Tim Roughgarden; C. Seshadhri; Fan Wei; Nicole Wein 2018-04-20
Exact leading coefficient of maxcode_L even L arxiv open Noga Alon; Boris Bukh; Yury Polyanskiy 2018-05-14
Exponent gap for frozen (Δ+1)-colourings arxiv open Marthe Bonamy; Nicolas Bousquet; Guillem Perarnau 2018-11-30
Eⁿ non-arrow (ℓ₃, ℓ_m) for large m arxiv partial David Conlon; Jacob Fox 2018-03-20
Forest families eventually k-nice arxiv open Ron Aharoni; Noga Alon; Michal Amir; Penny Haxell; Dan Hefetz; Zilin Jiang; Gal Kronenberg; Alon Naor 2018-04-16
Forest-containing families are infinitely k-nice arxiv open Ron Aharoni; Noga Alon; Michal Amir; Penny Haxell; Dan Hefetz; Zilin Jiang; Gal Kronenberg; Alon Naor 2018-04-16
Glauber (Δ+1)-colouring mixing without Δ = o(n) arxiv open Marthe Bonamy; Nicolas Bousquet; Guillem Perarnau 2018-11-30
High-chromatic subgraph with large average degree arxiv open Bojan Mohar; Hehui Wu 2018-08-05
High-girth subgraphs with large χ_f arxiv open Bojan Mohar; Hehui Wu 2018-08-05
Improved hub color ratio in girth-five wheels arxiv open Zdeněk Dvořák; Xiaolan Hu 2018-09-14
Induced 2-degenerate ⅞ subgraph triangle-free planar arxiv open Zdeněk Dvořák; Tom Kelly 2018-02-19
Large Girth Dense Bipartite Induced Subgraph arxiv open Louis Esperet; Ross J. Kang; Stéphan Thomassé 2018-12-04
List chromatic bound via sublinear clique condition arxiv solved Marthe Bonamy; Tom Kelly; Peter Nelson; Luke Postle 2018-03-02
List-chromatic Reed bound arxiv open Marthe Bonamy; Tom Kelly; Peter Nelson; Luke Postle 2018-03-02
NP-completeness of vertex-disjoint paths, stability two arxiv open Maria Chudnovsky; Alex Scott; Paul Seymour 2018-12-23
NP-hardness of generalized Turán approximation arxiv open Noga Alon; Clara Shikhelman 2018-11-21
Optimal clique count exponent for K_t-subdivisions arxiv open Jacob Fox; Fan Wei 2018-08-07
Optimal exponent in arithmetic k-cycle removal arxiv partial Jacob Fox; László Miklós Lovász; Lisa Sauermann 2018-09-04
Optimal ε for sparse-neighbourhood chromatic bound arxiv partial Marthe Bonamy; Thomas Perrett; Luke Postle 2018-10-15
Polynomial 3-coloring for P_t-free graphs arxiv partial Maria Chudnovsky; Shenwei Huang; Sophie Spirkl; Mingxian Zhong 2018-07-02
Polynomial domination bound in triangle-free digraphs arxiv open Ararat Harutyunyan; Tien-Nam Le; Alantha Newman; Stéphan Thomassé 2018-04-27
Polynomial query complexity for permutation property testing arxiv open Jacob Fox; Fan Wei 2018-04-04
Polynomial δ Dependence in Rödl's Theorem arxiv partial Maria Chudnovsky; Jacob Fox; Alex Scott; Paul Seymour; Sophie Spirkl 2018-03-09
Randomized round complexity of Δ-list-coloring arxiv open Pierre Aboulker; Marthe Bonamy; Nicolas Bousquet; Louis Esperet 2018-12-19
Separation choosability grows with minimum degree arxiv open Louis Esperet; Ross J. Kang; Stéphan Thomassé 2018-12-04
Sparse Strong EH-property Characterizes Forests arxiv solved Anita Liebenau; Marcin Pilipczuk; Paul Seymour; Sophie Spirkl 2018-10-01
Sparsity of clique-bounded critical graphs arxiv partial Marthe Bonamy; Thomas Perrett; Luke Postle 2018-10-15
Subgraph query complexity for K_m arxiv partial David Conlon; Jacob Fox; Andrey Grinshpun; Xiaoyu He 2018-11-04
Sublinear round complexity for distributed coloring arxiv open Pierre Aboulker; Marthe Bonamy; Nicolas Bousquet; Louis Esperet 2018-12-19
Tightness of 3-cop capture time bound for planar graphs arxiv open Anthony Bonato; Bojan Mohar 2018-04-22
Treewidth packing with k log k bound arxiv open Pierre Aboulker; Samuel Fiorini; Tony Huynh; Gwenaël Joret; Jean-Florent Raymond; Ignasi Sau 2018-07-05
Treewidth-exponential extension complexity for correlation polytopes arxiv open Pierre Aboulker; Samuel Fiorini; Tony Huynh; Marco Macchia; Johanna Seif 2018-10-18
ε-flexibility of d-degenerate graphs with (d+1)-lists arxiv partial Zdeněk Dvořák; Sergey Norin; Luke Postle 2018-11-17
χ-boundedness via spaghetti and path-decomposition intersection arxiv open Stefan Felsner; Gwenaël Joret; Piotr Micek; William T. Trotter; Veit Wiechert 2018-01-29
ℤ₅-antisymmetric flow in k-edge-connected digraphs arxiv open Louis Esperet; Rémi de Joannis de Verclos; Tien-Nam Le; Stéphan Thomassé 2018-02-07
Additive chromatic approximation gap in K_k-minor-free arxiv open Zdeněk Dvořák; Ken-ichi Kawarabayashi 2017-07-12
Bounded queue number of planar graphs arxiv solved Gwenaël Joret; Piotr Micek; Veit Wiechert 2017-01-09
Bounded-norm bipartite Johnson-Lindenstrauss reduction arxiv open Noga Alon; Bo'az Klartag 2017-04-02
Chromatic concentration lower bound in G(n,p) arxiv solved Alex Scott 2017-10-18
Chromatic number of Kₖ-free bounded treewidth graphs arxiv open Zdeněk Dvořák; Ken-ichi Kawarabayashi 2017-06-09
col★ characterization for minor-closed classes arxiv open Zdeněk Dvořák; Sergey Norin 2017-10-07
Cop convergence on Riemannian surfaces arxiv partial Bojan Mohar 2017-10-31
Cop number finiteness on bounded Riemannian surfaces arxiv partial Bojan Mohar 2017-10-31
Cop number of Riemannian surfaces by genus arxiv solved Bojan Mohar 2017-10-31
Cop number √g growth rate by genus arxiv open Bojan Mohar 2017-10-31
Cops and Robbers on constant-curvature surfaces arxiv partial Bojan Mohar 2017-10-31
Dominating number forcing in tournament subtournaments arxiv open Ararat Harutyunyan; Tien-Nam Le; Stéphan Thomassé; Hehui Wu 2017-03-15
Fractional 3-coloring of triangle-free planar requests arxiv disproved Zdeněk Dvořák; Jean-Sébastien Sereni 2017-09-19
Independence number n/4 in planar graphs arxiv open Zdeněk Dvořák; Jordan Venters 2017-02-09
Independent Feedback Vertex Set linear forest complexity arxiv open Marthe Bonamy; Konrad K. Dabrowski; Carl Feghali; Matthew Johnson; Daniel Paulusma 2017-07-28
Independent set APX-hardness without sublinear separators arxiv open Zdeněk Dvořák 2017-04-01
Kₘ extremal threshold in H-free G(n,p) arxiv partial Noga Alon; Alexandr Kostochka; Clara Shikhelman 2017-11-19
Large domination number forces Sᵢ subtournament arxiv open Ararat Harutyunyan; Tien-Nam Le; Stéphan Thomassé; Hehui Wu 2017-03-15
Linear extension complexity for minor-closed families arxiv partial Samuel Fiorini; Tony Huynh; Gwenaël Joret; Kanstantsin Pashkovich 2017-01-09
Linear xc bound for bounded-genus spanning trees arxiv open Samuel Fiorini; Tony Huynh; Gwenaël Joret; Kanstantsin Pashkovich 2017-01-09
List-coloring bounded obstruction for girth-5 planar graphs arxiv open Zdenek Dvorak; Daniel Kral; Robin Thomas 2017-07-05
Maximum tight skew partitions in perfect graphs arxiv open Maria Chudnovsky; Aurélie Lagoutte; Paul Seymour; Sophie Spirkl 2017-07-12
Monotone interference growth with network depth arxiv open Noga Alon; Jonathan D. Cohen; Biswadip Dey; Tom Griffiths; Sebastian Musslick; Kayhan Ozcimder; Daniel Reichman; Igor Shinkar; Tal Wagner 2017-06-09
Multitasker threshold at average degree log n arxiv open Noga Alon; Jonathan D. Cohen; Biswadip Dey; Tom Griffiths; Sebastian Musslick; Kayhan Ozcimder; Daniel Reichman; Igor Shinkar; Tal Wagner 2017-06-09
Obstructions for Diplanar Quartic Eulerian Digraphs arxiv open Dan Archdeacon; Paul Bonnington; Bojan Mohar 2017-06-09
Polynomial dependence in ordered binary matrix removal arxiv partial Noga Alon; Omri Ben-Eliezer; Eldar Fischer 2017-04-07
Polynomial dimension bound for planar cover graph posets arxiv partial Gwenaël Joret; Piotr Micek; Veit Wiechert 2017-09-23
Polynomial error term in H-free clique maximization arxiv open Noga Alon; Clara Shikhelman 2017-06-18
Projective plane structure in near-extremal r-partite hypergraphs arxiv open Penny Haxell; Alex Scott 2017-10-06
Regularity-free ordered graph removal lemma arxiv partial Noga Alon; Omri Ben-Eliezer; Eldar Fischer 2017-04-07
s Consecutive Rainbow Vertices in Holes arxiv open Alex Scott; Paul Seymour 2017-07-03
Thin overlays without bounded-degree assumption arxiv open Zdeněk Dvořák 2017-04-01
Tight constant for clique chromatic G(n,½) arxiv solved Noga Alon; Michael Krivelevich 2017-11-05
Triangle-free χ additive approximation in minor-closed arxiv open Zdeněk Dvořák; Ken-ichi Kawarabayashi 2017-07-12
Uniquely-covered induced path in triangle-free graphs arxiv open Alex Scott; Paul Seymour 2017-07-03
VC-dimension dichotomy for identifying codes approximation arxiv open Nicolas Bousquet; Aurélie Lagoutte; Zhentao Li; Aline Parreau; Stéphan Thomassé 2017-04-14
Worst fixed-genus surface for cop number arxiv open Bojan Mohar 2017-10-31
3-Choosability of Planar Graphs Forbidding C₄–C₆ arxiv open Zdenek Dvorak; Luke Postle 2016-10-08
4-colorability on fixed surfaces complexity arxiv open Zdenek Dvorak; Dan Kral; Robin Thomas 2016-03-04
5/4 n TSP walk bound for subcubic graphs arxiv solved Zdenek Dvorak; Daniel Kral; Bojan Mohar 2016-09-05
Block tree diameter gap beyond √(log n) arxiv solved Colin McDiarmid; Alex Scott 2016-05-16
Bridge path-elongation structure of ℓ(G)+br(G) counterexamples arxiv open Pierre Aboulker; Martin Matamala; Paul Rochet; Jose Zamora 2016-06-20
Closure of δ⁺-maderian digraphs under disjoint union arxiv open Pierre Aboulker; Nathann Cohen; Fréderic Havet; William Lochet; Phablo F. S. Moura; Stéphan Thomassé 2016-10-04
Cone graph crossing f_s(k) k^(3/4) asymptotic arxiv open Carlos A. Alfaro; Alan Arroyo; Marek Derunár; Bojan Mohar 2016-08-27
Correspondence chromatic number planar graphs C₄–C₈-free arxiv solved Zdenek Dvorak; Luke Postle 2016-10-08
Crossing bound for 2-page extension of 1-page drawing arxiv open Carlos A. Alfaro; Alan Arroyo; Marek Derunár; Bojan Mohar 2016-08-27
Edge-contraction clique-monotone graph characterization arxiv open Jacob Fox; Fan Wei 2016-03-23
Exact value of mader_χ̄(K̄ₙ) arxiv open Pierre Aboulker; Nathann Cohen; Fréderic Havet; William Lochet; Phablo F. S. Moura; Stéphan Thomassé 2016-10-04
Extremal cone crossing number function arxiv partial Carlos A. Alfaro; Alan Arroyo; Marek Derunár; Bojan Mohar 2016-08-27
Fair Matching Representation in K_{n,n} Partition arxiv partial Ron Aharoni; Noga Alon; Eli Berger; Maria Chudnovsky; Dani Kotlar; Martin Loebl; Ran Ziv 2016-11-10
Fair matching representation via edge partition arxiv open Ron Aharoni; Noga Alon; Eli Berger; Maria Chudnovsky; Dani Kotlar; Martin Loebl; Ran Ziv 2016-11-10
Fair representation matching in bipartite graphs arxiv open Ron Aharoni; Noga Alon; Eli Berger; Maria Chudnovsky; Dani Kotlar; Martin Loebl; Ran Ziv 2016-11-10
Finite exceptions to ℓ(G)+br(G)≥|G| arxiv open Pierre Aboulker; Martin Matamala; Paul Rochet; Jose Zamora 2016-06-20
Forb(H) χ-bounded iff H is forest arxiv partial Pierre Aboulker; Jørgen Bang-Jensen; Nicolas Bousquet; Pierre Charbit; Frédéric Havet; Frédéric Maffray; Jose Zamora 2016-05-24
Fractional majority colouring weight below 3 arxiv partial Stephan Kreutzer; Sang-il Oum; Paul Seymour; Dominic van der Zypen; David R. Wood 2016-08-10
Gallai path decomposition beyond odd semi-cliques arxiv partial Marthe Bonamy; Thomas Perrett 2016-09-20
k-coloring complexity for maximally locally connected graphs arxiv open Pierre Aboulker; Nick Brettell; Frédéric Havet; Dániel Marx; Nicolas Trotignon 2016-10-14
l=1 case of Set Mapping Theorem arxiv open David Conlon; Jacob Fox; Benny Sudakov 2016-02-11
Majority 1/k out-neighbour colouring digraphs arxiv disproved Stephan Kreutzer; Sang-il Oum; Paul Seymour; Dominic van der Zypen; David R. Wood 2016-08-10
Majority 2-coloring recognition complexity arxiv partial Stephan Kreutzer; Sang-il Oum; Paul Seymour; Dominic van der Zypen; David R. Wood 2016-08-10
Majority 3-coloring of digraphs arxiv partial Stephan Kreutzer; Sang-il Oum; Paul Seymour; Dominic van der Zypen; David R. Wood 2016-08-10
Majority 3-coloring of Eulerian digraphs arxiv open Stephan Kreutzer; Sang-il Oum; Paul Seymour; Dominic van der Zypen; David R. Wood 2016-08-10
Majority 3-coloring of tournaments arxiv open Stephan Kreutzer; Sang-il Oum; Paul Seymour; Dominic van der Zypen; David R. Wood 2016-08-10
Majority choosability constant for digraphs arxiv solved Stephan Kreutzer; Sang-il Oum; Paul Seymour; Dominic van der Zypen; David R. Wood 2016-08-10
Maximum order of (c,s)-normal graphs arxiv open David Gajser; Bojan Mohar 2016-01-06
Normality of G(n,p) with high probability arxiv open David Gajser; Bojan Mohar 2016-01-06
Ordered Ramsey exponent gap for matchings arxiv open David Conlon; Jacob Fox; Choongbum Lee; Benny Sudakov 2016-04-25
Ordered Ramsey number matching vs triangle magnitude arxiv partial David Conlon; Jacob Fox; Choongbum Lee; Benny Sudakov 2016-04-25
Path-partition height factor 2 tightness arxiv open Adam Gągol; Gwenaël Joret; Jakub Kozik; Piotr Micek 2016-10-02
Rainbow cycle error term in K_n arxiv partial Noga Alon; Alexey Pokrovskiy; Benny Sudakov 2016-08-25
Simultaneous fair representation in path partitions arxiv open Ron Aharoni; Noga Alon; Eli Berger; Maria Chudnovsky; Dani Kotlar; Martin Loebl; Ran Ziv 2016-11-10
Sublinear majority 3-coloring of digraphs arxiv solved Stephan Kreutzer; Sang-il Oum; Paul Seymour; Dominic van der Zypen; David R. Wood 2016-08-10
Token sliding connectivity by clique-tree degree arxiv disproved Marthe Bonamy; Nicolas Bousquet 2016-05-02
Tree T-decomposition via maximum degree connectivity arxiv disproved Julien Bensmail; Ararat Harutyunyan; Tien-Nam Le; Stéphan Thomassé 2016-06-30
TT_k Subdivision via Minimum Semidegree arxiv open Pierre Aboulker; Nathann Cohen; Fréderic Havet; William Lochet; Phablo F. S. Moura; Stéphan Thomassé 2016-10-04
WSK validity for 5-colorings of triangular lattice arxiv partial Marthe Bonamy; Nicolas Bousquet; Carl Feghali; Matthew Johnson 2016-09-22
δ⁺-Maderian property for oriented trees arxiv open Pierre Aboulker; Nathann Cohen; Fréderic Havet; William Lochet; Phablo F. S. Moura; Stéphan Thomassé 2016-10-04
η(G) ≥ 2n for 2-connected graphs arxiv open Marthe Bonamy; Martin Knor; Borut Lužar; Alexandre Pinlou; Riste Škrekovski 2016-02-16
κ-maderianness of strongly connected digraphs arxiv partial Pierre Aboulker; Nathann Cohen; Fréderic Havet; William Lochet; Phablo F. S. Moura; Stéphan Thomassé 2016-10-04
χ-boundedness of oriented-star-free classes arxiv partial Pierre Aboulker; Jørgen Bang-Jensen; Nicolas Bousquet; Pierre Charbit; Frédéric Havet; Frédéric Maffray; Jose Zamora 2016-05-24
χ-boundedness of P₄-orientation forbiddance classes arxiv solved Pierre Aboulker; Jørgen Bang-Jensen; Nicolas Bousquet; Pierre Charbit; Frédéric Havet; Frédéric Maffray; Jose Zamora 2016-05-24
χ-Mader bound for oriented trees arxiv solved Pierre Aboulker; Nathann Cohen; Fréderic Havet; William Lochet; Phablo F. S. Moura; Stéphan Thomassé 2016-10-04
χ_f bound 3 - 3/(n+1) for planar triangle-free arxiv open Zdeněk Dvořák; Tomáš Masařík; Jan Musílek; Ondřej Pangrác 2016-06-20