Select Git revision
-
Martin Mareš authoredMartin Mareš authored
data.bib 142.41 KiB
@article{catlin,
author={P. A. Catlin},
title={A bound on the chromatic number of a graph},
journal={Discrete Math.},
volume={22},
year=1978,
pages={81--83}
}
@article{hajos,
author={G. Haj\"os},
title={{\"Uber eine konstraktion nicht $n$-farbbarer graphen}},
journal={Wiss. Z. MartinLuther Univ. Halle-Wittenberg Math. Naturwiss. Reihe},
number={10},
year={1961},
pages={116--117}
}
@article{dirac,
author={G.A. Dirac},
title={A property of 4-chromatic graphs and some remarks on critical graphs},
journal={Journal of London Math Society},
volume=27,
year={1952},
pages={85--92}
}
@article{diracsh,
author={G. A. Dirac},
title={Short proof of a map colour theorem},
journal={Can. J. Math.},
volume=9,
year=1957,
pages="225--226"
}
@article{acyc,
author={O.V. Borodin},
year=1979,
title={On acyclic colorings of planar graphs},
journal={Discrete Mathematics},
volume=25,
pages="211--236"
}
@article{dens65,
author = {O.V. Borodin and S. G. Hartke and A. O. Ivanova and A. V. Kostochka and D. B. West},
title = {Circular (5,2)-coloring of sparse graphs},
journal = {Sib. Elektron. Mat. Izv.},
volume = 5,
year = 2008,
pages = "417--426"}
@inproceedings{plotkin,
title={Shallow excluded minors and improved graph decompositions},
author={Plotkin, S. and Rao, S. and Smith, W. D},
booktitle={Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms},
pages={462--470},
year={1994},
organization={Society for Industrial and Applied Mathematics}
}
@article{zhusurvey1,
title = "Circular chromatic number: a survey",
journal = "Discrete Mathematics ",
volume = "229",
number = "1-3",
pages = "371--410",
year = "2001",
author = {Zhu, X.},
}
@incollection{zhusurvey2,
title={Recent developments in circular colouring of graphs},
author={Zhu, X.},
booktitle={Topics in discrete mathematics},
pages={497--550},
year={2006},
publisher={Springer}
}
@article{zhucirc,
title={Circular chromatic number of planar graphs of large odd girth},
author={Zhu, X.},
journal={Electronic J. of Combinatorics},
volume={8},
pages={R25},
year={2001}
}
@article{CR16,
title={Planar graphs have independence ratio at least $3/13$},
author={D. W. Cranston and L. Rabern},
journal={Electronic J. of Combinatorics},
volume={23},
pages={P3.45},
year={2016}
}
@article{bkkw,
title={Homomorphisms from sparse graphs with large girth},
author={Borodin, Oleg and Kim, S-J. and Kostochka, Alexandr and West, Douglas},
journal={Journal of Combinatorial Theory, Series B},
volume={90},
number={1},
pages={147--159},
year={2004}
}
@article{vince,
author = {Vince, A.},
title = {Star chromatic number},
journal = {Journal of Graph Theory},
volume = {12},
number = {4},
pages = {551--559},
year = {1988}
}
@inproceedings{jaeger,
title={On circular flows in graphs},
author={F. Jaeger},
booktitle={Finite and Infinite Sets (Eger, 1981), Colloq. Math. Soc. J. Bolyai},
volume={37},
pages={391--402},
year={1984}
}
@article{matopriv,
author = {Matou\v{s}ek, J. and P\v{r}{\'\i}v\v{e}tiv\'y, A.},
title = {Large Monochromatic Components in Two-Colored Grids},
journal = {SIAM Journal on Discrete Mathematics},
volume = {22},
pages = {295--311},
year = {2008}
}
@incollection{dmnich,
title={Large independent sets in triangle-free planar graphs},
author={Dvo{\v{r}}{\'a}k, Zden{\v{e}}k and Mnich, Matthias},
booktitle={Algorithms-ESA 2014},
pages={346--357},
year=2014,
publisher={Springer}
}
@article{berkos,
author="A. Bernshteyn and A. Kostochka",
title="Sharp {D}irac's Theorem for {DP}-critical graphs",
journal={arXiv},
volume={1609.09122},
year=2016
}
@article{berkospron,
author="A. Bernshteyn and A. Kostochka and S. Pron",
title="On {DP}-coloring of graphs and multigraphs",
journal="Sib. Mat. Zhurnal",
year=2016,
note="In Russian, to appear. English version: arXiv:1609.00763"
}
@article{dmnichfull,
title={Large independent sets in triangle-free planar graphs},
author={Dvo{\v{r}}{\'a}k, Zden{\v{e}}k and Mnich, Matthias},
journal={SIAM J. Discrete Math.},
volume=31,
pages={1355--1373},
year=2017
}
@article{MW,
author = {Marx, D. and Wollan, P.},
title = {Immersions in Highly Edge Connected Graphs},
journal = {SIAM Journal on Discrete Mathematics},
volume = {28},
number = {1},
pages = {503-520},
year = {2014}
}
@misc{mat,
author = {J. Matou{\v{s}}ek and J. Vondr{\'a}k},
title = "The probabilistic method",
note="Lecture notes",
howpublished={\url{http://kam.mff.cuni.cz/~matousek/lectnotes.html}}
}
@article{jiang,
author = {T. Jiang},
title={Compact topological minors in graphs},
journal={J. Graph Theory},
volume=67,
year=2011,
pages={139--152}}
@article{fracsub,
author = {Zdenek Dvo\v{r}\'ak and Jean-S{\'e}bastien Sereni and Jan Volec},
title = {Subcubic triangle-free graphs have fractional chromatic number at most 14/5},
journal = {Journal of the London Mathematical Society},
volume = 89,
year = 2014,
pages = "641--662"
}
@article{frpltr,
author = {Zdenek Dvo\v{r}\'ak and Jean-S{\'e}bastien Sereni and Jan Volec},
title = {Fractional coloring of triangle-free planar graphs},
journal = {Electronic Journal of Combinatorics},
volume = 22,
year = 2015,
pages = "P4.11"
}
@article{planfr5,
author = {A. Hilton and R. Rado and S. Scott},
title = {A $(<5)$-Colour Theorem for Planar Graphs},
journal = {Bull. London Math. Soc.},
volume=5,
pages="302--306",
year=1973}
@incollection{Jones1985,
AUTHOR = {Jones, Kathryn Fraughnaugh},
TITLE = {Minimum independence graphs with maximum degree four},
BOOKTITLE = {Graphs and applications ({B}oulder, {C}olo., 1982)},
SERIES = {Wiley-Intersci. Publ.},
PAGES = {221--230},
YEAR = {1985},
PUBLISHER = {Wiley}
}
@article{submany,
title = "Sub-exponentially many 3-colorings of triangle-free planar graphs",
journal={J. Combin. Theory, Ser.~B},
volume = "103",
pages = "706--712",
year = "2013",
author = "A. Asadi and Z. Dvo{\v{r}}{\'a}k and L. Postle and R. Thomas"
}
@article{thom-many,
author={C. Thomassen},
title={Many $3$-colorings of triangle-free planar graphs},
journal={J. Combin. Theory, Ser.~B},
volume=97,
year=2007,
pages="334--349"
}
@article{BorIrred,
author={O. V. Borodin},
title={Irreducible graphs in the {G}r\"unbaum-Havel 3-colour problem},
journal={Discrete Math.},
volume=159,
year=1996,
pages={247--249}
}
@article{PosThoHyperb,
title={Hyperbolic families and coloring graphs on surfaces},
author={Postle, Luke and Thomas, Robin},
journal={Transactions of the American Mathematical Society, Series B},
volume=5,
pages={167--221},
year=2018
}
@inproceedings{crossalg,
author = {Markus Chimani and
Petra Mutzel and
Immanuel M. Bomze},
title = {A New Approach to Exact Crossing Minimization},
booktitle = {ESA},
year = {2008},
pages = {284-296},
crossref = {DBLP:conf/esa/2008}
}
@proceedings{DBLP:conf/esa/2008,
editor = {Dan Halperin and
Kurt Mehlhorn},
title = {Algorithms - ESA 2008, 16th Annual European Symposium, Karlsruhe,
Germany, September 15-17, 2008. Proceedings},
booktitle = {ESA},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
volume = {5193},
year = {2008}
}
@article{confluent,
author = {Chen, Jiangzhuo and Kleinberg, Robert D. and Lov\'{a}sz, L\'{a}szl\'{o} and Rajaraman, Rajmohan and Sundaram, Ravi and Vetta, Adrian},
title = {({A}lmost) Tight bounds and existence theorems for single-commodity confluent flows},
journal = {J. ACM},
issue_date = {July 2007},
volume = {54},
number = {4},
month = jul,
year = {2007},
issn = {0004-5411},
pages = {16:1--16:32}
}
@article{ChChGrid,
author = {Chekuri, Chandra and Chuzhoy, Julia},
title = {Polynomial Bounds for the Grid-Minor Theorem},
journal = {J. ACM},
volume = {63},
number = {5},
year = {2016},
pages = {40:1--40:65}
}
@article{HaWoTree,
author = "Harvey, David and Wood, David",
title = "Parameters tied to treewidth",
journal = {Journal of Graph Theory},
volume = 84,
year = 2017,
pages = {364--385}
}
@unpublished{Fox,
author = "Fox, Jacob",
title = "Constructing dense graphs with sublinear {H}adwiger number",
url = "http://arxiv.org/abs/1108.4953",
note = "J. Combin. Theory Ser. B, to appear"
}
@article {BPTWBand,
AUTHOR = {B{\"o}ttcher, Julia and Pruessmann, Klaas P. and Taraz, Anusch
and W{\"u}rfl, Andreas},
TITLE = {Bandwidth, expansion, treewidth, separators and universality
for bounded-degree graphs},
JOURNAL = {European J. Combin.},
FJOURNAL = {European Journal of Combinatorics},
VOLUME = {31},
YEAR = {2010},
NUMBER = {5},
PAGES = {1217--1227},
ISSN = {0195-6698},
MRCLASS = {05C12 (05C10 05C83)},
MRNUMBER = {2644412 (2012a:05091)},
DOI = {10.1016/j.ejc.2009.10.010},
URL = {http://dx.doi.org/10.1016/j.ejc.2009.10.010},
}
@article {BGHKTree,
AUTHOR = {Bodlaender, Hans L. and Gilbert, John R. and Hafsteinsson,
Hj{\'a}lmt{\'y}r and Kloks, Ton},
TITLE = {Approximating treewidth, pathwidth, frontsize, and shortest
elimination tree},
JOURNAL = {J. Algorithms},
FJOURNAL = {Journal of Algorithms},
VOLUME = {18},
YEAR = {1995},
NUMBER = {2},
PAGES = {238--255},
ISSN = {0196-6774},
DOI = {10.1006/jagm.1995.1009},
URL = {http://dx.doi.org/10.1006/jagm.1995.1009},
}
@article{PR1,
author = {Pinontoan, Benny and Richter, R. Bruce},
title = {Crossing numbers of sequences of graphs. {I}. {G}eneral tiles},
journal = {Australas. J. Combin.},
volume = {30},
year = {2004},
pages = {197--206}
}
@article{PR2,
AUTHOR = {Pinontoan, Benny and Richter, R. Bruce},
TITLE = {Crossing numbers of sequences of graphs. {II}. {P}lanar tiles},
JOURNAL = {J. Graph Theory},
FJOURNAL = {Journal of Graph Theory},
VOLUME = {42},
YEAR = {2003},
NUMBER = {4},
PAGES = {332--341},
MRCLASS = {05C10},
MRNUMBER = {1963105 (2004e:05060)},
DOI = {10.1002/jgt.10097},
URL = {http://dx.doi.org/10.1002/jgt.10097},
}
@article{Pinon06,
AUTHOR = {Pinontoan, Benny},
TITLE = {Tile with rational average crossing number},
JOURNAL = {J. Indones. Math. Soc.},
FJOURNAL = {Journal of the Indonesian Mathematical Society. Majalah Ilmiah
Himpunan Matematika Indonesia (MIHMI)},
VOLUME = {12},
YEAR = {2006},
NUMBER = {1},
PAGES = {83--87},
MRCLASS = {05C10},
MRNUMBER = {2208030 (2006i:05051)},
}
@MISC{BIRSreport,
author = "Archdeacon, Dan and Salazar, Gelasio and Sz\'ekely, L\'azsl\'o",
note = "Crossing numbers turn useful, Report on BIRS Workshop (11w5144)",
url = "http://www.birs.ca/workshops/2011/11w5144/report11w5144.pdf",
year = 2011
}
@article{plansat,
author = {David Lichtenstein},
title = {Planar Formulae and Their Uses},
journal = {SIAM J. Comput.},
volume = {11},
year = {1982},
pages = {329-343}
}
@inproceedings{minalg1,
author={K. Kawarabayashi and P. Wollan},
title={A simpler algorithm and shorter proof for the graph minor decomposition},
booktitle = {STOC},
year = {2011},
pages = {451--458},
crossref = {stoc43}}
@inproceedings{minalg2,
author = {Martin Grohe and {Ken-ichi} Kawarabayashi and Bruce A. Reed},
title = {A Simple Algorithm for the Graph Minor Decomposition - Logic meets Structural Graph Theory},
booktitle = {Proceedings of the Twenty-Fourth Annual {ACM-SIAM} {S}ymposium
on {D}iscrete {A}lgorithms, {SODA} 2013, {N}ew {O}rleans, {L}ouisiana,
{USA}, {J}anuary 6-8, 2013},
year = {2013},
pages = {414--431},
publisher = {SIAM},
}
@article{locplanq,
author={J. P. Hutchinson},
title={Three-Coloring Graphs Embedded on Surfaces with All Faces Even-Sided},
journal={J. Combin. Theory, Ser.~B},
volume=65,
pages="139--155",
year=1995}
@article{NakNegOta,
author = {A. Nakamoto and S. Negami and K. Ota},
title={Chromatic numbers and cycle parities of quadrangulations on nonorientable closed surfaces},
journal={Discrete Math.},
volume =285,
year=2004,
pages="211--218"}
@article{MohSey,
author={B. Mohar and P. D. Seymour},
title={Coloring locally bipartite graphs on surfaces},
journal={J. Combin. Theory, Ser.~B},
volume=84,
year=2002,
pages="301--310"}
@article{chooscomplex,
author="S. Gutner",
title="The complexity of planar graph choosability",
journal="Discrete Math.",
volume=159,
year=1996,
pages="119--130"}
@article{cabello-sepcurv,
author={S. Cabello and B. Mohar},
title={Finding shortest non-separating and non-contractible cycles for topologically embedded graphs},
journal={Discrete Comput. Geom.},
volume=37,
year=2007,
pages="213--235"}
@article{listcoltw,
author = {K. Jansen and P. Scheffler},
title = {Generalized coloring for tree-like graphs},
journal = {Discrete Appl. Math.},
volume = {75},
year = {1997},
pages = {135--155}
}
@inproceedings{topmintest,
author = {M. Grohe and K. Kawarabayashi and D. Marx and P. Wollan},
title = {Finding topological subgraphs is fixed-parameter tractable},
booktitle = {STOC},
year = {2011},
pages = {479-488},
crossref = {stoc43}
}
@proceedings{stoc43,
editor = {Lance Fortnow and
Salil P. Vadhan},
title = {Proceedings of the 43rd ACM Symposium on Theory of Computing,
STOC 2011, San Jose, CA, USA, 6-8 June 2011},
booktitle = {STOC},
publisher = {ACM},
year = {2011}
}
@article{nepol,
author="J. Ne\v{s}et\v{r}il and S. Poljak",
title="Complexity of the subgraph problem",
journal="Comment. Math. Univ. Carol.",
volume=26,
year=1985,
pages="415--420"}
@article{fellows,
author = "R. Downey and M. Fellows",
year=1995,
title="Fixed-parameter tractability and completeness. {II}. {O}n completeness for {W}[1]",
journal="Theoretical Computer Science",
volume=141,
pages="109--131"}
@article{bib-eppstein99,
author="D. Eppstein",
title="Subgraph isomorphism in planar graphs and related problems",
journal="Journal of Graph Algorithms and Applications",
volume=3,
year=1999,
pages="1--27"}
@article{subdivchar,
title={On forbidden subdivision characterizations of graph classes},
author={Z. Dvo{\v{r}}{\'a}k},
journal={European Journal of Combinatorics},
volume={29},
number={5},
pages={1321--1332},
year={2008}
}
@article{fg,
author = {M. Frick and M. Grohe},
title = {Deciding first-order properties of locally tree-decomposable structures},
journal = {J. ACM},
volume = {48},
year = {2001},
pages = {1184--1206}
}
@inproceedings{kreedsep,
author = {K. Kawarabayashi and B. Reed},
year = 2010,
title = "A separator theorem in minor-closed classes",
booktitle = {Proc. 51st Annual IEEE Symposium on. Foundations of Computer Science}}
@article{ssep1,
title={Fast algorithms for shortest paths in planar graphs, with applications},
author={Federickson, Greg N},
journal={SIAM Journal on Computing},
volume={16},
number={6},
pages={1004--1022},
year={1987},
publisher={SIAM}
}
@article{ssep2,
title={Planar separators and parallel polygon triangulation},
author={Goodrich, Michael T},
journal={Journal of Computer and System Sciences},
volume={51},
number={3},
pages={374--389},
year={1995},
publisher={Elsevier}
}
@article{ssep3,
title={Separator based sparsification: {I}. {P}lanarity testing and minimum spanning trees},
author={Eppstein, David and Galil, Zvi and Italiano, Giuseppe F and Spencer, Thomas H},
journal={Journal of Computer and System Sciences},
volume={52},
number={1},
pages={3--27},
year={1996}
}
@article{ssep4,
title={Separator-based sparsification {II}: {E}dge and vertex connectivity},
author={Eppstein, David and Galil, Zvi and Italiano, Giuseppe F and Spencer, Thomas H},
journal={SIAM Journal on Computing},
volume={28},
number={1},
pages={341--381},
year={1998}
}
@article{ssep5,
title={Exact algorithms for the {H}amiltonian cycle problem in planar graphs},
author={De{\i}, Vladimir G and Klinz, Bettina and Woeginger, Gerhard J and others},
journal={Operations Research Letters},
volume={34},
number={3},
pages={269--274},
year={2006},
publisher={Elsevier}
}
@article{ssep6,
title={Girth of a Planar Digraph with Real Edge Weights in {$O(n(\log n)^3)$} Time},
author={Wulff-Nilsen, Christian},
journal={arXiv},
volume={0908.0697},
year={2009}
}
@article{ssep7,
title={Shortest paths in directed planar graphs with negative lengths: A linear-space {$O(n \log_2 n)$}-time algorithm},
author={Klein, Philip N and Mozes, Shay and Weimann, Oren},
journal={ACM Transactions on Algorithms (TALG)},
volume={6},
number={2},
pages={30},
year={2010}
}
@article{lt79,
author={R. Lipton and R. Tarjan},
year=1979,
title = "A separator theorem for planar graphs",
journal = {SIAM Journal on Applied Mathematics},
volume= 36,
pages= {177--189}}
@article{lt80,
author={R. Lipton and R. Tarjan},
year=1980,
title = "Applications of a planar separator theorem",
journal = {SIAM Journal on Computing},
volume = 9,
pages = {615--627}}
@article{gilbert,
author={J. Gilbert and J. Hutchinson and R. Tarjan},
year=1984,
title = "A separator theorem for graphs of bounded genus",
journal = {Journal of Algorithms},
volume = 5,
pages = {391--407}}
@article{osmenwood,
author = {J. Ne\v{s}et\v{r}il and P. {Ossona de Mendez} and D. Wood},
title = {Characterisations and examples of graph classes with bounded expansion},
journal = {Eur. J. Comb.},
volume = {33},
year = {2012},
pages = {350--373}
}
@article{wood-cliques,
author = {D. Wood},
title = {On the Maximum Number of Cliques in a Graph},
journal = {Graph. Comb.},
volume = {23},
year = {2007},
pages = {337--352}
}
@inproceedings{npom-old,
author = {J. Ne{\v{s}}et\v{r}il and P. {Ossona de Mendez}},
title = {Linear time low tree-width partitions and algorithmic consequences},
booktitle = {Proceedings of the thirty-eighth annual ACM symposium on Theory of computing},
series = {STOC '06},
year = {2006},
pages = {391--400},
publisher = {ACM}
}
@article{grad1,
author = "J. Ne{\v{s}}et\v{r}il and P. {Ossona de Mendez}",
title = "Grad and classes with bounded expansion {I}. {D}ecompositions",
journal = "European J. Combin.",
volume = 29,
year = 2008,
pages = "760--776"}
@article{grad2,
author = "J. Ne{\v{s}}et\v{r}il and P. {Ossona de Mendez}",
title = "Grad and classes with bounded expansion {II}. {A}lgorithmic aspects",
journal = "European J. Combin.",
volume = 29,
year = 2008,
pages = "777--791"}
@article{grad3,
author = "J. Ne{\v{s}}et\v{r}il and P. {Ossona de Mendez}",
title = "Grad and classes with bounded expansion {III}. {R}estricted graph homomorphism dualities",
journal = "European J. Combin.",
volume = 29,
year = 2008,
pages = "1012--1024"}
@article{npom-nd1,
author = "J. Ne{\v{s}}et\v{r}il and P. {Ossona de Mendez}",
title={First order properties on nowhere dense structures},
journal="J. Symbolic Logic",
volume=75,
year=2010,
pages="868--887"}
@article{npom-nd2,
author = "J. Ne{\v{s}}et\v{r}il and P. {Ossona de Mendez}",
title = "On nowhere dense graphs",
journal = "European J. Combin.",
volume = 32,
year = 2011,
pages = "600--617"}
@inproceedings{dkt-fol,
author = {Z. Dvo\v{r}\'ak and D. Kr{\'a}l' and R. Thomas},
title = {Deciding First-Order Properties for Sparse Graphs},
year = {2010},
pages = {133-142},
crossref = {focs2010}
}
@proceedings{focs2010,
title = {51th Annual IEEE Symposium on Foundations of Computer Science,
FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA},
booktitle = {Proceedings of 51th Annual IEEE Symposium on Foundations of Computer Science},
publisher = {IEEE Computer Society},
year = 2010
}
@incollection{dynds,
author = {G. Brodal and R. Fagerberg},
title = {Dynamic Representations of Sparse Graphs},
booktitle = {Algorithms and Data Structures},
series = {Lecture Notes in Computer Science},
publisher = {Springer Berlin / Heidelberg},
pages = {773-773},
volume = {1663},
year = {1999}}
@book{4algs,
author= {T. H. Cormen and C. E. Leiserson and R. L. Rivest and C. Stein},
title={Introduction to algorithms},
publisher={The MIT Press},
year=2009}
@inproceedings{dk-surv,
author={Z. Dvo\v{r}\'ak and D. Kr\'al'},
title={Algorithms for classes of graphs with bounded expansion},
booktitle={Proceedings of WG'09},
series="Lecture Notes in Computer Science",
volume=5911,
publisher="Springer",
year=2009,
pages="17--32"}
@article{numplan,
author = "A. Denise and M. Vasconcellos and D. Welsh",
title = "The random planar graph",
journal = "Congr. Numer.",
volume=113,
year=1996,
pages = "61--79"}
@article{Alb98,
AUTHOR = {Albertson, Michael O.},
TITLE = {You can't paint yourself into a corner},
JOURNAL = {J. Combin. Theory, Ser.~B},
VOLUME = {73},
YEAR = {1998},
NUMBER = {2},
PAGES = {189--194}
}
@article{Albertson76,
AUTHOR = {Albertson, Michael O.},
TITLE = {A lower bound for the independence number of a planar graph},
JOURNAL = {J. Combin. Theory, Ser.~B},
VOLUME = 20,
YEAR = 1976,
NUMBER = 1,
PAGES = {84--93}
}
@article{thom-2007,
author = {Carsten Thomassen},
title = {Exponentially many 5-list-colorings of planar graphs},
journal = {J. Combin. Theory, Ser.~B},
volume = 97,
year = 2007,
pages = {571-583}}
@article{bencan,
author="E. A. Bender and E. R. Canfield",
title="The Asymptotic Number of Labeled Graphs with Given Degree Sequences",
journal="J. Combin. Theory, Ser.~A",
volume=24,
year=1978,
pages="296--307"}
@article{fc367,
author={Z. Dvo\v{r}\'ak and B. Lidick\'y and R. \v{S}krekovski},
title={3-choosability of triangle-free planar graphs with constraints on 4-cycles},
journal={SIAM J. Discrete Math.},
volume=24,
year=2010,
pages="934--945"}
@article{gonthier2008formal,
title={Formal proof--the four-color theorem},
author={G. Gonthier},
journal={Notices of the AMS},
volume=55,
number=11,
pages={1382--1393},
year=2008}
@article{minor2,
author = {A. Thomason},
title = {An extremal function for complete subgraphs},
journal = {Math. Proc. Camb. Phil. Soc.},
volume = 95,
year = 1984,
pages = {261--265}}
@article{bolo,
author = {B. Bollob{\'a}s},
title = {The isoperimetric number of random regular graphs},
journal = {European Journal of Combinatorics},
volume = 9,
year = 1988,
pages = {241--244}}
@article{AlbBolTuc,
author = {M. Albertson and B. Bollob\'as and S. Tucker},
title = {The independence ratio and the maximum degree of a graph},
journal = {Congr. Numer.},
volume = 17,
year = 1976,
pages = "43--50"}
@article{SteinbergTovey1993,
AUTHOR = {Steinberg, Richard and Tovey, Craig A.},
TITLE = {Planar {R}amsey numbers},
journal={J. Combin. Theory, Ser.~B},
VOLUME = {59},
YEAR = {1993},
NUMBER = {2},
PAGES = {288--296}
}
@article{steinberger2010unavoidable,
title={An unavoidable set of {D}-reducible configurations},
author={J. P. Steinberger},
journal={Trans. Amer. Math. Soc},
volume=362,
pages={6633--6661},
year=2010}
@article{bartoth,
author="J. Bart and G. Tth",
year=2010,
title="Towards the {A}lbertson {C}onjecture",
journal="Electronic Journal of Combinatorics",
volume=17,
pages="R73"}
@article{krst,
author="D. Krl' and L. Stacho",
title="Coloring plane graphs with independent crossings",
journal="J. Graph Theory",
volume=64,
year=2010,
pages="184--205"}
@article{CaHa11,
author={V. Campos and F. Havet},
title={5-choosability of graphs with 2 crossings},
journal = {ArXiv},
volume={1105.2723},
year=2011
}
@article{LidDvoSkre,
author={Z. Dvo\v{r}\'ak and B. Lidick\'y and R. \v{S}krekovski},
title={Graphs with two crossings are 5-choosable},
journal="SIAM J. Discrete Math.",
volume=25,
year=2011,
pages="1746--1753"}
@article{LidDvoMohPos,
author={Z. Dvo\v{r}\'ak and B. Lidick\'y and B. Mohar and L. Postle},
title={$5$-list-coloring planar graphs with distant precolored vertices},
journal = {Journal of Combinatorial Theory, Series B},
volume = 122,
year=2017,
pages={311--352}
}
@article{le4far,
author={Z. Dvo\v{r}\'ak},
title={$3$-choosability of planar graphs with $(\le\!4)$-cycles far apart},
journal={Journal of Combinatorial Theory, Series B},
volume=104,
pages={28--59},
year=2014}
@inproceedings{dvokawalg,
author = {Zden{\v{e}}k Dvo{\v{r}}{\'a}k and
{Ken-ichi} Kawarabayashi},
title = {List-coloring embedded graphs},
booktitle = {Proceedings of the Twenty-Fourth Annual {ACM-SIAM} {S}ymposium
on {D}iscrete {A}lgorithms, {SODA} 2013, {N}ew {O}rleans, {L}ouisiana,
{USA}, {J}anuary 6-8, 2013},
publisher = {SIAM},
year = {2013},
pages = {1004--1012},
}
@article{Ballantine,
AUTHOR = {Ballantine, J. P.},
TITLE = {A postulational introduction to the four color problem},
JOURNAL = {Publ. in Math., Univ. of Washington, Seattle},
YEAR = {1930},
PAGES = {1--16},
}
@article{EHLP-11,
author={R. Erman and F. Havet and B. Lidick\'{y} and O. Pangr\'{a}c},
title={5-colouring graphs with 4 crossings},
journal="SIAM J. Discrete Math.",
volume=25,
pages={401--422},
year=2011}
@article{rsst,
author = "N. Robertson and D. P. Sanders and P. Seymour and R. Thomas",
title = "The four colour theorem",
journal = "J. Combin. Theory, Ser.~B",
volume = 70,
year = 1997,
pages = "2--44"}
@article{Fisk78,
AUTHOR = {S. Fisk},
TITLE = {The nonexistence of colorings},
JOURNAL = {J. Combin. Theory, Ser.~B},
VOLUME = 24,
YEAR = 1978,
PAGES = {247--248},
}
@article{Albhut,
author="M. Albertson and J. Hutchinsonn",
title="The three excluded cases of {D}irac's map-color theorem",
journal = {Annals of the New York Academy of Sciences},
volume = 319,
publisher = {Blackwell Publishing Ltd},
pages = {7--17},
year = 1979}
@unpublished{pothom,
author = "L. Postle and R. Thomas",
title = "A {L}inear {U}pper {B}ound for 6-{C}ritical {G}raphs on {S}urfaces",
note = "Manuscript"}
@book{nesbook,
author="J. Ne{\v{s}}et\v{r}il and P. {Ossona de Mendez}",
title="Sparsity (Graphs, Structures, and Algorithms)",
volume=28,
series={Algorithms and Combinatorics},
publisher = "Springer",
year=2012}
@book{mohthom,
author = "B.~Mohar and C.~Thomassen",
title = "Graphs on Surfaces",
publisher = "The Johns Hopkins University Press",
address = "Baltimore and London",
year = 2001}
@article{Thomassen97,
AUTHOR = {C. Thomassen},
TITLE = {Color-critical graphs on a fixed surface},
JOURNAL = {J. Combin. Theory, Ser.~B},
VOLUME = 70,
YEAR = 1997,
PAGES = "67--100"
}
@article{Thomassen93,
author = "Carsten Thomassen",
title = "Five-{C}oloring {M}aps on {S}urfaces",
journal = "J. of Combin. Theory, Ser.~B",
volume = 59,
pages = "89 - 105",
year = 1993
}
@article{mohcrit,
author = {B. Mohar},
title = {7-critical graphs of bounded genus},
journal = {Discrete Math.},
volume = 112,
year = 1993,
pages = "279--281"
}
@article{Tho5torus,
AUTHOR = {C. Thomassen},
TITLE = {Five-coloring graphs on the torus},
JOURNAL = {J. Combin. Theory, Ser.~B},
VOLUME = 62,
YEAR = 1994,
PAGES = "11--33"
}
@article{Th2,
AUTHOR = {C. Thomassen},
TITLE = {Five-coloring graphs on surfaces},
JOURNAL = {J. Combin. Theory, Ser.~B},
VOLUME = 59,
YEAR = 1993,
PAGES = "89--105"
}
@article{galfor,
author = "T. Gallai",
title = "Kritische {G}raphen {I}",
journal = "Publ. Math. Inst. Hungar. Acad. Sci.",
volume = 8,
year =1963,
pages = "265--292"}
@article{galfor2,
author = "T. Gallai",
title = "Kritische {G}raphen {II}",
journal = "Publ. Math. Inst. Hungar. Acad. Sci.",
volume = 8,
year =1963,
pages = "373--395"}
@article{ChePosStrThoYer,
author="N. Chenette and L. Postle and N. Streib and R. Thomas and C. Yerger",
title="Five-coloring graphs in the {K}lein bottle",
journal="J. Combin. Theory Ser. B",
volume=102,
year=2012,
pages="1067--1098"
}
@article{KawKraKynLid,
author="K. Kawarabayashi and D. Kr\'al' and J. Kyn\v{c}l and B. Lidick\'y",
title="6-critical graphs on the {K}lein bottle",
journal="SIAM J.~Discrete Math.",
volume=23,
year=2008,
pages="372--383"}
@article{aksenov,
author="V. A. Aksionov",
title="On continuation of $3$-colouring of planar graphs",
note="In Russian",
journal="Diskret. Anal. Novosibirsk",
volume=26,
year=1974,
pages="3--19"}
@article{fartr1,
author="O. V. Borodin and A. Raspaud",
title="A sufficient condition for a planar graph to be 3-colorable",
journal="J. Combin. Theory, Ser.~B",
volume=88,
pages="17--27",
year=2003}
@article{conj-stein,
author="R. Steinberg",
title="The state of the three color problem. {Q}uo {V}adis, {G}raph {T}heory?",
journal="Ann. Discrete Math.",
volume=55,
year=1993,
pages="211--248"}
@article{bornew,
author = "O. V. Borodin",
title = "A new proof of {G}r{\"u}nbaum's 3 color theorem",
journal = "Discrete Math.",
volume = 169,
pages = "177--183",
year = 1997}
@MISC{montasweb,
author="M. Montassier",
title="The 3-Color Problem",
howpublished={\url{http://www.lirmm.fr/~montassier/index.php?n=Site.ThreeColorProblem}}}
@MISC{devosopen,
author="Matt DeVos",
title="Open Problem Garden: Mapping planar graphs to odd cycles",
howpublished={\url{http://www.openproblemgarden.org/op/mapping_planar_graphs_to_odd_cycles}}}
@article{bor47,
author="O. V. Borodin and A. N. Glebov and A. Raspaud and M. R. Salavatipour",
title="Planar graphs without cycles of length from 4 to 7 are 3-colorable",
journal="J. Combin. Theory, Ser.~B",
volume=93,
pages="303--311",
year=2005}
@article{fartr2,
author = {Borodin, O. V. and Glebov, A. N. and Jensen, T. R.},
title = {A step towards the strong version of {H}avel's three color conjecture},
journal = {J. Comb. Theory Ser. B},
volume = {102},
number = {6},
year = {2012},
pages = {1295--1320}}
@article{col457,
author="O. V. Borodin and A. N. Glebov and M. Montassier and A. Raspaud",
title="Planar graphs without 5- and 7-cycles and without adjacent triangles are 3-colorable",
journal = "J. Combin. Theory, Ser.~B",
volume = 99,
pages = "668--673",
year=2009}
@article{col467a5,
author = "M. Chen and W. Wang",
title = "On 3-colorable planar graphs without short cycles",
journal ="Appl. Math. Letter",
volume = 21,
pages="961--965",
year =2008}
@article{col468,
author = "M. Chen and W. Wang",
title = "Planar graphs without 4,6,8-cycles are 3-colorable",
journal = "Science in China Series A: Mathematics",
volume = 50,
pages = "1552--1562",
year = 2007}
@article{col4679,
author = "M. Chen and A. Raspaud and W. Wang",
title = "Three-coloring planar graphs without short cycles",
journal = "Information Processing Letters",
volume = 101,
pages = "134--138",
year = 2007}
@article{KowKur,
author = "\L. Kowalik and M. Kurowski",
title = "Oracles for bounded length shortest paths in planar graphs",
journal = "ACM Trans. Algorithms",
volume = 2,
year = 2006,
pages = "335--363"}
@inproceedings{Kow3col,
author = "\L.~Kowalik",
title = "Fast 3-Coloring Triangle-Free Planar Graphs",
booktitle = "ESA",
year = 2004,
pages = "436-447",
crossref = "DBLP:conf/esa/2004"
}
@proceedings{DBLP:conf/esa/2004,
editor = "Susanne Albers and Tomasz Radzik",
title = "Algorithms - ESA 2004, 12th Annual European Symposium, Bergen, Norway, September 14-17, 2004, Proceedings",
booktitle = "ESA",
publisher = "Springer",
series = "Lecture Notes in Computer Science",
volume = 3221,
year = 2004
}
@article{ShiHsu,
author = "W.-K. Shih and W.-L. Hsu",
title = "A new planarity test",
journal = "Theoret. Comp. Sci.",
volume = 223,
year = 1999,
pages = "179--191"}
@article{Wil,
author = "S.~G.~Williamson",
title = "Depth-first search and Kuratowski subgraphs",
journal = "J. Assoc. Comput. Mach.",
volume = 31,
year = 1984,
pages = "681--693"}
@article{aksmel,
author="V. A. Aksionov and L. S. Mel'nikov",
title="Some counterexamples associated with the {T}hree {C}olor {P}roblem",
journal="J. Combin. Theory, Ser.~B",
volume=28,
year=1980,
pages="1--9"}
@article{thom-torus,
author="C. Thomassen",
title={Gr{\"o}tzsch's 3-Color Theorem and Its Counterparts for the Torus and the Projective Plane},
journal="J. Combin. Theory, Ser.~B",
volume=62,
year=1994,
pages="268--279"}
@article{Heawood,
author={P. J. Heawood},
title={Map-color theorem},
journal={Quart. J. Pure Appl. Math.},
volume=24,
year=1890,
pages="332--338"}
@article{AppHak1,
author={K. Appel and W. Haken},
title={Every planar map is four colorable, {P}art {I}: {D}ischarging},
journal="Illinois J. of Math.",
volume=21,
year=1977,
pages="429--490"}
@article{AppHakKoc,
author={K. Appel and W. Haken and J. Koch},
title={Every planar map is four colorable, {P}art {II}: {R}educibility},
journal="Illinois J. of Math.",
volume=21,
year=1977,
pages="491--567"}
@article{baker1994approximation,
title={Approximation algorithms for {NP}-complete problems on planar graphs},
author={Baker, B.S.},
journal={Journal of the ACM (JACM)},
volume={41},
number={1},
pages={153--180},
year={1994}}
@article{bohme2003domination,
title={Domination, packing and excluded minors},
author={B{\"o}hme, T. and Mohar, B.},
journal={Electronic Journal of Combinatorics},
volume={10},
number={1},
pages={N9},
year={2003}}
@article{bohmelc,
author = {B{\"o}hme, T. and Mohar, B. and Stiebitz, M.},
title = {Dirac's map-color theorem for choosability},
journal = {J. Graph Theory},
volume = {32},
issue = {4},
year = {1999},
pages = {327--339}
}
@article{dircrit,
author="G. A. Dirac",
title = "The structure of $k$-chromatic graphs",
journal = "Fund. Math.",
volume = 40,
year = 1953,
pages = "42--55"}
@incollection{surcrit,
title={Color-critical graphs and hypergraphs with few edges: a survey},
author={A. Kostochka},
booktitle={More sets, graphs and numbers},
pages={175--197},
year=2006,
publisher={Springer}
}
@article{dvorak2008forbidden,
title={On forbidden subdivision characterizations of graph classes},
author={Dvo\v{r}\'ak, Z.},
journal={European Journal of Combinatorics},
volume={29},
number={5},
pages={1321--1332},
year={2008}}
@article{dmcross,
author="Z. Dvo\v{r}\'ak and B. Mohar",
title={Crossing-critical graphs with large maximum degree},
journal="J. Combin. Theory, Ser.~B",
volume=100,
year=2010,
pages="413--417"}
@article{dvolid,
author="Z. Dvo\v{r}\'ak and B. Lidick\'y",
title={$4$-critical graphs on surfaces without contractible $(\le 4)$-cycles},
journal = {SIAM Journal on Discrete Mathematics},
volume = 28,
year = 2014}
@article{5choosfar,
author="Z. Dvo\v{r}\'ak and B. Lidick\'y and B. Mohar",
title={$5$-choosability of graphs with crossings far apart},
journal={ArXiv},
volume={1201.3014v2},
year=2015}
@article{cone,
title={Coloring count cones of planar graphs},
author="Z. Dvo\v{r}\'ak and B. Lidick\'y",
year={2019},
volume={1907.04066},
journal={arXiv}
}
@article{cylgen-part1,
author="Z. Dvo\v{r}\'ak and B. Lidick\'y",
title={Fine structure of $4$-critical triangle-free graphs {I}. {P}lanar graphs with two triangles and $3$-colorability of chains},
journal={ArXiv},
volume={1505.07294},
month=may,
year=2015}
@article{cylgen-part2,
author="Z. Dvo\v{r}\'ak and B. Lidick\'y",
title={Fine structure of $4$-critical triangle-free graphs {II}. {P}lanar triangle-free graphs with two precolored $4$-cycles},
journal={SIAM J. Discrete Math.},
volume=31,
year=2017,
pages={865--874}
}
@article{cylgen-part3,
author="Z. Dvo\v{r}\'ak and B. Lidick\'y",
title={Fine structure of $4$-critical triangle-free graphs {III}. {G}eneral surfaces},
journal={SIAM J. Discrete Math.},
volume=32,
year=2018,
pages={94--105}}
@article{DvoKawTho,
author={Z. Dvo\v{r}\'ak and K. Kawarabayashi and R. Thomas},
title={Three-coloring triangle-free planar graphs in linear time},
journal="Trans. on Algorithms",
volume=7,
year=2011,
pages="article no. 41"}
@book{BonMur,
author={J. Bondy and U. Murty},
title={Graph {T}heory with {A}pplications},
publisher="North-Holland, New York, Amsterdam, Oxford",
year=1976}
@article{dk,
author="Z. Dvo\v{r}\'ak and K. Kawarabayashi",
title = "{Choosability of planar graphs of girth 5}",
journal = {ArXiv},
volume = {1109.2976},
year = 2011
}
@article{crnest,
author={C. Hernandez-Velez and G. Salazar and R. Thomas},
title={Nested cycles in large triangulations and crossing-critical graphs},
journal={Journal of Combinatorial Theory, Series B},
volume=102,
year=2012,
pages={86--92}}
@article{dkt,
author="Z. Dvo\v{r}\'ak and D. Kr\'al' and R. Thomas",
title="Coloring planar graphs with triangles far apart",
journal = {ArXiv},
archivePrefix = "arXiv",
volume = {0911.0885v1},
year = 2009,
month = nov}
@article{col8cyc,
author="Z. Dvo\v{r}\'ak and B. Lidick\'y",
title="3-coloring triangle-free planar graphs with a precolored 8-cycle",
journal = {J. Graph Theory},
volume=80,
year=2015,
pages={98--111}
}
@article{4c4t,
author="O. V. Borodin and Z. Dvo\v{r}\'ak and A. Kostochka and B. Lidick\'y and M. Yancey",
title="Planar 4-critical graphs with four triangles",
journal = {European J. Combin.},
volume = 41,
year = 2014,
pages = {138--151}
}
@article{trfree1,
author="Z. Dvo\v{r}\'ak and D. Kr\'al' and R. Thomas",
title="Three-coloring triangle-free graphs on surfaces {I}. {E}xtending a coloring to a disk with one triangle",
journal = {J. Comb. Theory, Ser. {B}},
volume = 120,
year = 2016,
pages = {1--17}
}
@article{trfree4,
author="Z. Dvo\v{r}\'ak and D. Kr\'al' and R. Thomas",
title="Three-coloring triangle-free graphs on surfaces {IV}. {B}ounding face sizes of $4$-critical graphs",
journal = "Journal of Combinatorial Theory, Series B",
year = 2021,
volume=150,
pages="270--304"
}
@article{trfree5,
author="Z. Dvo\v{r}\'ak and D. Kr\'al' and R. Thomas",
title="Three-coloring triangle-free graphs on surfaces {V}. {C}oloring planar graphs with distant anomalies",
journal = "Journal of Combinatorial Theory, Series B",
year=2021,
volume=150,
pages="244--269"}
@article{trfree6,
author="Z. Dvo\v{r}\'ak and D. Kr\'al' and R. Thomas",
title="Three-coloring triangle-free graphs on surfaces {VI}. $3$-colorability of quadrangulations",
journal = {ArXiv},
volume={1509.01013},
month=sep,
year=2015}
@article{trfree7,
author="Z. Dvo\v{r}\'ak and D. Kr\'al' and R. Thomas",
title="Three-coloring triangle-free graphs on surfaces {VII}. {A} linear-time algorithm",
journal = {ArXiv},
volume={1601.01197},
year=2016}
@article{tutteflow,
author="W.T. Tutte",
title={A Contribution on the Theory of Chromatic Polynomials},
journal={Canad. J. Math.},
volume=6,
year=1954,
pages="80--91"}
@inproceedings{coltrfree,
author = {Z. Dvo\v{r}\'{a}k and D. Kr\'{a}l' and R. Thomas},
title = {Coloring triangle-free graphs on surfaces},
booktitle = {Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms},
series = {SODA '09},
year = 2009,
pages = {120--129},
publisher = {Society for Industrial and Applied Mathematics},
address = {Philadelphia, PA, USA}}
@article{bor7c,
author="V. A. Aksenov and O. V. Borodin and A. N. Glebov",
title="Extending 3-colorability from a 7-face to a planar triangle-free graph",
journal="Sib. Elektron. Mat. Izv.",
volume=1,
year=2004,
pages="117--128",
note="In Russian"}
@article{aksenov6cyc,
author="V. A. Aksenov and O. V. Borodin and A. N. Glebov",
title="Continuation of a 3-coloring from a 6-face onto a plane graph without 3-cycles",
note="In Russian",
journal="Diskretn. Anal. Issled. Oper. Ser. 1",
volume=10,
year=2003,
pages="3--11"}
@article{trfree2,
author="Z. Dvo\v{r}\'ak and D. Kr\'al' and R. Thomas",
title="Three-coloring triangle-free graphs on surfaces {II}. $4$-critical graphs in a disk",
journal = {Journal of Combinatorial Theory, Series B},
volume = 132,
year = 2018,
pages="1--46"}
@article{trfree3,
author="Z. Dvo\v{r}\'ak and D. Kr\'al' and R. Thomas",
title="Three-coloring triangle-free graphs on surfaces {III}. {G}raphs of girth five",
journal = {Journal of Combinatorial Theory, Series B},
volume = 145,
year = 2020,
pages = "376--432"
}
@inproceedings{dvorak2010deciding,
title={Deciding first-order properties for sparse graphs},
author={Z. Dvo\v{r}\'ak and D. Kr\'al' and R. Thomas},
booktitle={2010 IEEE 51st Annual Symposium on Foundations of Computer Science},
pages={133--142},
year={2010}}
@article{dvorak2013testing,
title={Testing first-order properties for subclasses of sparse graphs},
author={Dvo{\v{r}}{\'a}k, Z. and Kr{\'a}l', Daniel and Thomas, Robin},
journal={Journal of the ACM (JACM)},
volume={60},
number={5},
pages={36},
year={2013}
}
@article{erdosrubintaylor1979,
author={P. Erd\H{o}s and A. L. Rubin and H. Taylor},
title={Choosability in graphs},
journal="Congr. Numer.",
volume=26,
year=1980,
pages="125--157"}
@article{erd-gircol,
author={P. Erd\H{o}s},
title={Graph Theory and Probability},
journal="Canad. J. Math",
volume=11,
year=1959,
pages="34--38"}
@phdthesis{dvorak,
author="Z. Dvo{\v{r}}{\'a}k",
title="Asymptotical structure of combinatorial objects",
school="Charles University in Prague",
year=2007}
@phdthesis{geelen,
author="J. Geelen",
title="Matchings, matroids and unimodular matrices",
school="University of Waterloo",
year=1995}
@article{GRS,
author = "J. F. Geelen and R. B. Richter and G. Salazar",
title = "Embedding grids in surfaces",
journal = " European J. Combin.",
volume = 25,
year = 2004,
pages = "785--792"}
@book{garey1979computers,
title={{Computers and Intractability: A Guide to the Theory of {NP}-completeness}},
author={Michael Garey and David Johnson},
isbn={0716710447},
year={1979},
publisher={WH Freeman \& Co. New York, NY, USA}}
@article{wagner,
author={K. Wagner},
year=1937,
title={{\"U}ber eine {E}igenschaft der ebenen {K}omplexe},
journal={Mathematische Annalen},
volume=114,
pages={570--590}}
@article{eppstein00,
author="D. Eppstein",
title="Diameter and treewidth in minor-closed graph families",
journal="Algorithmica",
volume=27,
year=2000,
pages="275--291"}
@article{grotzsch1959,
author={Herbert Gr{\"o}tzsch},
title={Ein {D}reifarbensatz f\"{u}r dreikreisfreie {N}etze auf der {K}ugel},
journal="Math.-Natur. Reihe",
volume=8,
year=1959,
pages="109--120"}
@article{Hl,
author = {P. Hlin\v{e}n\'y},
title = "Crossing-number critical graphs have bounded path-width",
journal = "J. Combin. Theory, Ser.~B",
volume = 88,
year = 2003,
pages = "347--367"}
@article{HS,
author = "P. Hlin\v{e}n\'y and G. Salazar",
title = {Stars and bonds in crossing-critical graphs},
journal = "J. Graph Theory",
volume = 65,
year = 2010,
pages = "198--215"}
@incollection{Karp,
author = {R. Karp},
booktitle = {Complexity of Computer Computations},
editor = {R. Miller and J. Thatcher},
pages = {85--103},
publisher = {Plenum Press},
title = {Reducibility among combinatorial problems},
year = 1972}
@article{ips,
title={The complexity of finding maximum disjoint paths with length constraints},
author={A. Itai and Y. Perl and Y. Shiloach},
journal={Networks},
volume={12},
number={3},
pages={277--286},
year={1982}}
@article{yang,
author="D. Yang",
title="Generalization of transitive fraternal augmentations for directed graphs and its applications",
journal="Discrete Math.",
number=309,
year=2009,
pages="4614--4623"}
@article{kierstead2003orderings,
title={Orderings on graphs and game coloring number},
author={Kierstead, HA and Yang, D.},
journal={Order},
volume={20},
number={3},
pages={255--264},
year={2003}}
@article{kierstead1994radius,
title={{Radius two trees specify $\chi$-bounded classes}},
author={H. Kierstead and S. Penrice},
journal={J. Graph Theory},
volume={18},
number={2},
pages={119--129},
year={1994}}
@article{kierstead2004radius,
title={Radius three trees in graphs with large chromatic number},
author={Kierstead, Hal A and Zhu, Yingxian},
journal={SIAM Journal on Discrete Mathematics},
volume={17},
number={4},
pages={571--581},
year={2004}
}
@article{kostomindeg,
author={Alexandr Kostochka},
title={{Lower bound of the {H}adwiger number of graphs by their average degree}},
journal="Combinatorica",
volume=4,
year=1984,
pages="307--316"}
@article{koyanore,
author = {Alexandr V. Kostochka and Matthew Yancey},
title = {Ore's conjecture on color-critical graphs is almost true},
journal = {J. Comb. Theory, Ser. {B}},
volume = {109},
pages = {73--101},
year = {2014}
}
@article{koyan,
author = {Alexandr V. Kostochka and Matthew Yancey},
title = {Ore's conjecture for $k=4$ and Gr{\"{o}}tzsch's Theorem},
journal = {Combinatorica},
volume = {34},
number = {3},
pages = {323--329},
year = {2014}
}
@article{thommindeg,
author={A. Thomason},
title={The extremal function for complete minors},
journal={J. Combin. Theory, Ser.~B},
volume=81,
year=2001,
pages={318--338}}
@article{BoTh,
author={B. Bollob\'as and A. Thomason},
title={Proof of a conjecture of {M}ader, {E}rd{\H{o}}s and {H}ajnal on topological complete subgraphs},
journal={European J. Combin.},
volume=19,
year=1998,
pages={883--887}}
@article{kostochka1997covering,
title={{Covering and coloring polygon-circle graphs}},
author={A. Kostochka and J. Kratochv{\'\i}l},
journal={Discrete Math.},
volume={163},
number={1-3},
pages={299--305},
year={1997}}
@article{krattuza1994,
author={J. Kratochv\'{\i}l and Z.~Tuza},
title={Algorithmic complexity of list colorings},
journal="Discrete Appl. Math.",
volume=50,
year=1994,
pages="297--302"}
@article{lam2005-356,
author={P. C. B. Lam and W. C. Shiu and Z. M. Song},
title={The 3-choosability of plane graphs of girth 4},
journal="Discrete Math.",
volume=294,
year=2005,
pages="297--301"}
@article{li2008,
author={X. Li},
title={On $3$-choosable planar graphs of girth at least $4$},
journal="Discrete Math.",
volume=309,
year=2009,
pages="2424--2431"}
@article{lidicky2008-3678,
author={B. Lidick\'y},
title={On 3-choosability of plane graphs without 6-, 7- and 8-cycles},
journal="Australasian J. Combin.",
volume=44,
year=2009,
pages="77--86"}
@article{sperft,
author={M. Chudnovsky and N. Robertson and P. Seymour and R. Thomas},
title={The strong perfect graph theorem},
journal = "Annals of Mathematics",
year=2006,
volume=164,
pages="51--229"}
@article{nessurvey,
title={Structural properties of sparse graphs},
author={J. Ne{\v{s}}et\v{r}il and P. {Ossona de Mendez}},
journal={Bolyai Society Mathematical Studies},
volume=19,
pages={369--426},
year=2008}
@article{oum,
author={S. Oum and P. Seymour},
title={Approximating clique-width and branch-width},
journal={J. Combin. Theory, Ser.~B},
volume=96,
year=2006,
pages="514--528"}
@inproceedings{raz1997sub,
title={A sub-constant error-probability low-degree test, and a sub-constant error-probability \textnormal{PCP} characterization of \textnormal{NP}},
author={R. Raz and S. Safra},
booktitle={Proceedings of the twenty-ninth annual ACM symposium on Theory of computing},
pages={475--484},
year={1997},
organization={ACM}
}
@article{gmarx,
author = {M. Grohe and D. Marx},
title = {Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs},
journal = {SIAM J. Comput.},
volume = 44,
year = 2015,
pages = {114--159}
}
@article{KoSz,
author={J. Koml{\'o}s and E. Szemer{\'e}di},
title={Topological cliques in graphs. {II}},
journal={Combin. Probab. Comput.},
volume=5,
year=1996,
pages={79--90}}
@article{moharmin,
author = {B. Mohar},
title = {The excluded minor structure theorem with planarly embedded wall},
journal = {ArXiv},
archivePrefix = "arXiv",
volume = {0909.4329},
year = 2009,
month = sep
}
@article{rs2,
title={Graph minors. {II}. {A}lgorithmic aspects of tree-width},
author={Robertson, Neil and Seymour, Paul D.},
journal={Journal of Algorithms},
volume={7},
number={3},
pages={309--322},
year={1986}
}
@article{rs3,
title={Graph {M}inors. {III}. {P}lanar tree-width},
author={Robertson, N. and Seymour, P.D.},
journal={Journal of Combinatorial Theory, Series~B},
volume={36},
pages={49--64},
year={1984}
}
@ARTICLE{seymgrid,
author = {{Chudnovsky}, M. and {Dvo{\v r}{\'a}k}, Z. and {Klimo{\v s}ov{\'a}}, T. and
{Seymour}, P.},
title = "{Immersion in four-edge-connected graphs}",
journal = {ArXiv},
archivePrefix = "arXiv",
volume = {1308.0827},
year = 2013,
month = aug
}
@ARTICLE{dvoklim,
author = {{Dvo{\v r}{\'a}k}, Z. and {Klimo{\v s}ov{\'a}}, T.},
title = "{Strong immersions and maximum degree}",
journal = {ArXiv},
archivePrefix = "arXiv",
volume = {1304.0728},
year = 2013,
month = apr
}
@article{RSey,
author = "Neil Robertson and Paul D. Seymour",
title = {Graph {M}inors. {V}. {E}xcluding a planar graph},
journal = "J. Combin. Theory, Ser.~B",
volume = 41,
year = 1986,
pages = "92--114"}
@article{rs9,
author = {N. Robertson and P. D. Seymour},
title = {Graph {M}inors. {IX}. {D}isjoint crossed paths},
journal = {J. Combin. Theory, Ser.~B},
volume = {49},
number = {1},
year = {1990},
pages = {40--77}
}
@article{rs10,
author = {N. Robertson and P. D. Seymour},
title = {Graph {M}inors. {X}. {O}bstructions to tree-decomposition},
journal = {J. Combin. Theory, Ser.~B},
volume = {52},
number = {2},
year = {1991},
pages = {153--190}
}
@article{rs11,
author = {N. Robertson and P. D. Seymour},
title = {Graph {M}inors. {XI}. {C}ircuits on a Surface},
journal = {J. Combin. Theory, Ser.~B},
volume = {60},
number = {1},
year = {1994},
pages = {72--106}
}
@article{rs12,
author = {N. Robertson and P. D. Seymour},
title = {Graph {M}inors. {XII}. {D}istance on a Surface},
journal = {J. Combin. Theory, Ser.~B},
volume = {64},
number = {2},
year = {1995},
pages = {240--272}
}
@article{rs7,
author = {N. Robertson and P. D. Seymour},
title = {Graph {M}inors {VII}. {D}isjoint paths on a surface},
journal = {J. Combin. Theory, Ser.~B},
volume = 45,
year = 1988,
pages = "212--254"}
@article{rs13,
title={Graph {M}inors. {XIII}. {T}he disjoint paths problem},
author = {N. Robertson and P. D. Seymour},
journal = {J. Combin. Theory, Ser.~B},
volume={63},
pages={65--110},
year={1995}
}
@article{rs14,
author = {N. Robertson and P. D. Seymour},
title = {Graph {M}inors. {XIV}. {E}xtending an Embedding},
journal = {J. Combin. Theory, Ser.~B},
volume = {65},
number = {1},
year = {1995},
pages = {23--50}
}
@article{rs15,
author = {N. Robertson and P. D. Seymour},
title = {Graph {M}inors. {XV}. {G}iant Steps},
journal = {J. Combin. Theory, Ser.~B},
volume = {68},
number = {1},
year = {1996},
pages = {112--148}
}
@article{rs17,
author = {N. Robertson and P. D. Seymour},
title = {Graph {M}inors: {XVII}. {T}aming a Vortex},
journal = {J. Combin. Theory, Ser.~B},
volume = {77},
number = {1},
year = {1999},
pages = {162--210}
}
@article{rs20,
author = {N. Robertson and P. D. Seymour},
title = {Graph {M}inors. {XX}. {W}agner's conjecture},
journal = {J. Combin. Theory, Ser.~B},
volume = {92},
number = {2},
year = {2004},
pages = {325--357}
}
@article{rs23,
author = {N. Robertson and P. D. Seymour},
title = {Graph {M}inors. {XXIII}. {N}ash-{W}illiams' immersion conjecture},
journal = {J. Combin. Theory, Ser.~B},
volume = {100},
number = {2},
year = {2010},
pages = {181--205}
}
@article{robertson2003graph,
author = {N. Robertson and P. D. Seymour},
title={{Graph {M}inors. {XVI}. {E}xcluding a non-planar graph}},
journal={J. Combin. Theory, Ser.~B},
volume={89},
number={1},
pages={43--76},
year={2003}}
@article{quickly,
author = {N. Robertson and P. D. Seymour and R. Thomas},
title = {Quickly Excluding a Planar Graph},
journal = {J. Combin. Theory, Ser.~B},
volume = {62},
number = {2},
year = {1994},
pages = {323--348}
}
@article{thomassen1994,
author={C. Thomassen},
title={Every planar graph is 5-choosable},
journal="J. Combin. Theory, Ser.~B",
volume=62,
year=1994,
pages="180--181"}
@article{thomassen1995-34,
author={C. Thomassen},
title={3-list-coloring planar graphs of girth 5},
journal="J. Combin. Theory, Ser.~B",
volume=64,
year=1995,
pages="101--107"}
@article{ThoShortlist,
author={C. Thomassen},
title={A short list color proof of {G}r{\"o}tzsch's theorem},
journal="J. Combin. Theory, Ser.~B",
volume=88,
year=2003,
pages="189--192"}
@article{thomassen-surf,
author="C. Thomassen",
title="The chromatic number of a graph of girth 5 on a fixed surface",
journal="J. Combin. Theory, Ser.~B",
volume=87,
year=2003,
pages="38--71"}
@article{tw-klein,
author="R. Thomas and B. Walls",
title="Three-coloring {K}lein bottle graphs of girth five",
journal="J. Combin. Theory, Ser.~B",
volume=92,
year=2004,
pages="115--135"}
@article{Youngs,
author={D. Youngs},
title={4-chromatic projective graphs},
journal="Journal of Graph Theory",
volume=21,
year=1996,
pages="219--227"}
@article{gimbel,
author={J. Gimbel and C. Thomassen},
title={Coloring graphs with fixed genus and girth},
journal="Trans. Amer. Math. Soc.",
volume=349,
year=1997,
pages="4555--4564"}
@article{grunbaum,
author="B. Gr{\"u}nbaum",
title="Gr{\"o}tzsch's theorem on 3-colorings",
journal="Michigan Math. J.",
volume=10,
year=1963,
pages="303--310"}
@article{conj-havel,
author="I. Havel",
title={On a conjecture of {B}. {G}r\"unbaum},
journal="J. Combin. Theory, Ser.~B",
volume=7,
year=1969,
pages="184--186"}
@article{havel-zbarv,
author="I. Havel",
title={O zbarvitelnosti rovinn\'ych graf\r{u} t\v{r}emi barvami},
journal="Mathematics (Geometry and Graph Theory)",
publisher="Univ. Karlova, Prague",
year=1970,
pages="89--91"}
@article{vizing,
author={V. G. Vizing},
title={On an estimate of the chromatic class of a p-graph},
journal="Diskret. Analiz.",
volume=3,
year=1964,
pages="25--30"}
@article{vizing1976,
author={V. G. Vizing},
title={Vertex colorings with given colors (in Russian)},
journal="Metody Diskret. Analiz, Novosibirsk",
volume=29,
year=1976,
pages="3--10"}
@article{voigt1993,
author={M. Voigt},
title={List colourings of planar graphs},
journal="Discrete Math.",
volume=120,
year=1993,
pages="215--219"}
@article{voigt1995,
author={M. Voigt},
title={A not 3-choosable planar graph without 3-cycles},
journal="Discrete Math.",
volume=146,
year=1995,
pages="325--328"}
@article{ringel,
author="G. Ringel and J. W. T. Youngs",
title="Solution of the {H}eawood map-coloring problem",
journal="Proc. Nat. Acad. Sci. U.S.A.",
volume=60,
year=1968,
pages="438--445"}
@article{franklin,
author = "P. Franklin",
title = "A {S}ix {C}olour {P}roblem",
journal= "J. Math. Phys.",
volume = 13,
year = 1934,
pages = "363--369"}
@book{ore,
author = {O. Ore},
title={{The Four Color Problem}},
publisher={Academic Press, New York},
year=1967}.
@book{diestel,
author = {R. Diestel},
edition = {Third},
publisher = {Springer-Verlag, Heidelberg},
series = {Graduate Texts in Mathematics},
title = {{Graph Theory}},
volume = 173,
year = 2005}
@phdthesis{walls,
author="B. Walls",
title="Coloring girth restricted graphs on surfaces",
school="Georgia Institute of Technology",
year=1999}
@article{zhang2005-3589,
author={H. Zhang},
title={On 3-choosability of plane graphs without 5-, 8- and 9-cycles},
journal="J. Lanzhou Univ., Nat. Sci.",
volume=41,
year=2005,
pages="93--97"}
@article{zhang2004-3679,
author={H. Zhang and B. Xu},
title={On 3-choosability of plane graphs without 6-, 7- and 9-cycles},
journal="Appl. Math. J. Chinese Univ., Ser.~B (Engl. Ed.)",
volume=19,
year=2004,
pages="109--115"}
@article{zhang2006-389,
author={H. Zhang and B. Xu and Z. Sun},
title={Every plane graph with girth at least 4 without 8- and 9-circuits is 3-choosable},
journal="Ars Comb.",
volume=80,
year=2006,
pages="247--257"}
@article{zhu2009colouring,
title={Colouring graphs with bounded generalized colouring number},
author={X. Zhu},
journal={Discrete Math.},
volume={309},
number={18},
pages={5562--5568},
year={2009},
publisher={Elsevier}}
@article{zhu2007-389,
author={X. Zhu and M. Lianying and C. Wang},
title={On 3-choosability of plane graphs without 3-, 8- and 9-cycles},
journal="Australas. J. Comb.",
volume=38,
year=2007,
pages="249--254"}
@inproceedings{kawmoh,
author = {Kawarabayashi, {Ken-ichi} and Mohar, Bojan},
title = {List-color-critical graphs on a fixed surface},
booktitle = {Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms},
series = {SODA '09},
year = {2009},
location = {New York, New York},
pages = {1156--1165},
publisher = {Society for Industrial and Applied Mathematics},
address = {Philadelphia, PA, USA}
}
@article{Axenovich20111046,
title = "List precoloring extension in planar graphs",
journal = "Discrete Math.",
volume = "311",
number = "12",
pages = "1046--1056",
year = "2011",
author = "Maria Axenovich and Joan P. Hutchinson and Michelle A. Lastrina"
}
@article{arr1,
author = "V. R{\"o}dl and R. Thomas",
title = "Arrangeability and clique subdivisions",
journal = "Algorithms Combin.",
volume = 14,
year = 1997,
pages="236--239"}
@article{arr2,
author = "G. Chen and R. Schelp",
title = "Graphs with linearly bounded {R}amsey numbers",
journal = "J. Combin. Theory, Ser.~B",
volume=57,
year = 1993,
pages = "138--149"}
@article{arr3,
author = "H. Kierstead and W. Trotter",
title = "Planar graph coloring with an uncooperative partner",
journal = "J. Graph Theory",
volume = 18,
year = 1994,
pages = "569--584"}
@article{devospart,
author = {Matt DeVos and Guoli Ding and Bogdan Oporowski and Daniel Sanders and Bruce Reed and Paul Seymour and Dirk Vertigan},
title = {Excluding any graph as a minor allows a low tree-width 2-coloring},
journal = {J. Comb. Theory, Ser. B},
volume = 91,
year = 2004,
pages = {25--41}
}
@inproceedings{contrpart,
author = {E. Demaine and M. Hajiaghayi and K. Kawarabayashi},
title = {Contraction Decomposition in {H}-minor-free Graphs and Algorithmic Applications},
booktitle = {Proceedings of the Forty-third Annual ACM Symposium on Theory of Computing},
series = {STOC '11},
year = {2011},
pages = {441--450},
publisher = {ACM}
}
@article{twd,
author = {Z. Dvo{\v{r}}{\'a}k},
title = {Sublinear separators, fragility and subexponential expansion},
journal = "European Journal of Combinatorics ",
volume = 52,
pages = "103--119",
year = 2016}
@article{gridtw,
author = {E. Berger and Z. Dvo{\v{r}}{\'a}k and S. Norin},
title = {Treewidth of grid subsets},
year = 2017,
journal = "Combinatorica",
note = "Accepted, \url{doi.org/10.1007/s00493-017-3548-5}"}
@article{induced,
author = {J. Ne\v{s}et\v{r}il and P. {Ossona de Mendez}},
title = "Induced Matchings and Induced Paths in Graphs",
journal = {ITI series},
volume = 335,
year = 2007}
@article{domker,
author = {P{\aa}l Gr{\o}n{\aa}s Drange and
Markus S. Dregi and
Fedor V. Fomin and
Stephan Kreutzer and
Daniel Lokshtanov and
Marcin Pilipczuk and
Michal Pilipczuk and
Felix Reidl and
Saket Saurabh and
Fernando Sanchez Villaamil and
Somnath Sikdar},
title = {Kernelization and Sparseness: the case of Dominating Set},
journal = {arXiv},
volume = {1411.4575},
year = {2014}
}
@article{smallcl,
author = "Z. Dvo{\v{r}}{\'a}k and Serguei Norine",
title = "Small graph classes and bounded expansion",
journal = "Journal of Combinatorial Theory, Series B",
volume = 100,
pages = "171--175",
year = 2010
}
@article{apxindep,
title={Completeness in standard and differential approximation classes: {P}oly-({D}){APX}-and ({D}){PTAS}-completeness},
author={Bazgan, Cristina and Escoffier, Bruno and Paschos, Vangelis Th.},
journal={Theoretical Computer Science},
volume={339},
number={2},
pages={272--292},
year={2005}
}
@article{dnorin,
author = {Z. Dvo{\v{r}}{\'a}k and S. Norin},
title = {Treewidth of graphs with balanced separations},
year = 2019,
journal = {Journal of Combinatorial Theory, Series B},
volume = 137,
pages = "137--144"}
@unpublished{septw-v1,
author = {Z. Dvo{\v{r}}{\'a}k and S. Norin},
title = {Treewidth of graphs with balanced separations},
note = "\url{http://arxiv.org/abs/1408.3869v1}"
}
@article{komszem2,
author = {J. Koml{\'o}s and E. Szemer{\'e}di},
title = {Topological cliques in graphs {II}},
journal = {Comb. Probab. Comput.},
volume = 5,
year = 1996,
pages = {79--90}}
@article{kopyb,
author = {A. Kostochka and L. Pyber},
title = {Small topological complete subgraphs of "dense" graphs},
journal = {Combinatorica},
volume = 8,
year = 1988,
pages = {83--86}
}
@article{DKM,
author = "M. DeVos and K. Kawarabayshi and B. Mohar",
title = "Locally planar graphs are $5$-choosable",
journal = "J. Combin. Theory, Ser.~B",
volume = 98,
year = 2008,
pages = "1215--1232"}
@article{Er,
author = "P. Erd\H{o}s",
title="Graph theory and probability",
journal="Canad. J. Math.",
volume=11,
year=1959,
pages="34--38"}
@article{mattpriv,
author = {M. {DeVos} and J. {McDonald} and B. {Mohar} and D. {Scheide}},
title = "{A note on forbidding clique immersions}",
journal = {ArXiv},
volume = {1207.2117},
year = 2012,
month = jul,
}
@article{mindim,
author = {M. {DeVos} and Z. Dvo{\v{r}}{\'a}k and J. Fox and J. {McDonald} and B. {Mohar} and D. {Scheide}},
title = {Minimum degree condition forcing complete graph immersion},
journal = {Combinatorica},
volume = 34,
year = 2014,
pages = "279--298"
}
@misc{pothompriv,
author="L. Postle and R. Thomas",
year= 2012,
howpublished="Personal communication"}
@phdthesis{lukethe,
author="L. Postle",
title="5-List-Coloring Graphs on Surfaces",
school="Georgia Institute of Technology",
year=2012}
}
@article{wollims,
title = "The structure of graphs not admitting a fixed immersion",
journal = "Journal of Combinatorial Theory, Series B",
volume = 110,
pages = "47--66",
year = 2015,
author = "Paul Wollan"
}
@article{topmin,
author={Z. Dvo{\v{r}}{\'a}k},
title="A stronger structure theorem for excluded topological minors",
journal = {ArXiv},
archivePrefix = "arXiv",
volume = {1209.0129},
year = 2012,
month = sep
}
@article{thilinfdeg,
title={Searching for a visible, lazy fugitive},
author={Richerby, D. and Thilikos, D.M.},
journal={SIAM Journal on Discrete Mathematics},
volume={25},
pages={497},
year={2011}
}
@article{bib-dai,
author="D. Dailey",
title="Uniqueness of colorability and colorability of planar 4-regular graphs are {NP}-complete",
journal="Discrete Math.",
volume=30,
year=1980,
pages="289--293"}
@inproceedings{apxdomindeg,
author = {C. Lenzen and R. Wattenhofer},
title = {Minimum dominating set approximation in graphs of bounded arboricity},
booktitle = {Proceedings of the 24th international conference on Distributed computing},
series = {DISC'10},
year = {2010},
pages = {510--524},
publisher = {Springer-Verlag},
address = {Berlin, Heidelberg},
}
@article{demainesurf,
author = {E. Demaine and F. Fomin and M. Hajiaghayi and D. Thilikos},
title = {Subexponential parameterized algorithms on bounded-genus graphs and {H}-minor-free graphs},
journal = {J. ACM},
volume = {52},
year = {2005},
pages = {866--893}
}
@article{eigran,
author = {F. Eisenbrand and F. Grandoni},
title = "On the complexity of fixed parameter clique and dominating set",
journal = "Theoretical Computer Science",
volume = 326,
year=2004,
pages = "57--67"
}
@article{KloZhang,
author={W. Klostermeyer and C. Q. Zhang},
title={$(2+\epsilon)$-coloring of planar graphs with large odd-girth},
journal={J. Graph Theory},
volume=33,
year=2000,
pages="109--119"
}
@article{klokmil,
author={T. Kloks and D. Kratsch and H. M{\"u}ller},
title = "Finding and counting small induced subgraphs efficiently",
journal = "Information Processing Letters",
volume = 74,
year=2000,
pages = "115--121"
}
@inproceedings{epphin,
author = {D. Eppstein and M. Goodrich and D. Strash and L. Trott},
title = {Extended dynamic subgraph statistics using h-index parameterized data structures},
booktitle = {Proceedings of the 4th international conference on Combinatorial optimization and applications - Volume Part I},
series = {COCOA'10},
year = {2010},
pages = {128--141},
publisher = {Springer-Verlag}
}
@article{thoheck,
author = {C. Heckman and R. Thomas},
title = {A new proof of the independence ratio of triangle-free cubic graphs},
journal = "Discrete Math.",
volume = 233,
year = 2001,
pages = {233--237}
}
@article{HeTh06,
author = {C. Heckman and R. Thomas},
title = {Independent sets in triangle-free cubic planar graphs},
journal = {J. Combin. Theory Ser. B},
volume = 96,
year = 2006,
pages = {253--275}
}
@article{tuvoigt,
author = {Zs. Tuza and M. Voigt},
title = {Every 2-choosable graph is $(2m,m)$-choosable},
journal = "J. Graph Theory",
volume = 22,
year = 1996,
pages = {245--252}
}
@article{bioinformatics,
title={Uncovering biological network function via graphlet degree signatures},
author={Milenkovi{\ae}, Tijana and Pr{\v{z}}ulj, Nata{\v{s}}a},
journal={Cancer informatics},
volume={6},
pages={257},
year={2008},
publisher={Libertas Academica}
}
@article{social_networking,
title={Advances in exponential random graph ($p^\ast$) models},
author={Robins, Garry and Morris, Martina},
journal={Social Networks},
volume={29},
number={2},
pages={169--172},
year={2007},
publisher={Elsevier}
}
@article{mader,
author={W. Mader},
title={A reduction method for edge-connectivity in graphs},
journal={Annals of Discrete Mathematics},
volume=3,
year=1978,
pages={145--164}}
@article{frank,
author={A. Frank},
title={On a theorem of {M}ader},
journal={Discrete Mathematics},
volume=101,
year=1992,
pages={49--57}}
@inproceedings{expand,
author={A. Lubotzky and R. Phillips and P. Sarnak},
title={Ramanujan conjectures and explicit constructions of expanders},
booktitle={Proc. ACM Symposium on the Theory of Computation},
year=1986,
pages={240-246}}
@unpublished{weakdeg,
author = {D. Marx and P. Wollan},
title={Immersions in highly connected graphs},
note="Manuscript",
year=2013}
@article{liuthom,
author = {C.-H. Liu and R. Thomas},
journal="ArXiv",
title={Excluding subdivisions of bounded degree graphs},
volume={1407.4428},
year=2014}
@article{aksenov77,
author="V. A. Aksenov",
title="Chromatic connected vertices in planar graphs",
note="in Russian",
journal="Diskret. Analiz",
volume=31,
year=1977,
pages="5--16"}
@article{JT00,
author={T. Jensen and C. Thomassen},
title={The color space of a graph},
journal="J. Graph Theory",
volume=34,
year=2000,
pages="234--245"}
@article{aksenovetal02,
author="V. A. Aksenov and O. V. Borodin and N. A. Glebov",
title="On the continuation of a 3-coloring from two vertices in a plane graph without 3-cycles",
note="in Russian",
journal="Diskretn. Anal. Issled. Oper. Ser. 1",
volume=9,
year=2002,
pages="3--36"}
@article{borodinKLY2014,
author={O.V. Borodin and A.V. Kostochka and B. Lidick{\'{y}} and M. Yancey},
title={Short proofs of coloring theorems on planar graphs},
journal={European Journal of Combinatorics},
volume={36},
pages={314--321},
year={2014}}
@article{alonlchoos,
title = "Choosability and fractional chromatic numbers",
journal = "Discrete Mathematics ",
volume = "165--166",
pages = "31 - 38",
year = "1997",
note = "Graphs and Combinatorics ",
author = "N. Alon and Zs. Tuza and M. Voigt"
}
@inproceedings{alon1990separator,
title={A separator theorem for graphs with an excluded minor and its applications},
author={Alon, Noga and Seymour, Paul and Thomas, Robin},
booktitle={Proceedings of the twenty-second annual ACM symposium on Theory of computing},
pages={293--299},
year={1990},
organization={ACM}
}
@inproceedings{schaefer,
title={The complexity of satisfiability problems},
author={Schaefer, Thomas},
booktitle={Proceedings of the tenth annual ACM symposium on Theory of computing},
pages={216--226},
year={1978},
publisher = {ACM}
}
@article{moret,
author = {Moret, B. M. E.},
title = {Planar {NAE3SAT} is in {P}},
journal = {SIGACT News},
volume = {19},
number = {2},
year = {1988},
pages = {51--54},
publisher = {ACM},
address = {New York, NY, USA}
}
@article{1in3,
author = {Mulzer, Wolfgang and Rote, G\"{u}nter},
title = {Minimum-weight Triangulation is {NP}-hard},
journal = {J. ACM},
volume = {55},
number = {2},
year = {2008},
articleno = {11}
}
@article{matching,
author = {Edmonds, Jack},
year=1965,
title={Paths, trees, and flowers},
journal={Canad. J. Math.},
volume = 17,
pages = "449--467"
}
@article{feder1,
author = {Tomas Feder},
title = {Fanout limitations on constraint systems},
journal = {Theor. Comput. Sci.},
volume = 255,
pages = "281--293",
year = 2001
}
@article{feder2,
author = {Tomas Feder and Daniel K. Ford},
title = {Classification of Bipartite Boolean Constraint Satisfaction through {D}elta-Matroid Intersection},
journal = {SIAM J. Discrete Math.},
volume = 20,
pages = "372--394",
year = 2006
}
@article{DSV08,
author = {Z. Dvo\v{r}\'{a}k and R. \v{S}krekovski and T. Valla},
title = {Planar graphs of odd-girth at least 9 are homomorphic to the {P}etersen graph},
journal = {SIAM J. Discrete Math.},
volume = 22,
pages = "568--591",
year = 2008
}
@incollection{dalmau,
year={2003},
booktitle={Mathematical Foundations of Computer Science 2003},
volume={2747},
series={Lecture Notes in Computer Science},
editor={Rovan, Branislav and Vojtas, Peter},
title={Generalized Satisfiability with Limited Occurrences per Variable: {A} Study through {Delta-Matroid Parity}},
publisher={Springer Berlin Heidelberg},
author={Dalmau, Victor and Ford, Daniel K.},
pages="358--367"
}
@article{courcelle,
title={The monadic second-order logic of graphs. {I}. {R}ecognizable sets of finite graphs},
author={Courcelle, Bruno},
journal={Information and computation},
volume={85},
number={1},
pages={12--75},
year={1990},
publisher={Elsevier}
}
@article{spqr,
author={Mac Lane, Saunders},
year=1937,
title={A structural characterization of planar combinatorial graphs},
journal={Duke Mathematical Journal},
volume=3,
pages={460-472}
}
@unpublished{istrate,
author={Gabriel Istrate},
title={Looking for a version of {S}chaefer's dichotomy theorem when each variable occurs at most twice},
year=1997,
note="Technical Report TR652, The University of Rochester"
}
@article{gim97,
title = "The linear {D}elta-matroid parity problem",
journal = "Journal of Combinatorial Theory, Series B",
volume = "88",
number = "2",
pages = "377-398",
year = 2003,
author = "James F. Geelen and Satoru Iwata and Kazuo Murota"
}
@article{wenzel,
title = "{$\Delta$}-matroids with the strong exchange conditions",
journal = "Applied Mathematics Letters",
volume = "6",
pages = "67-70",
year = "1993",
author = "Walter Wenzel"
}
@article{federvardi,
title={The computational structure of monotone monadic {SNP} and constraint satisfaction: {A} study through {D}atalog and group theory},
author={Feder, Tom{\'a}s and Vardi, Moshe Y.},
journal={SIAM Journal on Computing},
volume={28},
number={1},
pages={57-104},
year={1998}
}
@inproceedings{barko1,
author = {Barto, Libor and Kozik, Marcin},
title = {Constraint Satisfaction Problems of Bounded Width},
booktitle = {Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science},
year = {2009},
pages = {595--603},
publisher = {IEEE Computer Society},
address = {Washington, DC, USA}
}
@article{barko2,
title={The {CSP} dichotomy holds for digraphs with no sources and no sinks (a positive answer to a conjecture of {B}ang-{J}ensen and {H}ell)},
author={Barto, Libor and Kozik, Marcin and Niven, Todd},
journal={SIAM Journal on Computing},
volume={38},
number={5},
pages={1782--1802},
year={2009}
}
@article{buje,
title={Classifying the complexity of constraints using finite algebras},
author={Bulatov, Andrei and Jeavons, Peter and Krokhin, Andrei},
journal={SIAM Journal on Computing},
volume={34},
number={3},
pages={720--742},
year={2005}
}
@article{bula,
title={A dichotomy theorem for constraint satisfaction problems on a 3-element set},
author={Bulatov, Andrei},
journal={Journal of the ACM (JACM)},
volume={53},
number={1},
pages={66--120},
year={2006}
}
@inproceedings{cai2010holographic,
title={Holographic algorithms with matchgates capture precisely tractable planar \#{CSP}},
author={Cai, Jin-Yi and Lu, Pinyan and Xia, Mingji},
booktitle = {Proceedings of the 2010 51st Annual IEEE Symposium on Foundations of Computer Science},
pages={427--436},
year=2010,
publisher = {IEEE Computer Society},
address = {Washington, DC, USA}
}
@inproceedings{heng13complexity,
author = {Guo, Heng and Williams, Tyson},
title={The complexity of planar {B}oolean \#{CSP} with complex weights},
booktitle = {Proceedings of the 40th International Conference on Automata, Languages, and Programming - Volume Part I},
year = 2013,
pages = {516--527},
publisher = {Springer-Verlag},
address = {Berlin, Heidelberg}
}
@article{kawthorem,
title = "From the plane to higher surfaces",
journal = "Journal of Combinatorial Theory, Series B ",
volume = "102",
number = "4",
pages = "852--868",
year = 2012,
author = "{Ken-ichi} Kawarabayashi and Carsten Thomassen"
}
@article{kolesnik2014lower,
title={Lower bounds for the isoperimetric numbers of random regular graphs},
author={Kolesnik, Brett and Wormald, Nick},
journal={SIAM Journal on Discrete Mathematics},
volume=28,
number=1,
pages={553--575},
year=2014
}
@book{ScheinermanUllman2011,
AUTHOR = {Scheinerman, Edward R. and Ullman, Daniel H.},
TITLE = {Fractional graph theory},
PUBLISHER = {Dover Publications Inc.},
ADDRESS = {Mineola, NY},
YEAR = {2011},
PAGES = {xviii+211},
ISBN = {978-0-486-48593-5; 0-486-48593-5},
MRCLASS = {05-02 (05C72)},
MRNUMBER = {2963519},
}
@incollection{Burr1975,
title = {On the magnitude of generalized {Ramsey} numbers for graphs},
booktitle = {Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erd{\H o}s on his 60th birthday), Vol. 1},
publisher = {North-Holland, Amsterdam},
author = {Burr, S. A. and Erd\H{o}s, P.},
year = {1975},
pages = {215--240. Colloq. Math. Soc. J{\'a}nos Bolyai, Vol. 10}
}
@article{Kierstead2009,
title = {The Two-Coloring Number and Degenerate Colorings of Planar Graphs},
volume = {23},
doi = {10.1137/070703697},
number = {3},
journal = {{SIAM} J. Discrete Math.},
author = {Kierstead, H. and Mohar, B. and {\v S}pacapan, S. and Yang, D. and Zhu, X.},
month = jan,
year = {2009},
pages = {1548--1560}
}
@article{colplanarnpc,
title = "Some simplified {NP}-complete graph problems",
journal = "Theoretical Computer Science",
volume = "1",
number = "3",
pages = "237--267",
year = "1976",
author = "M.R. Garey and D.S. Johnson and L. Stockmeyer"
}
@article{borsurvey,
title = "Colorings of plane graphs: A survey",
journal = "Discrete Mathematics",
volume = "313",
number = "4",
pages = "517--539",
year = "2013",
author = "O.V. Borodin"
}
@article{Voigt45,
title = "A non-3-choosable planar graph without cycles of length 4 and 5",
journal = "Discrete Mathematics",
volume = "307",
number = "7-8",
pages = "1013--1015",
year = "2007",
author = "M. Voigt"
}
@article {choos49,
author = {Borodin, O. V.},
title = {Structural properties of plane graphs without adjacent triangles and an application to 3-colorings},
journal = {Journal of Graph Theory},
volume = {21},
number = {2},
pages = {183--186},
year = {1996}
}
@article {PU02,
author = {A. Pirnazar and D. H. Ullman},
title = {Girth and fractional chromatic number of planar graphs},
journal = {Journal of Graph Theory},
volume = 39,
pages = {201--217},
year = 2002
}
@article{fleischsplit,
author={H. Fleischner},
title={Eularian Graphs and Related Topics, Part 1},
journal={Ann. Discrete Math.},
volume={45},
publisher={North Holland, Amsterdam},
year=1990}
@article{win1989connection,
title={On a connection between the existence of $k$-trees and the toughness of a graph},
author={Win, Sein},
journal={Graphs and Combinatorics},
volume={5},
number={1},
pages={201--205},
year={1989},
publisher={Springer}}
@article{haglist,
title={New bounds on the list-chromatic index of the complete graph and other simple graphs},
author={H{\"a}ggkvist, Roland and Janssen, Jeannette},
journal={Combinatorics, Probability and Computing},
volume={6},
number={03},
pages={295--313},
year={1997},
publisher={Cambridge Univ Press}
}
@article{DKMO,
author = {M. DeVos and K. Kawarabayashi and B. Mohar and H. Okamura},
title = {Immersing small complete graphs},
journal = {Ars Math. Contemp.},
volume = 3,
year = 2010,
pages = "139--146"
}
@incollection{abu2003graph,
year={2003},
booktitle={Computing and Combinatorics},
volume={2697},
series={Lecture Notes in Computer Science},
editor={Warnow, Tandy and Zhu, Binhai},
title={Graph Coloring and the Immersion Order},
publisher={Springer Berlin Heidelberg},
author={Abu-Khzam, Faisal and Langston, Michael},
pages={394--403}
}
@article{hadwiger,
author={H. Hadwiger},
title={{\"{U}ber eine Klassifikation der Streckenkomplexe}},
journal ={Vierteljschr. Naturforsch. Ges. Z\"{u}rich},
volume=88,
year=1943,
pages={133-143}
}
@article{lesuremeyniel,
author={F. Lescure and H. Meyniel},
title={On a problem upon configurations contained in graphs with given chromatic number},
year={1989},
journal={Ann. Discrete Math.},
note={Graph theory in memory of G.A. Dirac (Sandbjerg,1985)},
volume={41},
pages={325-331}
}
@article{robertsonseymourthomas,
author={N. Robertson and P. D. Seymour and R. Thomas},
title={{Hadwiger's conjecture for $K_6$-free graphs}},
journal={Combinatorica},
number={13},
year={1993},
pages={279-361}
}
@article{kostochka,
author={A. Kostochka},
title={{Lower bound of the Hadwiger number of graphs by their average degree}},
journal={Combinatorica},
year=1984,
volume =4,
pages={307-316}
}
@article{collinsheenehan,
author={Collins, K. L. and Heenehan, M. E.},
year={2014},
title={{Constructing Graphs with No Immersion of Large Complete Graphs}},
journal={Journal of Graph Theory},
volume={77},
pages={1-18}
}
@inproceedings{twchu1,
author = {Chekuri, Chandra and Chuzhoy, Julia},
title = {Polynomial Bounds for the Grid-minor Theorem},
booktitle = {Proceedings of the 46th Annual ACM Symposium on Theory of Computing},
series = {STOC '14},
year = {2014},
pages = {60--69},
publisher = {ACM},
address = {New York, NY, USA}
}
@inproceedings{twchu2,
author = {Chuzhoy, Julia},
title = {Excluded Grid Theorem: Improved and Simplified},
booktitle = {Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing},
series = {STOC '15},
year = {2015},
pages = {645--654},
publisher = {ACM},
address = {New York, NY, USA}
}
@article{bramble,
title={Graph searching and a min-max theorem for tree-width},
author={Seymour, Paul D and Thomas, Robin},
journal={Journal of Combinatorial Theory, Series B},
volume={58},
number={1},
pages={22--33},
year={1993}
}
@article{papavemp,
title={On the approximability of the traveling salesman problem},
author={C. H. Papadimitriou and S. Vempala},
journal={Combinatorica},
volume=26,
pages={101--120},
year=2006}
@techreport{christo,
title={Worst-case analysis of a new heuristic for the travelling salesman problem},
author={Christofides, Nicos},
year={1976},
institution={DTIC Document}}
@inproceedings{graprox,
title={Approximating graphic {TSP} by matchings},
author={M\"omke, T and Svensson, Ola},
booktitle={Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on},
pages={560--569},
year={2011},
organization={IEEE}
}
@article{correa,
title={{TSP} tours in cubic graphs: beyond 4/3},
author={Correa, Jos{\'e} and Larr{\'e}, Omar and Soto, Jos{\'e} A},
journal={SIAM Journal on Discrete Mathematics},
volume={29},
number={2},
pages={915--939},
year={2015},
publisher={SIAM}
}
@article{candluk,
title={Cubic {TSP} -- a 1.3-approximation},
author={Candr{\'a}kov{\'a}, Barbora and Lukot{\hskip -0.3ex}'ka, Robert},
journal={arXiv},
volume={1506.06369},
year={2015}
}
@article{karpra,
title={A 9/7-approximation algorithm for graphic {TSP} in cubic bipartite graphs},
author={Karp, Jeremy and Ravi, R},
journal={arXiv},
volume={1311.3640},
year={2013}
}
@article{cor01,
title={A 4/3-approximation for {TSP} on cubic 3-edge-connected graphs},
author={Aggarwal, N. and Garg, N. and Gupta, S.},
journal={arXiv},
volume={1101.5586},
year={2011}
}
@article{zuylen,
title={Improved Approximations for Cubic and Cubic Bipartite {TSP}},
author={van Zuylen, Anke},
journal={arXiv},
volume={1507.07121},
year={2015}
}
@article{boyd,
title={The traveling salesman problem on cubic and subcubic graphs},
author={Boyd, Sylvia and Sitters, Ren{\'e} and van der Ster, Suzanne and Stougie, Leen},
journal={Mathematical Programming},
volume={144},
number={1-2},
pages={227--245},
year={2014},
publisher={Springer}
}
@article{liusmall,
author = {Chun{-}Hung Liu and Sang{-}il Oum},
title = {Partitioning H-minor free graphs into three subgraphs with no large components},
journal = {Electronic Notes in Discrete Mathematics},
volume = {49},
pages = {133--138},
year = {2015}
}
@article{alon2003partitioning,
title={Partitioning into graphs with only small components},
author={Alon, Noga and Ding, Guoli and Oporowski, Bogdan and Vertigan, Dirk},
journal={Journal of Combinatorial Theory, Series B},
volume={87},
number={2},
pages={231--243},
year={2003}
}
@article{cowen1997defective,
title={Defective coloring revisited},
author={Cowen, Lenore and Goddard, Wayne and Jesurum, C Esther},
journal={Journal of Graph Theory},
volume={24},
number={3},
pages={205--219},
year={1997}
}
@article{edwards2014relative,
title={A relative of Hadwiger's conjecture},
author={Edwards, Katherine and Kang, Dong Yeap and Kim, Jaehoon and Oum, Sang-il and Seymour, Paul},
journal = {{SIAM} J. Discrete Math.},
volume = 29,
pages = {2385--2388},
year = 2015
}
@article{ding2000surfaces,
title={Surfaces, tree-width, clique-minors, and partitions},
author={Ding, Guoli and Oporowski, Bogdan and Sanders, Daniel P and Vertigan, Dirk},
journal={Journal of Combinatorial Theory, Series B},
volume={79},
number={2},
pages={221--246},
year={2000},
publisher={Elsevier}
}
@book{grotschel2012geometric,
title={Geometric algorithms and combinatorial optimization},
author={Gr{\"o}tschel, Martin and Lov{\'a}sz, L{\'a}szl{\'o} and Schrijver, Alexander},
volume={2},
year={2012},
publisher={Springer Science \& Business Media}
}
@article{padberg1982odd,
title={Odd minimum cut-sets and b-matchings},
author={Padberg, Manfred W and Rao, M Ram},
journal={Mathematics of Operations Research},
volume={7},
number={1},
pages={67--80},
year={1982}
}
@article{edmonds1965maximum,
title={Maximum matching and a polyhedron with 0, l-vertices},
author={Edmonds, Jack},
journal={J. Res. Nat. Bur. Standards B},
volume={69},
number={1965},
pages={125--130},
year={1965}
}
@article{Postle2015,
title = {Five-list-coloring graphs on surfaces {II}. {A} linear bound for critical graphs in a disk},
author = "Luke Postle and Robin Thomas",
journal = "Journal of Combinatorial Theory, Series B",
volume = "",
number = "",
year = "2015",
note = "In press"
}
@article{ramsey,
author = {Ramsey, F. P.},
year = 1930,
title = {On a problem of formal logic},
journal = {Proceedings of the London Mathematical Society},
volume = 30,
pages = {264--286}
}
@article{akomsem,
title = "A note on {R}amsey numbers",
journal = "Journal of Combinatorial Theory, Series A ",
volume = 29,
number = 3,
pages = "354--360",
year = 1980,
author = "Mikl{\'o}s Ajtai and J{\'a}nos Koml{\'o}s and Endre Szemer{\'e}di"
}
@Article{bohkee,
author="Bohman, Tom and Keevash, Peter",
title="The early evolution of the {H}-free process",
journal="Inventiones mathematicae",
year=2010,
volume=181,
number=2,
pages="291--336"
}
@article {conlon,
author = {Conlon, David},
title = {A new upper bound for diagonal {R}amsey numbers},
journal = {Ann. of Math. (2)},
volume = 170,
year = 2009,
number = 2,
pages = {941--960}
}
@article {erd47,
author = {Erd{\"o}s, P.},
title = {Some remarks on the theory of graphs},
journal = {Bull. Amer. Math. Soc.},
volume = 53,
year = 1947,
pages = {292--294}
}
@article{ersek,
title={A combinatorial problem in geometry},
author={Erd{\"o}s, Paul and Szekeres, George},
journal={Compositio Mathematica},
volume={2},
pages={463--470},
year={1935}
}
@article{spencer,
title = "Ramsey's theorem -- {A} new lower bound",
journal = "Journal of Combinatorial Theory, Series A ",
volume = 18,
number = 1,
pages = "108--115",
year = 1975,
author = "Joel Spencer"
}
@article {erhaj,
author = {Erd{\H{o}}s, P. and Hajnal, A.},
title = {Ramsey-type theorems},
note = {Combinatorics and complexity (Chicago, IL, 1987)},
journal = {Discrete Appl. Math.},
volume = 25,
year = 1989,
number = {1--2},
pages = {37--52}
}
@article {nogpach,
AUTHOR = {Alon, Noga and Pach, J{\'a}nos and Solymosi, J{\'o}zsef},
TITLE = {Ramsey-type theorems with forbidden subgraphs},
NOTE = {Paul Erd{\H{o}}s and his mathematics (Budapest, 1999)},
JOURNAL = {Combinatorica},
VOLUME = {21},
YEAR = {2001},
NUMBER = {2},
PAGES = {155--170}
}
@article {chudsur,
AUTHOR = {Chudnovsky, Maria},
TITLE = {The {E}rd\"os-{H}ajnal conjecture---a survey},
JOURNAL = {J. Graph Theory},
FJOURNAL = {Journal of Graph Theory},
VOLUME = {75},
YEAR = {2014},
NUMBER = {2},
PAGES = {178--190}
}
@article{bull,
title = "The {E}rd{\H{o}}s-{H}ajnal conjecture for bull-free graphs ",
journal = "Journal of Combinatorial Theory, Series B ",
volume = "98",
number = "6",
pages = "1301--1310",
year = 2008,
author = "Maria Chudnovsky and Shmuel Safra"
}
@article{gyarfas1987,
title={Problems from the world surrounding perfect graphs},
author={Gy{\'a}rf{\'a}s, Andr{\'a}s},
journal={Applicationes Mathematicae},
volume={19},
number={3-4},
pages={413--441},
year={1987},
publisher={Institute of Mathematics Polish Academy of Sciences}
}
@article{rankdec,
author={Dvo{\v{r}}{\'a}k, Zden{\v{e}}k and Kr{\'a}l, Daniel},
title = "Classes of graphs with small rank decompositions are {$\chi$}-bounded",
journal = "European Journal of Combinatorics",
volume = 33,
year = 2012,
pages = {679--683}
}
@article{chudcon,
title = "Substitution and {$\chi$}-boundedness",
journal = "Journal of Combinatorial Theory, Series B ",
volume = "103",
number = "5",
pages = "567--586",
year = "2013",
author = "Maria Chudnovsky and Irena Penev and Alex Scott and Nicolas Trotignon"
}
@article {scott,
author = {Scott, A. D.},
title = {Induced trees in graphs of large chromatic number},
journal = {Journal of Graph Theory},
volume = {24},
number = {4},
publisher = {Wiley Subscription Services, Inc., A Wiley Company},
pages = {297--311},
year = {1997}
}
@article{pawlik2014triangle,
title={Triangle-free intersection graphs of line segments with large chromatic number},
author={Pawlik, Arkadiusz and Kozik, Jakub and Krawczyk, Tomasz and Laso{\'n}, Micha{\l} and Micek, Piotr and Trotter, William T. and Walczak, Bartosz},
journal={Journal of Combinatorial Theory, Series B},
volume={105},
pages={6--10},
year={2014}
}
@article{oddholes,
title = "Induced subgraphs of graphs with large chromatic number. {I}. {O}dd holes",
journal = "Journal of Combinatorial Theory, Series B",
volume = "",
number = "",
pages = "",
year = 2015,
note = "In Press",
author = "Alex Scott and Paul Seymour",
}
@unpublished{chudnovsky2015induced,
title={Induced subgraphs of graphs with large chromatic number. {III}. {L}ong holes},
author={Chudnovsky, Maria and Scott, Alex and Seymour, Paul},
year={2015},
note="Manuscript"
}
@article{scott2015induced,
title={Induced subgraphs of graphs with large chromatic number. {IV}. {C}onsecutive holes},
author={Scott, Alex and Seymour, Paul},
journal={arXiv},
volume={1509.06563},
year=2015
}
@article {girthchrom,
AUTHOR = {R{\"o}dl, V.},
TITLE = {On the chromatic number of subgraphs of a given graph},
JOURNAL = {Proc. Amer. Math. Soc.},
VOLUME = {64},
YEAR = {1977},
NUMBER = {2},
PAGES = {370--371}
}
@article{kuhn2004every,
title={Every graph of sufficiently large average degree contains a {$C_4$}-free subgraph of large average degree},
author={K{\"u}hn, Daniela and Osthus, Deryk},
journal={Combinatorica},
volume={24},
number={1},
pages={155--162},
year={2004},
publisher={Springer}
}
@article {alondeg,
author = {Alon, Noga},
title = {Degrees and choice numbers},
journal = {Random Structures \& Algorithms},
volume = {16},
number = {4},
publisher = {John Wiley \& Sons, Inc.},
pages = {364--368},
year = {2000}
}
@article{dinzhu,
title = "A bound for the game chromatic number of graphs",
journal = "Discrete Mathematics",
volume = "196",
number = "1-3",
pages = "109--115",
year = "1999",
author = "Thomas Dinski and Xuding Zhu"
}
@inproceedings{khot2001improved,
title={Improved inapproximability results for {MaxClique}, chromatic number and approximate graph coloring},
author={Khot, Subhash},
booktitle={Foundations of Computer Science, 2001. Proceedings. 42nd IEEE Symposium on},
pages={600--609},
year={2001},
organization={IEEE}
}
@TechReport{BodlaenderEtAl2008,
author = {Bodlaender, Hans L. and Demaine, Erik and Fellows, Michael R. and Guo, Jiong and Hermelin, Danny and Lokshtanov, Daniel and M{\"u}ller, Moritz and Raman, Venkatesh and van Rooij, Johan and Rosamond, Frances A.},
title = {Open Problems in Parameterized and Exact Computation},
institution = {Utrecht University},
year = {2008},
number = {UU-CS-2008-017},
}
@article{indsettight,
author = {Dvo{\v{r}}{\'a}k, Zden{\v{e}}k and Masa{\v{r}}{\'\i}k, Tom{\'a}{\v{s}} and Mus{\'\i}lek, Jan and Pangr{\'a}c, Ond{\v{r}}ej},
title = {Triangle-free planar graphs with smallest independence number},
year = 2016,
journal={ArXiv},
volume={1606.06265}
}
@article{Sta79,
author = {W. Staton},
title = {Some {R}amsey-type numbers and the independence ratio},
journal = {Trans. Amer. Math. Soc.},
volume = 256,
year = 1979,
pages = "353--370"
}
@article{Jon90,
author = {Jones, K. F.},
title = {Size and independence in triangle-free graphs with maximum degree three},
journal = {J. Graph Theory},
volume = 14,
year = 1990,
pages = "525--535"
}
@article{franklwilson,
title={Intersection theorems with geometric consequences},
author={Frankl, Peter and Wilson, Richard M.},
journal={Combinatorica},
volume={1},
number={4},
pages={357--368},
year={1981}
}
@article{extgsum,
title = "Extending the {G}y{\'a}rf{\'a}s-{S}umner conjecture",
journal = "Journal of Combinatorial Theory, Series B",
volume = "105",
pages = "11--16",
year = "2014",
author = "Maria Chudnovsky and Paul Seymour"
}
@article{alon1992colorings,
title={Colorings and orientations of graphs},
author={Alon, Noga and Tarsi, Michael},
journal={Combinatorica},
volume={12},
number={2},
pages={125--134},
year={1992}
}
@article{kinglupeng,
title={A fractional analogue of {B}rooks' theorem},
author={King, Andrew D and Lu, Linyuan and Peng, Xing},
journal={SIAM Journal on Discrete Mathematics},
volume={26},
number={2},
pages={452--471},
year={2012}
}
@article{gacrE1,
author = {Foucaud, F. and Naserasr, R.},
title = {The Complexity of Homomorphisms of Signed Graphs and Signed Constraint Satisfaction},
journal = {Lecture Notes in Computer Science},
volume = 8392,
year = 2014,
pages = "526--537"
}
@article{gacrE11,
author={Kang, Y. and Steffen, E.},
title = {Circular coloring of signed graphs},
journal={arXiv},
volume={1509.04488},
year=2015
}
@article{gacrE12,
author={M{\'a}{\v{c}}ajov{\'a}, E. and Raspaud, A. and {\v{S}}koviera, M.},
title={The chromatic number of a signed graph},
journal={arXiv},
volume={1412.6349},
year=2016
}
@article{cor13,
author={Lampis, M.},
title={Improved inapproximability for {TSP}},
journal = {Lecture Notes in Computer Science},
volume={7408},
year = 2013,
pages = "243--253"
}
@article{KLS13,
author={Karpinski, M. and Lampis, M. and Schmied, R.},
title={New inapproximability bounds for {TSP}},
journal={Journal of Computer and System Sciences},
volume=81,
year=2015,
pages="1665--1677"
}
@article{cor08,
author={Gamarnik, D. and Lewenstein, M. and Sviridenko, M.},
title={An improved upper bound for the {TSP} in cubic 3-edge-connected graph},
journal={Operations Research Letters},
volume={33},
year= 2005,
pages="467--474"
}
@article{cor15,
author={Mucha, M.},
title={13/9-approximation for graphic {TSP}},
journal={Theory of Computing Systems},
volume={55},
year= 2014,
pages="640--657"
}
@inproceedings{cor16,
author={Oveis Gharan, S. and Saberi, A. and Singh, M.},
title={A Randomized Rounding Approach to the Traveling Salesman Problem},
booktitle={Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on},
pages={550--559},
year={2011},
organization={IEEE}
}
@article{cor21,
author={Seb\"o, A. and Vygen, J.},
title={Shorter tours by nicer ears: 7/5-Approximation for the graph-{TSP}, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs},
journal={Combinatorica},
volume={34},
year= 2014,
pages="597--629"
}
@article{KS13,
author={Karpinski, M. and Schmied, R.},
title={Approximation hardness of graphic {TSP} on cubic graphs},
journal={RAIRO Operations Research},
volume=49,
year=2015,
pages="651--668"
}
@article{gacrE2,
author={Naserasr, R. and Rollov{\'a}, E. and Sopena, E.},
title={Homomorphisms of planar signed graphs to signed projective cubes},
journal={Discrete Mathematics and Theoretical Computer Science},
volume=15,
year=2013,
pages="1--12"
}
@article{gacrE3,
author={Naserasr, R. and Rollov{\'a}, E. and Sopena, E.},
title={Homomorphisms of Signed Graphs},
journal={Journal of Graph Theory},
volume=79,
year=2015,
pages="178--212"
}
@article{gacrE4,
author={Ochem, P. and Pinlou, A. and Sen, S.},
title={Homomorphisms of signed planar graphs},
journal={arXiv},
volume={1401.3308},
year=2014
}
@article{gacrE5,
author={Zaslavsky, T.},
title={Signed graph coloring},
journal={Discrete Math.},
volume=39,
year=1982,
pages="215--228"
}
@article{Arch,
author={Archdeacon, D. and Hutchinson, J. and Nakamoto, A. and Negami, S. and Ota, K.},
title={Chromatic numbers of quadrangulations on closed surfaces},
journal={J. Graph Theory},
volume=37,
year=2001,
pages="100--114"
}
@incollection{Erd,
author={Erd\H{o}s, P.},
title={Problems and results in combinatorial analysis and graph theory},
booktitle={Proof techniques in Graph Theory},
editor={F. Harary},
publisher={Academic Press},
year=1969
}
@article{KS,
author={Kaiser, T. and Stehl{\'{\i}}k, M.},
title={Colouring quadrangulations of projective spaces},
journal={J. Combin. Theory Ser. B},
volume=113,
year=2015,
pages="1--17"
}
@article{apex,
title={List-coloring apex-minor-free graphs},
author={Dvo{\v{r}}{\'a}k, Zden{\v{e}}k and Thomas, Robin},
journal={arXiv},
volume={1401.1399},
year={2014}
}
@article{FellowsEtAl2012,
author = {Michael R. Fellows and Jiong Guo and D{\'a}niel Marx and Saket Saurabh},
title = {{Data Reduction and Problem Kernels (Dagstuhl Seminar 12241)}},
pages = {26--50},
journal = {Dagstuhl Reports},
year = {2012},
volume = {2},
number = {6},
editor = {Michael R. Fellows and Jiong Guo and D{\'a}niel Marx and Saket Saurabh}
}
@book {Niedermeier2006,
AUTHOR = {Niedermeier, Rolf},
TITLE = {Invitation to fixed-parameter algorithms},
SERIES = {Oxford Lecture Series in Mathematics and its Applications},
VOLUME = {31},
PUBLISHER = {Oxford University Press},
ADDRESS = {Oxford},
YEAR = {2006},
PAGES = {xii+300}
}
@inproceedings{borodin1977criterion,
title={Criterion of chromaticity of a degree prescription},
author={Borodin, Oleg V},
booktitle={IV All-Union Conf. on Theoretical Cybernetics (Novosibirsk)},
pages={127--128},
year={1977}
}
@inproceedings{brooks1941colouring,
title={On colouring the nodes of a network},
author={Brooks, Rowland Leonard},
booktitle={Mathematical Proceedings of the Cambridge Philosophical Society},
volume={37},
pages={194--197},
year={1941},
organization={Cambridge Univ Press}
}
@article{fajtlowicz1978size,
title={On the size of independent sets in graphs},
author={Fajtlowicz, Simeon},
journal={Congr. Numer},
volume={21},
pages={269--274},
year={1978}
}
@article{kinged,
author = {Katherine Edwards and Andrew D. King},
title = {Bounding the Fractional Chromatic Number of {$K_\Delta$}-Free Graphs},
journal = {{SIAM} J. Discrete Math.},
volume = {27},
number = {2},
pages = {1184--1208},
year = {2013}
}
@book{downey2012parameterized,
title={Parameterized complexity},
author={Downey, Rodney G and Fellows, Michael Ralph},
year={2012},
publisher={Springer Science \& Business Media}
}
@book{cygan2015parameterized,
title={Parameterized Algorithms},
author={Cygan, Marek and Fomin, Fedor V and Kowalik, {\L}ukasz and Lokshtanov, Daniel and Marx, D{\'a}niel and Pilipczuk, Marcin and Pilipczuk, Micha{\l} and Saurabh, Saket},
volume={4},
year={2015},
publisher={Springer}
}
@incollection{mnich2016large,
title={Large Independent Sets in Subquartic Planar Graphs},
author={Mnich, Matthias},
booktitle={WALCOM: Algorithms and Computation},
pages={209--221},
year={2016},
publisher={Springer}
}
@article{CohenAddad2016,
title = {Steinberg's Conjecture is false},
journal = {Journal of Combinatorial Theory, Series B},
volume = 122,
year = 2017,
author = {Vincent Cohen-Addad and Michael Hebdige and Daniel Kr{\'a}l' and Zhentao Li and Esteban Salgado},
pages = {452--456}
}
@article{corr1,
author = {Anton Bernshteyn},
title = {The asymptotic behavior of the correspondence chromatic number},
journal = {Discrete Mathematics},
volume = {339},
number = {11},
pages = {2680--2692},
year = {2016}
}
@unpublished{corrprob,
author = {Marthe Bonamy and Thomas Perrett and Luke Postle},
title = {Colouring Graphs with Sparse Neighbourhoods: {B}ounds and Applications},
year = 2016,
note = "Manuscript"
}
@Article{Demaine2008,
author="Demaine, Erik D. and Hajiaghayi, MohammadTaghi",
title="Linearity of grid minors in treewidth with applications through bidimensionality",
journal="Combinatorica",
year="2008",
volume="28",
number="1",
pages="19--36",
}
@article{rs1,
title = "Graph minors. {I}. {E}xcluding a forest",
journal = "Journal of Combinatorial Theory, Series B",
volume = 35,
pages = "39--61",
year = 1983,
author = "Neil Robertson and P.D. Seymour"
}
@article{homclebsch,
title = "Homomorphisms and edge-colourings of planar graphs",
journal = "Journal of Combinatorial Theory, Series B",
volume = 97,
number = 3,
pages = "394--400",
year = 2007,
author = "Reza Naserasr"
}
@article{kanjzhang,
title = "On the independence number of graphs with maximum degree 3",
journal = "Theoretical Computer Science",
volume = 478,
pages = "51--75",
year = 2013,
author = "Iyad Kanj and Fenghui Zhang"
}
@article{hutcheuler,
title = "Colouring {E}ulerian Triangulations",
journal = "Journal of Combinatorial Theory, Series B",
volume = 84,
pages = "225--239",
year = 2002,
author = "Joan Hutchinson and R.Bruce Richter and Paul Seymour"
}
@article{nakaeuler,
title = "5-Chromatic even triangulations on surfaces",
journal = "Discrete Mathematics",
volume = 308,
number = 12,
pages = "2571--2580",
year = 2008,
author = "Atsuhiro Nakamoto"
}
@article{RSTtutte,
title = "Tutte's Edge-Colouring Conjecture",
journal = "Journal of Combinatorial Theory, Series B",
volume = 70,
pages = "166--183",
year = 1997,
author = "Neil Robertson and Paul Seymour and Robin Thomas"
}
@article{doublecross,
author = {Katherine Edwards and Daniel P. Sanders and Paul D. Seymour and Robin Thomas},
title = {Three-edge-colouring doublecross cubic graphs},
journal = {J. Comb. Theory, Ser. {B}},
volume = 119,
pages = {66--95},
year = 2016
}
@unpublished{cubapex,
author = {Daniel Sanders and Robin Thomas},
title = {Edge three-coloring cubic apex graphs},
note = {In preparation}
}
@incollection{grun,
booktitle={Recent progress in combinatorics: proceedings},
editor={Tutte, William Thomas},
volume=1968,
year=1969,
publisher={Academic Press},
author={B. Gr{\"u}nbaum},
title={Conjecture 6},
pages={343}
}
@article{kochdis,
author={M. Kochol},
title={Polyhedral embeddings of snarks in orientable surfaces},
journal={Proc. Amer. Math. Soc.},
volume=137,
year=2009,
pages="1613--1619"
}
@article{ltwz,
author = {L{\'a}szl{\'o} Mikl{\'o}s Lov{\'a}sz and Carsten Thomassen and Yezhou Wu and Cun{-}Quan Zhang},
title = {Nowhere-zero 3-flows and modulo $k$-orientations},
journal = {J. Comb. Theory, Ser. {B}},
volume = 103,
pages = {587--598},
year = 2013
}
@article{fabrici2007structure,
title={The structure of 1-planar graphs},
author={Fabrici, Igor and Madaras, Tom{\'a}{\v{s}}},
journal={Discrete Mathematics},
volume={307},
number={7},
pages={854--865},
year={2007}
}
@article{gale1979game,
title={The game of {H}ex and the {B}rouwer fixed-point theorem},
author={Gale, David},
journal={The American Mathematical Monthly},
volume={86},
number={10},
pages={818--827},
year={1979},
publisher={JSTOR}
}
@article{feige,
title={Improved approximation algorithms for minimum weight vertex separators},
author={Feige, Uriel and Hajiaghayi, MohammadTaghi and Lee, James R},
journal={SIAM Journal on Computing},
volume=38,
number=2,
pages={629--657},
year=2008
}
@article{layers,
title={Layered separators in minor-closed families with applications},
author={Dujmovi{\'c}, Vida and Morin, Pat and Wood, David R},
journal={Journal of Combinatorial Theory, Series B},
volume=127,
year=2017,
pages={111--147}
}
@article{dvorak2016strongly,
title={Strongly sublinear separators and polynomial expansion},
author={Dvo{\v{r}}{\'a}k, Z. and Norin, Sergey},
journal={SIAM Journal on Discrete Mathematics},
volume=30,
pages={1095--1101},
year=2016
}
@inproceedings{dawar2006approximation,
title={Approximation schemes for first-order definable optimisation problems},
author={Dawar, Anuj and Grohe, Martin and Kreutzer, Stephan and Schweikardt, Nicole},
booktitle={21st Annual IEEE Symposium on Logic in Computer Science (LICS'06)},
pages={411--420},
year={2006},
organization={IEEE}
}
@inproceedings{demaine2005algorithmic,
title={Algorithmic graph minor theory: {D}ecomposition, approximation, and coloring},
author={Demaine, Erik D. and Hajiaghayi, MohammadTaghi and Kawarabayashi, Ken-ichi},
booktitle={46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05)},
pages={637--646},
year={2005},
organization={IEEE}
}
@article{grohe2003local,
title={Local tree-width, excluded minors, and approximation algorithms},
author={Grohe, Martin},
journal={Combinatorica},
volume={23},
number={4},
pages={613--632},
year={2003},
publisher={Springer}
}
@inproceedings{demaine2005bidimensionality,
title={Bidimensionality: new connections between {FPT} algorithms and {PTAS}s},
author={Demaine, Erik D. and Hajiaghayi, MohammadTaghi},
booktitle={Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms},
pages={590--601},
year={2005},
organization={Society for Industrial and Applied Mathematics}
}
@inproceedings{fomin2011bidimensionality,
title={Bidimensionality and {EPTAS}},
author={Fomin, Fedor V and Lokshtanov, Daniel and Raman, Venkatesh and Saurabh, Saket},
booktitle={Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms},
pages={748--759},
year={2011},
organization={SIAM}
}
@inproceedings{demaine2004equivalence,
title={Equivalence of local treewidth and linear local treewidth and its algorithmic applications},
author={Demaine, Erik D. and Hajiaghayi, MohammadTaghi},
booktitle={Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms},
pages={840--849},
year={2004},
organization={Society for Industrial and Applied Mathematics}
}
@article{hunt1998nc,
title={{NC}-approximation schemes for {NP}- and {PSPACE}-hard problems for geometric graphs},
author={Hunt, Harry B and Marathe, Madhav V and Radhakrishnan, Venkatesh and Ravi, Shankar S and Rosenkrantz, Daniel J and Stearns, Richard E},
journal={Journal of Algorithms},
volume={26},
number={2},
pages={238--274},
year={1998},
publisher={Elsevier}
}
@article{grigoriev2007algorithms,
title={Algorithms for graphs embeddable with few crossings per edge},
author={Grigoriev, Alexander and Bodlaender, Hans L},
journal={Algorithmica},
volume={49},
number={1},
pages={1--11},
year={2007},
publisher={Springer}
}
@incollection{har2015approximation,
title={Approximation algorithms for polynomial-expansion and low-density graphs},
author={Har-Peled, Sariel and Quanrud, Kent},
booktitle={Algorithms-ESA 2015},
pages={717--728},
year={2015},
publisher={Springer}
}
@article{har2015approximationjrnl,
title={Approximation algorithms for polynomial-expansion and low-density graphs},
author={Har-Peled, Sariel and Quanrud, Kent},
journal={SIAM Journal on Computing},
volume=46,
number=6,
pages={1712--1744},
year=2017
}
@article{cabello2015simple,
title={Simple {PTAS}'s for families of graphs excluding a minor},
author={Cabello, Sergio and Gajser, David},
journal={Discrete Applied Mathematics},
volume={189},
pages={41--48},
year={2015},
publisher={Elsevier}
}
@inproceedings{grohe2014deciding,
title={Deciding first-order properties of nowhere dense graphs},
author={Grohe, Martin and Kreutzer, Stephan and Siebertz, Sebastian},
booktitle={Proceedings of the 46th Annual ACM Symposium on Theory of Computing},
pages={89--98},
year={2014},
organization={ACM}
}
@article{grohe2014decidingjrnl,
title={Deciding first-order properties of nowhere dense graphs},
author={Grohe, Martin and Kreutzer, Stephan and Siebertz, Sebastian},
journal={Journal of the ACM},
volume=64,
number=3,
year=2017,
pages={17}
}
@inproceedings{nonapdom,
author = {Dinur, Irit and Steurer, David},
title = {Analytical Approach to Parallel Repetition},
booktitle = {Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing},
series = {STOC '14},
year = 2014,
pages = {624--633},
publisher = {ACM},
address = {New York, NY, USA}
}
@inproceedings{papadimitriou1988optimization,
title={Optimization, approximation, and complexity classes},
author={Papadimitriou, Christos and Yannakakis, Mihalis},
booktitle={Proceedings of the twentieth annual ACM symposium on Theory of computing},
pages={229--234},
year={1988},
organization={ACM}
}
@article{albertson1979three,
title={The three excluded cases of {D}irac's map-color theorem},
author={Albertson, Michael and Hutchinson, Joan},
journal={Annals of the New York Academy of Sciences},
volume=319,
pages={7--17},
year=1979
}
@article{thomas2008coloring,
title={Coloring even-faced graphs in the torus and the {K}lein bottle},
author={Daniel Kr{\'a}l' and Robin Thomas},
journal={Combinatorica},
volume=28,
pages={325--341},
year=2008
}
@article{bodlaender1998,
title = "A partial $k$-arboretum of graphs with bounded treewidth",
journal = "Theoretical Computer Science",
volume = 209,
number = 1,
pages = "1--45",
year = 1998,
author = "Hans L. Bodlaender"
}
@article{kuhndens,
author={Daniela K{\"u}hn and Deryk Osthus},
title={Induced Subdivisions In {$K_{s,s}$}-Free Graphs of Large Average Degree},
journal={Combinatorica},
volume=24,
pages = "287--304",
year=2004
}
@article{johansson1996asymptotic,
title={Asymptotic choice number for triangle free graphs},
author={Johansson, Anders},
year={1996},
journal={DIMACS Technical Report},
volume={91-4, 1196}
}
@article{triadegen,
author = {Noga Alon and Michael Krivelevich and Benny Sudakov},
title = {Coloring Graphs with Sparse Neighborhoods},
journal = {J. Comb. Theory, Ser. {B}},
volume = 77,
pages = {73--82},
year = 1999
}
@article{kim1995ramsey,
title={The {R}amsey number {$R(3, t)$} has order of magnitude $t^2/\log t$},
author={Kim, Jeong Han},
journal={Random Structures \& Algorithms},
volume={7},
number={3},
pages={173--207},
year={1995},
publisher={Wiley Online Library}
}
@book{molloy2013graph,
title={Graph colouring and the probabilistic method},
author={Molloy, Michael and Reed, Bruce},
volume={23},
year={2013},
publisher={Springer Science \& Business Media}
}
@article{gyarfas1988line,
title={On-line and first fit colorings of graphs},
author={Gy{\'a}rf{\'a}s, Andr{\'a}s and Lehel, Jen{\"o}},
journal={Journal of Graph theory},
volume=12,
number=2,
pages={217--227},
year=1988
}
@article{colnonap,
author={Zuckerman, David},
year=2007,
title={Linear degree extractors and the inapproximability of {M}ax {C}lique and {C}hromatic {N}umber},
journal={Theory of Computing},
volume=3,
pages={103--128}
}
@inproceedings{decihad,
author = {Ken{-}ichi Kawarabayashi and Bruce A. Reed},
title = {Hadwiger's conjecture is decidable},
booktitle = {Proceedings of the 41st Annual {ACM} Symposium on Theory of Computing,
{STOC} 2009, Bethesda, MD, USA, May 31 - June 2, 2009},
pages = {445--454},
year = 2009,
publisher = {{ACM}}
}
@inproceedings{kawarabayashi2009additive,
title={Additive approximation algorithms for list-coloring minor-closed class of graphs},
author={Kawarabayashi, Ken-ichi and Demaine, Erik D. and Hajiaghayi, MohammadTaghi},
booktitle={Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms},
pages={1166--1175},
year=2009,
organization={SIAM}
}
@article{demaine2009approximation,
title={Approximation algorithms via structural results for apex-minor-free graphs},
author={Demaine, Erik D. and Hajiaghayi, MohammadTaghi and Kawarabayashi, Ken-ichi},
journal={Automata, Languages and Programming},
pages={316--327},
year={2009},
publisher={Springer}
}
@article{coltweasy,
author={Arnborg, Stefan and Proskurowski, Andrzej},
year=1989,
title={Linear time algorithms for {NP}-hard problems restricted to partial {$k$}-trees},
journal={Discrete Applied Mathematics},
volume=23,
pages={11--24}
}
@article{blades,
title={Solution to advanced problem no. 4526},
author={Descartes, Blanche},
journal={Amer. Math. Monthly},
volume=61,
pages={532},
year=1954
}
@article{konedes,
title={Properties of {D}escartes' construction of triangle-free graphs with high chromatic number},
author={Kostochka, Alexandr and Ne{\v{s}}et{\v{r}}il, Jaroslav},
journal={Combinatorics, Probability and Computing},
volume=8,
number=5,
pages={467--472},
year=1999
}
@article{zykov,
author={A. Zykov},
title={On some properties of linear complexes},
journal={Mat. Sb. (NS)},
volume=24,
number=66,
year=1949,
pages={163--188}
}
@misc{robinconj,
author={Robin Thomas},
note = {Conference Graph Theory 2008 at Sandbjerg Manor; slides at \url{http://people.math.gatech.edu/~thomas/SLIDE/beyondgrot.pdf}.}
}
@article{espsublin,
title={Polynomial expansion and sublinear separators},
author={Esperet, Louis and Raymond, Jean-Florent},
journal={European Journal of Combinatorics},
volume=69,
pages={49--53},
year=2018
}
@article{marx2013everything,
title={Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask)},
author={Marx, D{\'a}niel and Pilipczuk, Micha{\l}},
journal = {ArXiv},
volume={1307.2187},
year={2013}
}
@inproceedings{feige2006finding,
title={Finding small balanced separators},
author={Feige, Uriel and Mahdian, Mohammad},
booktitle={Proceedings of the thirty-eighth annual ACM symposium on Theory of computing},
pages={375--384},
year=2006,
organization={ACM}
}
@article{betsep,
title = {Reduced Constants for Simple Cycle Graph Separation},
author = {Djidjev, H. and Venkatesan, S.},
journal = {Acta Informatica},
year = 1997,
volume = 34,
pages = "231--243"
}
@inproceedings{Parekh2015,
author={Parekh, Ojas and Pritchard, David},
editor={Bampis, Evripidis and Svensson, Ola},
title={Generalized Hypergraph Matching via Iterated Packing and Local Ratio},
bookTitle={Approximation and Online Algorithms: 12th International Workshop, WAOA 2014, Wroc{\l}aw, Poland, September 11-12, 2014, Revised Selected Papers},
year=2015,
publisher={Springer International Publishing},
pages="207--223"
}
@article{BANSAL201721,
title = {Tight approximation bounds for dominating set on graphs of bounded arboricity},
journal = {Information Processing Letters},
volume = 122,
pages = "21--24",
year = 2017,
author = {Nikhil Bansal and Seeun William Umboh}
}
@article{apxdomin,
title = {Constant-factor approximation of domination number in sparse graphs},
author={Z. Dvo{\v{r}}{\'a}k},
journal = {European Journal of Combinatorics},
volume = 34,
year = 2013,
pages = "833--840"
}
@article{haastad1999clique,
title={Clique is hard to approximate within $n^{1-\varepsilon}$},
author={H{\aa}stad, Johan},
journal={Acta Mathematica},
volume=182,
pages="105--142",
year=1999
}
@article{amiri2017distributed,
title={Distributed domination on graph classes of bounded expansion},
author={Amiri, Saeed Akhoondian and {Ossona de Mendez}, Patrice and Rabinovich, Roman and Siebertz, Sebastian},
journal={arXiv},
volume={1702.02848},
year=2017
}
@article{dvopek,
title={Irreducible 4-critical triangle-free toroidal graphs},
author={Dvo{\v{r}}{\'a}k, Zden{\v{e}}k and Pek{\'a}rek, Jakub},
journal={European Journal of Combinatorics},
pages="103112",
year=2020,
volume=88
}
@article{cylflow,
title={Coloring near-quadrangulations of the cylinder and the torus},
author={Dvo{\v{r}}{\'a}k, Zden{\v{e}}k and Pek{\'a}rek, Jakub},
journal={European Journal of Combinatorics},
volume=93,
year=2021,
pages="103258"}
@unpublished{dpfuture,
title={Characterization of $4$-critical triangle-free toroidal graphs},
author={Dvo{\v{r}}{\'a}k, Zden{\v{e}}k and Pek{\'a}rek, Jakub},
note={In preparation},
year=2018}
@article{postle3crit,
author = {Luke Postle},
title = {3-List Coloring Graphs of Girth at least Five on Surfaces},
journal = {arXiv},
volume = {1710.06898},
year = 2017}
@article{Jon84,
author= {K.F. Jones},
title={Independence in graphs with maximum degree four},
journal={J. Combin. Theory Ser. B},
volume=37,
year=1984,
pages={254--269}}
@article{listfraccyl,
author={Dvo{\v{r}}{\'a}k, Zden{\v{e}}k and Hu, Xiaolan},
title={$(3a:a)$-list-colorability of embedded graphs of girth at least five},
journal={ArXiv},
volume={1805.11507},
year=2018}
@article{kneser,
author={Lov{\'a}sz, L{\'a}szl{\'o}},
year=1978,
title={Kneser's conjecture, chromatic number, and homotopy},
journal={Journal of Combinatorial Theory, Series A},
volume=25,
pages={319--324}
}
@article{hallneq,
title={The fractional chromatic number, the Hall ratio, and the lexicographic product},
author={Johnson Jr, Peter D},
journal={Discrete Mathematics},
volume=309,
number=14,
pages={4746--4749},
year=2009,
}
@article{cropper2006hall,
title={Hall ratio of the Mycielski graphs},
author={Cropper, Mathew and Gy{\'a}rf{\'a}s, Andr{\'a}s and Lehel, Jen{\H{o}}},
journal={Discrete mathematics},
volume=306,
number=16,
pages={1988--1990},
year=2006
}
@article{PRS,
author={L. Pyber and V. R{\"o}dl and E. Szemer{\'e}di},
title={Dense graphs without 3-regular subgraphs},
journal={J. Combin. Theory, Ser. B},
volume=63,
year=1995,
pages={41--54}
}
@article{requests,
author={Dvo{\v{r}}{\'a}k, Zden{\v{e}}k and Norin, Sergey and Postle, Luke},
title={List coloring with requests},
journal = {Journal of Graph Theory},
volume = 92,
year = 2019,
pages = "191--206"
}
@unpublished{bcr1,
author={D. I. A. Cohen},
title={Block count consistency and the four color problem},
note={Manuscript}
}
@article{bcr2,
author={S. J. Gismondi and E. R. Swart},
title={A new type of 4-colour reducibility},
journal={Congressus Numerantium},
volume=82,
pages={33--48},
year=1991
}
@article{tait,
author={P. G. Tait},
title={Note on a theorem in geometry of position},
journal={Trans. Roy. Soc. Edinburgh},
volume=29,
year=1880,
pages={657--660}
}
@article{latin,
author = {Colbourn, Charles J.},
title = {The complexity of completing partial Latin squares},
journal = {Discrete Applied Mathematics},
volume = 8,
year = 1984,
pages = {25-30}
}
@article{fiala2003np,
title={{NP} completeness of the edge precoloring extension problem on bipartite graphs},
author={Fiala, Ji{\v{r}}{\'\i}},
journal={Journal of Graph Theory},
volume=43,
pages={156--160},
year=2003
}
@article{arnborg1989linear,
title={Linear time algorithms for {NP}-hard problems restricted to partial $k$-trees},
author={Arnborg, Stefan and Proskurowski, Andrzej},
journal={Discrete applied mathematics},
volume={23},
number={1},
pages={11--24},
year={1989}
}
@article{exp4trfree,
author = {Kelly, Tom and Postle, Luke},
title = {Exponentially many 4-list-colorings of triangle-free graphs on surfaces},
journal = {Journal of Graph Theory},
volume = 87,
pages = {230--238},
year=2018
}
@inproceedings{thin,
title={Thin graph classes and polynomial-time approximation schemes},
author={Dvo{\v{r}}{\'a}k, Zden{\v{e}}k},
booktitle={Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'18)},
pages={1685--1701},
year=2018,
organization={ACM}
}
@inproceedings{addnon,
author = {Zden\v{e}k Dvo\v{r}{\'{a}}k and
Ken{-}ichi Kawarabayashi},
title = {Additive Non-Approximability of Chromatic Number in Proper Minor-Closed
Classes},
booktitle = {45th International Colloquium on Automata, Languages, and Programming,
{ICALP} 2018},
pages = {47:1--47:12},
year = {2018},
series = {LIPIcs},
volume = 107,
publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik}
}
@inproceedings{dawar2007locally,
title={Locally excluding a minor},
author={Dawar, Anuj and Grohe, Martin and Kreutzer, Stephan},
booktitle={Logic in Computer Science, 2007. LICS 2007. 22nd Annual IEEE Symposium on},
pages={270--279},
year={2007},
organization={IEEE}
}
@inproceedings{kreutzer2010lower,
title={Lower bounds for the complexity of monadic second-order logic},
author={Kreutzer, Stephan and Tazari, Siamak},
booktitle={Logic in Computer Science (LICS), 2010 25th Annual IEEE Symposium on},
pages={189--198},
year={2010},
organization={IEEE}
}
@article{ponomarenko1988isomorphism,
title={Isomorphism problem for classes of graphs closed under contractions},
author={Ponomarenko, Ilia Nikolaevich},
journal={Zapiski Nauchnykh Seminarov POMI},
volume={174},
pages={147--177},
year={1988},
publisher={St. Petersburg Department of Steklov Institute of Mathematics}
}
@article{miller1997separators,
title={Separators for sphere-packings and nearest neighbor graphs},
author={Miller, Gary L and Teng, Shang-Hua and Thurston, William and Vavasis, Stephen A},
journal={Journal of the ACM (JACM)},
volume={44},
number={1},
pages={1--29},
year={1997}
}
@inproceedings{bakergame,
author = {Z. Dvo{\v{r}}{\'a}k},
title = {Baker Game and Polynomial-Time Approximation Schemes},
year = 2020,
publisher = {Society for Industrial and Applied Mathematics},
booktitle = {Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms},
pages = {2227--2240},
series = {SODA '20}
}
@article{linial1995geometry,
title={The geometry of graphs and some of its algorithmic applications},
author={Linial, Nathan and London, Eran and Rabinovich, Yuri},
journal={Combinatorica},
volume={15},
number={2},
pages={215--245},
year={1995}
}
@article{onsubsep,
title= {On classes of graphs with strongly sublinear separators},
author = {Z. Dvo{\v{r}}{\'a}k},
journal = {European Journal of Combinatorics},
volume=71,
year=2018,
pages={1-11}
}
@article{hoppen2018local,
title={Local algorithms, regular graphs of large girth, and random regular graphs},
author={Hoppen, Carlos and Wormald, Nicholas},
journal={Combinatorica},
volume={38},
number={3},
pages={619--664},
year={2018}
}
@inproceedings{befoin,
author = {Jakub Gajarsk{\'{y}} and
Stephan Kreutzer and
Jaroslav Ne\v{s}et\v{r}il and
Patrice Ossona de Mendez and
Michal Pilipczuk and
Sebastian Siebertz and
Szymon Toru{\'{n}}czyk},
title = {First-Order Interpretations of Bounded Expansion Classes},
booktitle = {45th International Colloquium on Automata, Languages, and Programming,
{ICALP} 2018},
pages = {126:1--126:14},
year = {2018}
}
@article{van2017generalised,
title={On the generalised colouring numbers of graphs that exclude a fixed minor},
author={van den Heuvel, Jan and de Mendez, Patrice Ossona and Quiroz, Daniel and Rabinovich, Roman and Siebertz, Sebastian},
journal={European Journal of Combinatorics},
volume={66},
pages={129--144},
year={2017},
publisher={Elsevier}
}
@incollection{gaifman1982local,
title={On local and non-local properties},
author={Gaifman, Haim},
booktitle={Studies in Logic and the Foundations of Mathematics},
volume={107},
pages={105--135},
year={1982},
publisher={Elsevier}
}
@article{seese1996linear,
title={Linear time computable problems and first-order descriptions},
author={Seese, Detlef},
journal={Mathematical Structures in Computer Science},
volume={6},
number={6},
pages={505--526},
year={1996},
publisher={Cambridge University Press}
}
@inproceedings{dawar2009domination,
title={Domination Problems in Nowhere-Dense Classes of Graphs},
author={Dawar, Anuj and Kreutzer, Stephan},
booktitle={Foundations of Software Technology and Theoretical Computer Science (FSTTCS)},
year={2009}
}
@article{kreutzer2018polynomial,
title={Polynomial kernels and wideness properties of nowhere dense graph classes},
author={Kreutzer, Stephan and Rabinovich, Roman and Siebertz, Sebastian},
journal={ACM Transactions on Algorithms (TALG)},
volume={15},
number={2},
pages={24},
year={2018},
publisher={ACM}
}
@inproceedings{eickmeyer2017neighborhood,
title={Neighborhood Complexity and Kernelization for Nowhere Dense Classes of Graphs},
author={Eickmeyer, Kord and Giannopoulou, Archontia C and Kreutzer, Stephan and Kwon, O and Pilipczuk, Michal and Rabinovich, Roman and Siebertz, Sebastian and others},
booktitle={LIPIcs-Leibniz International Proceedings in Informatics},
volume={80},
year={2017},
organization={Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik}
}
@inproceedings{numtypes,
author = {Pilipczuk, Micha\l and Siebertz, Sebastian and Toru\'{n}czyk, Szymon},
title = {On the Number of Types in Sparse Graphs},
booktitle = {Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science},
series = {LICS'18},
year = {2018},
pages = {799--808},
publisher = {ACM}
}
@article{rplgr,
author = {C. McDiarmid and A. Steger and D. Welsh},
title = {Random planar graphs},
journal={Journal of Combinatorial Theory, Series A},
volume = 93,
pages = {187--206},
year = 2015
}
@article{luks,
author = {E. Luks},
title = {Isomorphism of Graphs of Bounded Valence can be Tested in Polynomial Time},
journal = {J. Comput. Syst. Sci.},
volume=25,
pages={42--65},
year=1982
}
@book{grohe2017descriptive,
title={Descriptive complexity, canonisation, and definable graph structure theory},
author={Grohe, Martin},
volume={47},
year={2017},
publisher={Cambridge University Press}
}
@article{reed1998fractional,
title={Fractional colouring and Hadwiger's conjecture},
author={Reed, Bruce and Seymour, Paul},
journal={Journal of combinatorial theory, Series B},
volume=74,
pages={147--152},
year=1998
}
@article{van2018improper,
title={Improper colourings inspired by Hadwiger's conjecture},
author={van den Heuvel, Jan and Wood, David R.},
journal={Journal of the London Mathematical Society},
volume=98,
year=2018,
pages={129--148}
}
@article{lokshtanov2017fixed,
title={Fixed-parameter tractable canonization and isomorphism test for graphs of bounded treewidth},
author={Lokshtanov, Daniel and Pilipczuk, Marcin and Pilipczuk, Micha{\l} and Saurabh, Saket},
journal={SIAM Journal on Computing},
volume=46,
pages={161--189},
year=2017
}
@inproceedings{rabinovich2003average,
title={On average distortion of embedding metrics into the line and into L 1},
author={Rabinovich, Yuri},
booktitle={Proceedings of the thirty-fifth annual ACM symposium on Theory of computing},
pages={456--462},
year={2003},
organization={ACM}
}
@article{nevsetvril2013note,
title={A note on {F}iedler value of classes with sublinear separators},
author = "J. Ne{\v{s}}et\v{r}il and P. {Ossona de Mendez}",
journal={Linear Algebra and its Applications},
volume=439,
pages={2216--2221},
year=2013
}
@article{koebe,
author={P. Koebe},
title={Kontaktprobleme der {K}onformen {A}bbildung},
organization={Ber. S{\"a}chs. Akad. Wiss. Leipzig},
journal={Math.-Phys. Kl.},
volume=88,
pages={141--164},
year=1936
}
@article{apxlp,
author={Z. Dvo{\v{r}}{\'a}k},
title = {On distance $r$-dominating and $2r$-independent sets in sparse graphs},
journal = {arXiv},
volume = {1710.10010},
year = 2017
}
@article{dvovrak2018induced,
title={Induced subdivisions and bounded expansion},
author={Z. Dvo{\v{r}}{\'a}k},
journal={European Journal of Combinatorics},
volume=69,
pages={143--148},
year=2018
}
@article{dotri,
title={Do triangle-free planar graphs have exponentially many $3$-colorings?},
author = {Zdenek Dvo\v{r}\'ak and Jean-S{\'e}bastien Sereni},
journal = {Electronic Journal of Combinatorics},
volume = 24,
year = 2017,
pages = {P3.47}
}
@article{req-trfree,
author = {Dvo{\v{r}}{\'a}k, Zden{\v{e}}k and Masa{\v{r}}{\'\i}k, Tom{\'a}{\v{s}} and Mus{\'\i}lek, Jan and Pangr{\'a}c, Ond{\v{r}}ej},
title = {Flexibility of triangle-free planar graphs},
journal = {arXiv},
volume = {1902.02971},
year = 2017
}
@article{trlight,
author = {P. Wernicke},
title = {{\"U}ber den kartographischen {V}ierfarbensatz},
journal = {Math. Ann.},
volume = 58,
year = 1904,
pages = {413--426}}
@article{fctc,
author = {Ken{-}ichi Kawarabayashi and Kenta Ozeki},
title = {A simple algorithm for 4-coloring 3-colorable planar graphs},
journal = {Theor. Comput. Sci.},
volume = 411,
number = {26-28},
pages = {2619--2622},
year = 2010
}
@article{cabello2012algorithms,
title={Algorithms for the edge-width of an embedded graph},
author={Cabello, Sergio and de Verdiere, {\'E}ric Colin and Lazarus, Francis},
journal={Computational Geometry},
volume=45,
pages={215--224},
year=2012
}
@inproceedings{lamsep,
author = {David Eppstein and
Bruce Reed},
title = {Finding Maximal Sets of Laminar 3-Separators in Planar Graphs in Linear
Time},
booktitle = {Proceedings of the Thirtieth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2019, San Diego, California, USA, January 6-9,
2019},
pages = {589--605},
year = 2019,
}
@article{dvovrak2018planar,
title={Planar graphs have two-coloring number at most 8},
author={Dvo{\v{r}}{\'a}k, Zden{\v{e}}k and Kabela, Adam and Kaiser, Tom{\'a}{\v{s}}},
journal={Journal of Combinatorial Theory, Series B},
volume=130,
pages={144--157},
year=2018
}
@inproceedings{indoc,
author = {Marthe Bonamy and
Edouard Bonnet and
Nicolas Bousquet and
Pierre Charbit and
St{\'{e}}phan Thomass{\'{e}}},
title = {{EPTAS} for Max Clique on Disks and Unit Balls},
booktitle = {59th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2018, Paris, France, October 7-9, 2018},
pages = {568--579},
year = {2018}
}
@article{SS,
author = {Scott, A. and Seymour, P.},
title = {Colouring graphs with no odd holes},
journal = {manuscript},
year = 2014
}
@article{GLS,
author = {Gr\"{o}tschel, M. and Lov\'{a}sz, L. and Schrijver, A.},
title = {Polynomial algorithms for perfect graphs},
journal = {North-Holland mathematics studies},
volume = 88,
pages = {325--356},
year = 1984
}
@article{BCT,
author = {Bonamy, M. and Charbit, P. and Thomass\'{e}, S.},
title = {Graphs with large chromatic number induce $3k$-cycles},
journal = {arXiv},
volume = {1408.2172},
year = 2014
}
@InProceedings{BGKRS,
author = {{\'E}douard Bonnet and Panos Giannopoulos and Eun Jung Kim and Pawel Rzazewski and Florian Sikora},
title = {{QPTAS and Subexponential Algorithm for Maximum Clique on Disk Graphs}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {12:1--12:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
year = 2018,
volume = 99,
editor = {Bettina Speckmann and Csaba D. T{\'o}th},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany}
}
@inproceedings{polycen,
author = {Michal Pilipczuk and Sebastian Siebertz},
title = {Polynomial bounds for centered colorings on proper minor-closed graph classes},
booktitle = {Proceedings of the Thirtieth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2019, San Diego, California, USA, January 6-9, 2019},
pages = {1501--1520},
year = 2019
}
@article{devos2018structure,
title={The structure of graphs with no {$K_{3,3}$} immersion},
author={DeVos, Matt and Malekian, Mahdieh},
journal={arXiv},
volume={1810.12873},
year={2018}
}
@article{devos2018structurew4,
title={The structure of graphs with no {$W_4$} immersion},
author={DeVos, Matt and Malekian, Mahdieh},
journal={arXiv},
volume={1810.12863},
year={2018}
}
@article{giannopoulou2015forbidding,
title={Forbidding Kuratowski graphs as immersions},
author={Giannopoulou, Archontia C. and Kami{\'n}ski, Marcin and Thilikos, Dimitrios M.},
journal={Journal of Graph Theory},
volume=78,
pages={43--60},
year=2015
}
@article{har2016notes,
title={Notes on approximation algorithms for polynomial-expansion and low-density graphs},
author={Har-Peled, Sariel and Quanrud, Kent},
journal={arXiv},
volume={1603.03098},
year={2016}
}
@article{arman2017maximum,
title={The maximum number of cycles in a graph with fixed number of edges},
author={Arman, Andrii and Tsaturian, Sergei},
journal={arXiv},
volume={1702.02662},
year={2017}
}
@article{morrison2019maximising,
title={Maximising the number of cycles in graphs with forbidden subgraphs},
author={Morrison, Natasha and Roberts, Alexander and Scott, Alex},
journal={arXiv},
volume={1902.08133},
year={2019}
}
@techreport{kiraly2009maximum,
title={Maximum number of cycles and hamiltonian cycles in sparse graphs},
author={Kir{\'a}ly, Zolt{\'a}n},
year={2009},
institution={Egerv{\'a}ry Research Group},
volume={2009-03}
}
@article{glebkriv,
title={On the number of Hamilton cycles in sparse random graphs},
author={R. Glebov and M. Krivelevich},
journal={SIAM J. Discrete Math.},
volume=27,
year=2013,
pages={27--42}
}
@phdthesis{patkos,
author={B. Patk{\'{o}}s},
title={Problems in extremal finite set theory},
school={Central European University, Budapest},
year=2007}
@article{erdos1946structure,
title={On the structure of linear graphs},
author={Erdos, Paul and Stone, Arthur H and others},
journal={Bull. Amer. Math. Soc},
volume=52,
pages={1087-1091},
year=1946
}
@article{DJM+,
author={V. Dujmovi{\'c} and G. Joret and P. Micek and P. Morin and T. Ueckerdt and D.~R. Wood},
title={Planar Graphs have Bounded Queue-Number},
journal={Journal of the ACM},
volume=67,
pages=22,
year=2020}
@article{wood2018defective,
title={Defective and Clustered Graph Colouring},
author={Wood, David R},
journal={The Electronic Journal of Combinatorics},
volume={1000},
pages={23--13},
year={2018}
}
@article{espjor,
title={Colouring planar graphs with three colours and no large monochromatic components},
author={L. Esperet and G. Joret},
journal={Combinatorics, Probability and Computing},
volume=23,
year=2014,
pages={551--570}
}
@article{twocom,
author = {Paul D. Seymour},
title = {A short proof of the two-commodity flow theorem},
journal = {J. Comb. Theory, Ser. {B}},
volume = 26,
number = 3,
pages = {370--371},
year = 1979
}
@article{postledistr,
author = {Luke Postle},
title = {Linear-Time and Efficient Distributed Algorithms for List Coloring Graphs on Surfaces},
journal = {arXiv},
volume = {1904.03723},
year = 2019
}
@article{list5col,
author = {Luke Postle and Robin Thomas},
title = {Five-list-coloring graphs on surfaces {II.} {A} linear bound for critical graphs in a disk},
journal = {J. Comb. Theory, Ser. {B}},
volume = 119,
pages = {42--65},
year = 2016
}
@article{lee2016separators,
title={Separators in region intersection graphs},
author={Lee, James R},
journal={arXiv},
volume={1608.01612},
year={2016}
}
@article{chakerian1967some,
title={Some intersection properties of convex bodies},
author={Chakerian, G. D. and Stein, S. K.},
journal={Proceedings of the American Mathematical Society},
volume=18,
number=1,
pages={109--112},
year=1967
}
@article{miller1998geometric,
title={Geometric separators for finite-element meshes},
author={Miller, Gary L. and Teng, Shang-Hua and Thurston, William and Vavasis, Stephen A.},
journal={SIAM Journal on Scientific Computing},
volume={19},
number={2},
pages={364--386},
year={1998}
}
@article{biswal2010eigenvalue,
title={Eigenvalue bounds, spectral partitioning, and metrical deformations via flows},
author={Biswal, Punyashloka and Lee, James R. and Rao, Satish},
journal={Journal of the ACM (JACM)},
volume={57},
number={3},
pages={13},
year={2010}
}
@inproceedings{smith1998geometric,
title={Geometric separator theorems and applications},
author={Smith, Warren D and Wormald, Nicholas C},
booktitle={Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No. 98CB36280)},
pages={232--243},
year={1998},
organization={IEEE}
}
@article{atar,
author = {Xuding Zhu},
title = {The {A}lon-{T}arsi number of planar graphs},
journal = {J. Comb. Theory, Ser. {B}},
volume = 134,
pages = {354--358},
year = 2019
}
@Article{KraLee07,
author = {Krauthgamer, Robert and Lee, James R.},
title = {The intrinsic dimensionality of graphs},
journal = {Combinatorica},
year = {2007},
volume = {27},
number = {5},
pages = {551--585}
}
@article{zhutarsi,
author = {Xuding Zhu},
title = {The {A}lon-{T}arsi number of planar graphs},
journal = {J. Comb. Theory, Ser. {B}},
volume = 134,
pages = {354--358},
year = 2019
}
@article{vanDerStappen1993,
author = "A.Frank van der Stappen and Dan Halperin and Mark H. Overmars",
title = "The complexity of the free space for a robot moving amidst fat obstacles",
journal = "Computational Geometry",
volume = "3",
number = "6",
pages = "353 - 373",
year = "1993",
issn = "0925-7721",
doi = "https://doi.org/10.1016/0925-7721(93)90007-S"
}
@inproceedings{teng1991unified,
title={Unified Geometric Approach to Graph Separators},
author={G.L. Miller and S.-H. Teng and S.A. Vavasis},
booktitle={Proc. 31st Ann. Symp. Foundations of Computer Science},
pages={538--547},
year={1991}
}
@article{shapira2015small,
title={Small complete minors above the extremal edge density},
author={Shapira, Asaf and Sudakov, Benny},
journal={Combinatorica},
volume=35,
pages={75--94},
year=2015
}
@inproceedings{chekuri2014degree,
title={Degree-3 treewidth sparsifiers},
author={Chekuri, Chandra and Chuzhoy, Julia},
booktitle={Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms},
pages={242--255},
year=2015,
organization={SIAM}
}
@article{fralo,
author = {Kathryn Fraughnaugh and Stephen C. Locke},
title = {11/30 (Finding Large Independent Sets in Connected Triangle-Free 3-Regular Graphs)},
journal = {J. Comb. Theory, Ser. {B}},
volume = 65,
pages = {51--72},
year = 1995
}
@article{bajnok1998independence,
title={On the independence number of triangle free graphs with maximum degree three},
author={Bajnok, B. and Brinkmann, G.},
journal={Journal of Combinatorial Mathematics and Combinatorial Computing},
volume=26,
pages={237--254},
year=1998
}
@article{van2019large,
title={Large independent sets in triangle-free cubic graphs: beyond planarity},
author={van Batenburg, Wouter Cames and Goedgebeur, Jan and Joret, Gwena{\"e}l},
journal={arXiv},
volume={1911.12471},
year=2019
}
@article{sepprof,
author={I. Benjamini and O. Schramm and {\'A}. Tim{\'a}r},
title={On the separation profile of infinite graphs},
journal={Groups Geom. Dyn.},
volume=6,
year=2012}
@article{covcol,
author = {Grohe, M. and Kreutzer, S. and Rabinovich, R. and Siebertz, S. and Stavropoulos, K.},
title = {Coloring and Covering Nowhere Dense Graphs},
journal = {SIAM Journal on Discrete Mathematics},
volume = 32,
pages = {2467-2481},
year = 2018}
@book{gallier2013guide,
title={A guide to the classification theorem for compact surfaces},
author={Gallier, Jean and Xu, Dianna},
year=2013,
publisher={Springer Science \& Business Media}
}
@inproceedings{postledistr-focs,
author = {Luke Postle},
title = {Linear-Time and Efficient Distributed Algorithms for List Coloring Graphs on Surfaces},
booktitle = {60th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS} 2019, Baltimore, Maryland, USA, November 9-12, 2019},
pages = {929--941},
publisher = {{IEEE} Computer Society},
year = {2019}
}
@article{mohar1999linear,
title={A linear time algorithm for embedding graphs in an arbitrary surface},
author={Mohar, Bojan},
journal={SIAM Journal on Discrete Mathematics},
volume=12,
pages={6--26},
year=1999
}
@inproceedings{rao1999small,
title={Small distortion and volume preserving embeddings for planar and Euclidean metrics},
author={Rao, Satish},
booktitle={Proceedings of the fifteenth annual symposium on Computational geometry},
pages={300--306},
year={1999}
}
@incollection{fakcharoenphol2003improved,
title={An improved decomposition theorem for graphs excluding a fixed minor},
author={Fakcharoenphol, Jittat and Talwar, Kunal},
booktitle={Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques},
pages={36--46},
year={2003},
publisher={Springer}
}
@article{dvorak2020weighted,
title={On weighted sublinear separators},
author={Zden\v{e}k Dvo\v{r}\'ak},
year=2020,
journal="arXiv",
volume={2007.11853}
}
@inproceedings{bartal1996probabilistic,
title={Probabilistic approximation of metric spaces and its algorithmic applications},
author={Bartal, Yair},
booktitle={Proceedings of 37th Conference on Foundations of Computer Science},
pages={184--193},
year={1996},
organization={IEEE}
}
@article{subconvex,
author = {Z. Dvo{\v{r}}{\'a}k and R. McCarty and S. Norin},
title = {Sublinear separators in intersection graphs of convex shapes},
journal = "arXiv",
volume = {2001.01552},
year = 2020}
@article{dujmovic2019graph,
title={Graph product structure for non-minor-closed classes},
author={Dujmovi{\'c}, Vida and Morin, Pat and Wood, David R},
journal={arXiv},
volume={1907.05168},
year=2019
}
@article{erlebach2005polynomial,
title={Polynomial-time approximation schemes for geometric intersection graphs},
author={Erlebach, T. and Jansen, K. and Seidel, E.},
journal={SIAM Journal on Computing},
volume=34,
pages={1302--1323},
year=2005
}
@article{thom-noexp,
title = {Exponentially many 3-colorings of planar triangle-free graphs with no short separating cycles},
journal = {Journal of Combinatorial Theory, Series B},
year = {2021},
author = {C. Thomassen},
note="In Press"
}
@article{mohar2002coloring,
title={Coloring Eulerian triangulations of the projective plane},
author={Mohar, Bojan},
journal={Discrete Mathematics},
volume=244,
pages={339--344},
year=2002
}
@article{islands,
title={Islands in minor-closed classes. I. Bounded treewidth and separators},
author={Zdenek Dvo\v{r}\'ak and Sergey Norin},
year={2017},
volume={1710.02727},
journal={arXiv}
}
@article{exp5,
author={G.D. Birkhoff and D.C. Lewis},
title={Chromatic polynomials},
journal={Trans. Amer. Math. Soc.},
volume=60,
year=1946,
pages={355--451}}
@article{nonexp2021,
title = {Exponentially many 3-colorings of planar triangle-free graphs with no short separating cycles},
journal = {Journal of Combinatorial Theory, Series B},
year = 2021,
author = {Carsten Thomassen},
note = {In Press}
}
@inproceedings{felsner2011contact,
title={Contact representations of planar graphs with cubes},
author={Felsner, S. and Francis, M.C.},
booktitle={Proceedings of the twenty-seventh annual symposium on Computational geometry},
pages={315--320},
year={2011}
}
@article{wcolig,
title={Weak Coloring Numbers of Intersection Graphs},
author={Dvo{\v{r}}{\'a}k, Z. and Pek{\'a}rek, J. and T. Ueckerdt and Y. Yuditsky},
year={2021},
volume={2103.17094},
journal={arXiv}
}
@inproceedings{distapx,
author = {Z. Dvor{\'{a}}k and
A. Lahiri},
title = {Approximation Schemes for Bounded Distance Problems on Fractionally
Treewidth-Fragile Graphs},
booktitle = {29th Annual European Symposium on Algorithms, {ESA} 2021, September
6-8, 2021, Lisbon, Portugal (Virtual Conference)},
series = {LIPIcs},
volume = {204},
pages = {40:1--40:10},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2021}
}
@article{logapx,
author = {Z. Dvor{\'{a}}k},
title = {Approximation metatheorem for fractionally treewidth-fragile graphs},
journal = {arXiv},
volume = {2103.08698},
year = {2021}
}
@article{box-treewidth,
author = {L. Sunil Chandran and Naveen Sivadasan},
title = {Boxicity and treewidth},
journal = {Journal of Combinatorial Theory, Series B},
volume = {97},
number = {5},
pages = {733--744},
year = {2007},
issn = {0095-8956},
doi = {https://doi.org/10.1016/j.jctb.2006.12.004},
url = {https://www.sciencedirect.com/science/article/pii/S0095895607000111},
}
@book{graphsandgeom,
author= {L. Lov\'asz},
title={Graphs and Geometry},
publisher={American Mathematical Society},
year=2019,
address = "Providence"}
@article{sachs94,
author = {H. Sachs},
title = {Coin graphs, polyhedra, and conformal mapping },
journal = {Discrete Mathematics},
volume = 134,
year=1994,
pages={133--138}}
}
@article{albertson2004coloring,
title={Coloring with no $2$-Colored ${P}_4$'s},
author={Albertson, M.O. and Chappell, G.G. and Kierstead, H.A. and K{\"u}ndgen, A. and Ramamurthi, R.},
journal={The Electronic Journal of Combinatorics},
pages={R26--R26},
year={2004}
}