Graph-theory open problems
1034 / 1034 rows OPG: open 57partial 137solved 19disproved 13unclear 1 arXiv: open 540partial 118solved 80disproved 21unclear 36 unreviewed Bondy–Murty: open 13partial 21solved 3disproved 1 OPG 227 arXiv 768Bondy–Murty 38curated 1
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
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
Polynomial-time approximation for tournament ω-ordering arxiv open Pierre Aboulker; Guillaume Aubian; Raul Lopes 2026-01-23
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
2-reconstructibility threshold in G(n,p) arxiv open Tom Johnston; Gal Kronenberg; Alexander Roberts; Alex Scott 2025-06-23
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
Colour-separated decomposition of rainbow expanders arxiv Noga Alon; Matija Bucić; Lisa Sauermann; Dmitrii Zakharov; Or Zamir 2025-02-26
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
Identity products of transpositions arxiv Noga Alon; Matija Bucić; Lisa Sauermann; Dmitrii Zakharov; Or Zamir 2025-02-26
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 cubic counterexamples to Lovász's conjecture 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
Log-log factor in rainbow-cycle bounds arxiv open Noga Alon; Matija Bucić; Lisa Sauermann; Dmitrii Zakharov; Or Zamir 2025-02-26
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 solved 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 solved 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
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
Short signed products in finite groups arxiv Noga Alon; Matija Bucić; Lisa Sauermann; Dmitrii Zakharov; Or Zamir 2025-02-26
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
Edges forced by vertex subsets arxiv Noga Alon; Matija Bucić; Micha Christoph; Michael Krivelevich 2024-06-10
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 solved 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
Minimum intersecting hypergraph at full cover arxiv Noga Alon; Matija Bucić; Micha Christoph; Michael Krivelevich 2024-06-10
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 solved 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 solved 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
Uniform edge counts in large subsets arxiv Noga Alon; Matija Bucić; Micha Christoph; Michael Krivelevich 2024-06-10
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 disproved 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 solved 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 solved 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 solved 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 solved Pierre Aboulker; Guillaume Aubian; Pierre Charbit; Raul Lopes 2023-10-06
χ⃗-binding tournaments with forest backedge graphs arxiv disproved 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 disproved 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 solved Maria Chudnovsky; Alex Scott; Paul Seymour; Sophie Spirkl 2022-08-03
χ-boundedness for odd-cycle-free digraphs arxiv disproved 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 solved 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 solved 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 solved 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 solved 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 disproved 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 disproved 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 solved 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 solved 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 solved 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 solved 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 solved 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 solved 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 solved 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 solved 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 disproved 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
Barát–Thomassen conjecture bm solved Covers, decompositions and packings J. Barát and C. Thomassen 2006
Birmelé's conjecture on long cycles bm partial Paths and cycles in graphs E. Birmelé 2003
Harborth's conjecture (integral straight-line drawings) bm partial Embeddings A. Kemnitz and H. Harborth 2001
Weighted Caccetta–Häggkvist conjecture bm open Paths and cycles in digraphs B. Bollobás and A.D. Scott 1996
Bondy's small cycle double cover conjecture bm partial Covers, decompositions and packings J.A. Bondy 1990
1-factorization conjecture bm partial Edge colouring A.J.W. Hilton 1989
Thomassen's spanning k-connected bipartite subgraph conjecture bm partial Connectivity C. Thomassen 1989
Finding a second Hamilton cycle in a cubic graph bm open Complexity M. Chrobak and S. Poljak 1988
El-Zahar–Erdős conjecture bm partial Vertex colouring M. El-Zahar and P. Erdős 1985
Meyniel's conjecture on the cop number curated partial Cops and Robbers H. Meyniel 1985
Matthews–Sumner conjecture bm partial Hamilton paths and cycles M.M. Matthews and D.P. Sumner 1984
Orientable five cycle double cover conjecture bm open Embeddings D. Archdeacon (1984); F. Jaeger (1988) 1984
Albertson's toroidal colouring conjecture bm open Colouring graphs embedded in surfaces M.O. Albertson 1981
Five cycle double cover conjecture bm open Covers, decompositions and packings M. Preissmann 1981
Linear arboricity conjecture bm partial Covers, decompositions and packings J. Akiyama, G. Exoo and F. Harary (1981); A.J.W. Hilton (1982) 1981
Internally disjoint odd paths: is it in co-NP? bm open Complexity C. Thomassen 1980
Hajós conjecture for $k = 5$ and $k = 6$ bm open Vertex colouring G. Hajós; P.A. Catlin 1979
Kotzig's unique $k$-path conjecture bm partial Paths and cycles in graphs A. Kotzig 1979
Grötschel's conjecture on bipartite hypotraceable graphs bm open Hamilton paths and cycles M. Grötschel 1978
Hypohamiltonian graphs of minimum degree at least 4 bm open Hamilton paths and cycles C. Thomassen 1978
Burr–Erdős tree Ramsey conjecture bm partial Ramsey numbers S.A. Burr and P. Erdős 1976
Thomassen's conjecture on Hamiltonian vertex-transitive graphs bm partial Hamilton paths and cycles C. Thomassen 1976
Gyárfás's tree conjecture for triangle-free graphs bm partial Vertex colouring A. Gyárfás 1975
Kelmans–Seymour conjecture bm solved Embeddings P.D. Seymour (1974); A.K. Kelmans (1979) 1974
Chvátal's toughness conjecture bm partial Hamilton paths and cycles V. Chvátal 1973
Even-cycle Turán number bm partial Extremal problems P. Erdős 1971
Halin's conjecture on hypomorphic infinite graphs bm disproved Reconstruction R. Halin 1970
Constructive exponential lower bound for diagonal Ramsey numbers bm open Ramsey numbers P. Erdős 1969
Conway's thrackle conjecture bm partial Embeddings J.H. Conway 1968
Erdős–Lovász Tihany conjecture bm partial Vertex colouring L. Lovász 1968
Vizing's interchange conjecture bm solved Edge colouring V.G. Vizing 1965
Erdős–Sós conjecture bm partial Extremal problems P. Erdős and V.T. Sós 1963
Cantoni's conjecture bm partial Hamilton paths and cycles R. Cantoni 1950
Chromatic number of the plane (Hadwiger–Nelson problem) bm partial Colouring graphs embedded in surfaces E. Nelson 1950
Limit of $r(k,k)^{1/k}$ bm partial Ramsey numbers P. Erdős 1947
Hadwiger's conjecture bm open Vertex colouring H. Hadwiger 1943
Barnette's conjecture on 4-regular 4-polytopes bm open Hamilton paths and cycles D.W. Barnette
Bondy's linear-length cycle conjecture for cyclically 4-edge-connected cubic graphs bm open Paths and cycles in graphs J.A. Bondy
Smith's conjecture on longest cycles bm partial Paths and cycles in graphs S. Smith