zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Characterisations and examples of graph classes with bounded expansion. (English) Zbl 1230.05250
Summary: Classes with bounded expansion, which generalise classes that exclude a topological minor, have recently been introduced by Nešetřil and Ossona de Mendez. These classes are defined by the fact that the maximum average degree of a shallow minor of a graph in the class is bounded by a function of the depth of the shallow minor. Several linear-time algorithms are known for bounded expansion classes (such as subgraph isomorphism testing), and they allow restricted homomorphism dualities, amongst other desirable properties. In this paper we establish two new characterisations of bounded expansion classes, one in terms of so-called topological parameters, the other in terms of controlling dense parts. The latter characterisation is then used to show that the notion of bounded expansion is compatible with Erdös-Rényi model of random graphs with constant average degree. In particular, we prove that for every fixed d>0, there exists a class with bounded expansion, such that a random graph of order n and edge probability d/n asymptotically almost surely belongs to the class. We then present several new examples of classes with bounded expansion that do not exclude some topological minor, and appear naturally in the context of graph drawing or graph colouring. In particular, we prove that the following classes have bounded expansion: graphs that can be drawn in the plane with a bounded number of crossings per edge, graphs with bounded stack number, graphs with bounded queue number, and graphs with bounded non-repetitive chromatic number. We also prove that graphs with ‘linear’ crossing number are contained in a topologically-closed class, while graphs with bounded crossing number are contained in a minor-closed class.
MSC:
05C75Structural characterization of families of graphs
References:
[1]AEOLUS, structural properties of overlay computers: state of the art survey and algorithmic solutions, Deliverable D1.1.1, Project IP-FP6-015964 of EEC, 2006. http://aeolus.ceid.upatras.gr/sub-projects/deliverables/D111.pdf.
[2]Aigner, M.; Ziegler, G. M.: Proofs from the book, (2004)
[3]Ajtai, M.; Chvátal, V.; Newborn, M. M.; Szemerédi, E.: Crossing-free subgraphs, North-holland math. Stud. 60, 9-12 (1982) · Zbl 0502.05021
[4]Ajtai, M.; Komlós, J.; Szemerédi, E.: Topological complete subgraphs in random graphs, Studia sci. Math. hungar. 14, 293-297 (1979) · Zbl 0489.05051
[5]Albertson, M. O.; Chappell, G. G.; Kierstead, H. A.; Kündgen, A.; Ramamurthi, R.: Coloring with no 2-colored p4’s, Electron. J. Combin. 11, #R26 (2004)
[6]Alon, N.; Grytczuk, J.: Breaking the rhythm on graphs, Discrete math. 308, 1375-1380 (2008) · Zbl 1135.05018 · doi:10.1016/j.disc.2007.07.063
[7]Alon, N.; Grytczuk, J.; Hałuszczak, M.; Riordan, O.: Nonrepetitive colorings of graphs, Random structures algorithms 21, No. 3–4, 336-346 (2002) · Zbl 1018.05032 · doi:10.1002/rsa.10057
[8]Alon, N.; Marshall, T. H.: Homomorphisms of edge-colored graphs and Coxeter groups, J. algebraic combin. 8, No. 1, 5-13 (1998) · Zbl 0911.05034 · doi:10.1023/A:1008647514949
[9]G.H. Atneosen, On the embeddability of compacta in n-books: intrinsic and extrinsic properties, Ph.D. Thesis, Michigan State University, USA, 1968.
[10]Barát, J.; Varjú, P. P.: On square-free vertex colorings of graphs, Studia sci. Math. hungar. 44, No. 3, 411-422 (2007) · Zbl 1164.05021 · doi:10.1556/SScMath.2007.1029
[11]Barát, J.; Varjú, P. P.: On square-free edge colorings of graphs, Ars combin. 87, 377-383 (2008) · Zbl 1224.05157
[12]Barát, J.; Wood, D. R.: Notes on nonrepetitive graph colouring, Electron. J. Combin. 15, R99 (2008) · Zbl 1163.05316 · doi:emis:journals/EJC/Volume_15/Abstracts/v15i1r99.html
[13]Bernhart, F. R.; Kainen, P. C.: The book thickness of a graph, J. combin. Theory ser. B 27, No. 3, 320-331 (1979) · Zbl 0427.05028 · doi:10.1016/0095-8956(79)90021-2
[14]R. Blankenship, Book embeddings of graphs, Ph.D. Thesis, Department of Mathematics, Louisiana State University, USA, 2003.
[15]R. Blankenship, B. Oporowski, Drawing subdivisions of complete and complete bipartite graphs on books, Tech. Rep. 1999-4, Department of Mathematics, Louisiana State University, USA, 1999.
[16]Bollobás, B.: Random graphs, (2001)
[17]Brešar, B.; Grytczuk, J.; Klavžar, S.; Niwczyk, S.; Peterin, I.: Nonrepetitive colorings of trees, Discrete math. 307, No. 2, 163-172 (2007) · Zbl 1106.68089 · doi:10.1016/j.disc.2006.06.017
[18]Brešar, B.; Klavžar, S.: Square-free colorings of graphs, Ars combin. 70, 3-13 (2004) · Zbl 1093.05023
[19]Currie, J. D.: Pattern avoidance: themes and variations, Theoret. comput. Sci. 339, No. 1, 7-18 (2005) · Zbl 1076.68051 · doi:10.1016/j.tcs.2005.01.004
[20]Czerwiński, S.; Grytczuk, J.: Nonrepetitive colorings of graphs, Electron. notes discrete math. 28, 453-459 (2007)
[21]Dawar, A.: Finite model theory on tame classes of structures, Lecture notes in computer science 4708, 2-12 (2007) · Zbl 1147.03311 · doi:10.1007/978-3-540-74456-6_2
[22]Devos, M.; Ding, G.; Oporowski, B.; Sanders, D. P.; Reed, B.; Seymour, P.; Vertigan, D.: Excluding any graph as a minor allows a low tree-width 2-coloring, J. combin. Theory ser. B 91, No. 1, 25-41 (2004) · Zbl 1042.05036 · doi:10.1016/j.jctb.2003.09.001
[23]Dujmović, V.; Por, A.; Wood, D. R.: Track layouts of graphs, Discrete math. Theor. comput. Sci. 6, No. 2, 497-522 (2004) · Zbl 1066.68095 · doi:emis:journals/DMTCS/volumes/abstracts/dm060221.abs.html
[24]Dujmović, V.; Morin, P.; Wood, D. R.: Layout of graphs with bounded tree-width, SIAM J. Comput. 34, No. 3, 553-579 (2005) · Zbl 1069.05055 · doi:10.1137/S0097539702416141
[25]Dujmović, V.; Wood, D.: Stacks, queues and tracks: layouts of graph subdivisions, DIMACS ser. Discrete math. Theoret. comput. Sci. 7, 155-202 (2005) · Zbl 1153.05036 · doi:http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/issue/view/53
[26]Dujmović, V.; Wood, D. R.: On linear layouts of graphs, Discrete math. Theor. comput. Sci. 6, No. 2, 339-358 (2004) · Zbl 1059.05077 · doi:emis:journals/DMTCS/volumes/abstracts/dm060210.abs.html
[27]Dujmović, V.; Wood, D. R.: Stacks, queues and tracks: layouts of graph subdivisions, Discrete math. Theor. comput. Sci. 7, 155-202 (2005) · Zbl 1153.05036 · doi:http://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/issue/view/53
[28]Z. Dvořák, Asymptotical structure of combinatorial objects, Ph.D. Thesis, Faculty of Mathematics and Physics, Charles University, Czech Republic, 2007.
[29]Dvořák, Z.: On forbidden subdivision characterization of graph classes, European J. Combin. 29, No. 5, 1321-1332 (2008) · Zbl 1151.05038 · doi:10.1016/j.ejc.2007.05.008
[30]Enomoto, H.; Miyauchi, M. S.: Embedding graphs into a three page book with O(MlogN) crossings of edges over the spine, SIAM J. Discrete math. 12, No. 3, 337-341 (1999) · Zbl 0933.05043 · doi:10.1137/S0895480195280319
[31]Enomoto, H.; Miyauchi, M. S.; Ota, K.: Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph, Discrete appl. Math. 92, No. 2–3, 149-155 (1999) · Zbl 0933.05042 · doi:10.1016/S0166-218X(99)00044-X
[32]Eppstein, D.: Separating thickness from geometric thickness, Lecture notes in comput. Sci. 2528, 150-161 (2002) · Zbl 1037.68582 · doi:http://link.springer.de/link/service/series/0558/bibs/2528/25280150.htm
[33]Erdos, P.; Rényi, A.: The evolution of random graphs, Magyar tud. Akad. mat. Kutató int. Kozl 5, 17-61 (1960) · Zbl 0103.16301
[34]Fertin, G.; Raspaud, A.; Reed, B.: On star coloring of graphs, J. graph theory 47, No. 3, 163-182 (2004) · Zbl 1055.05051 · doi:10.1002/jgt.20029
[35]Fountoulakis, N.; Kühn, D.; Osthus, D.: The order of the largest complete minor in a random graph, Random structures algorithms 33, No. 2, 127-141 (2008) · Zbl 1230.05261 · doi:10.1002/rsa.20215
[36]Fox, J.; Sudakov, B.: Two remarks on the burr-Erdös conjecture, European J. Combin. 30, No. 7, 1630-1645 (2008) · Zbl 1223.05185 · doi:10.1016/j.ejc.2009.03.004
[37]Galil, Z.; Kannan, R.; Szemerédi, E.: On 3-pushdown graphs with large separators, Combinatorica 9, No. 1, 9-19 (1989) · Zbl 0726.05042 · doi:10.1007/BF02122679
[38]Galil, Z.; Kannan, R.; Szemerédi, E.: On nontrivial separators for k-page graphs and simulations by nondeterministic one-tape Turing machines, J. comput. System sci. 38, No. 1, 134-149 (1989) · Zbl 0676.68019 · doi:10.1016/0022-0000(89)90036-6
[39]Gilbert, E.: Random graphs, Ann. math. Statist. 30, 1141-1144 (1959) · Zbl 0168.40801 · doi:10.1214/aoms/1177706098
[40]Grytczuk, J.: Nonrepetitive colorings of graphs–a survey, Int. J. Math. math. Sci. (2007) · Zbl 1139.05020 · doi:10.1155/2007/74639
[41]Grytczuk, J.: Pattern avoidance on graphs, Discrete math. 307, No. 11–12, 1341-1346 (2007) · Zbl 1149.05016 · doi:10.1016/j.disc.2005.11.071
[42]Grytczuk, J.: Thue type problems for graphs, points, and numbers, Discrete math. 308, No. 19, 4419-4429 (2008) · Zbl 1160.05036 · doi:10.1016/j.disc.2007.08.039
[43]Heath, L. S.; Leighton, F. T.; Rosenberg, A. L.: Comparing queues and stacks as mechanisms for laying out graphs, SIAM J. Discrete math. 5, No. 3, 398-412 (1992) · Zbl 0764.05093 · doi:10.1137/0405031
[44]Heath, L. S.; Pemmaraju, S. V.: Stack and queue layouts of posets, SIAM J. Discrete math. 10, No. 4, 599-625 (1997) · Zbl 0884.05086 · doi:10.1137/S0895480193252380
[45]Heath, L. S.; Rosenberg, A. L.: Laying out graphs using queues, SIAM J. Comput. 21, No. 5, 927-958 (1992) · Zbl 0778.05078 · doi:10.1137/0221055
[46]Hotz, G.: Ein satz über mittellinien, Arch. math. 10, 314-320 (1959) · Zbl 0135.41803 · doi:10.1007/BF01240804
[47]Hotz, G.: Arkadenfadendarstellung von knoten und eine neue darstellung der knotengruppe, Abh. math. Sem. univ. Hamburg 24, 132-148 (1960) · Zbl 0102.38706 · doi:10.1007/BF02942026
[48]Kannan, R.: Unraveling k-page graphs, Inf. control 66, No. 1–2, 1-5 (1985) · Zbl 0584.05055 · doi:10.1016/S0019-9958(85)80008-5
[49]Kündgen, A.; Pelsmajer, M. J.: Nonrepetitive colorings of graphs of bounded tree-width, Discrete math. 308, No. 19, 4473-4478 (2008) · Zbl 1154.05033 · doi:10.1016/j.disc.2007.08.043
[50]Leighton, F. T.: Complexity issues in VLSI, (1983)
[51]łuczak, T.; Pittel, B.; Wierman, J.: The structure of a random graph at the point of the phase transition, Trans. amer. Math. soc. 341, 721-748 (1994) · Zbl 0807.05065 · doi:10.2307/2154580
[52]F. Manin, The complexity of nonrepetitive edge coloring of graphs, 2007. http://arXiv.org/abs/0709.4497.
[53]Marx, D.; Schaefer, M.: The complexity of nonrepetitive coloring, Discrete appl. Math. 157, 13-18 (2009) · Zbl 1188.05066 · doi:10.1016/j.dam.2008.04.015
[54]Miyauchi, M. S.: An O(nm) algorithm for embedding graphs into a 3-page book, IEICE trans. 77-A, No. 3, 521-526 (1994)
[55]Miyauchi, M. S.: Embedding a graph into a d+1-page book with mlogdn edge-crossings over the spine, IEICE trans. Fundam. 88-A, No. 5, 1136-1139 (2005)
[56]Nešetřil, J.; De Mendez, P. Ossona: The Grad of a graph and classes with bounded expansion, Electronic notes in discrete mathematics 22, 101-106 (2005) · Zbl 1182.05102 · doi:10.1016/j.endm.2005.06.018
[57]Nešetřil, J.; De Mendez, P. Ossona: Linear time low tree-width partitions and algorithmic consequences, , 391-400 (2006)
[58]Nešetřil, J.; De Mendez, P. Ossona: Tree-depth, subgraph coloring and homomorphism bounds, European J. Combin. 27, No. 6, 1022-1041 (2006) · Zbl 1089.05025 · doi:10.1016/j.ejc.2005.01.010
[59]Nešetřil, J.; De Mendez, P. Ossona: Grad and classes with bounded expansion I. Decompositions, European J. Combin. 29, No. 3, 760-776 (2008) · Zbl 1156.05056 · doi:10.1016/j.ejc.2006.07.013
[60]Nešetřil, J.; De Mendez, P. Ossona: Grad and classes with bounded expansion II. Algorithmic aspects, European J. Combin. 29, No. 3, 777-791 (2008) · Zbl 1185.05131 · doi:10.1016/j.ejc.2006.07.014
[61]Nešetřil, J.; De Mendez, P. Ossona: Grad and classes with bounded expansion III. Restricted graph homomorphism dualities, European J. Combin. 29, No. 4, 1012-1024 (2008) · Zbl 1213.05240 · doi:10.1016/j.ejc.2007.11.019
[62]Nešetřil, J.; De Mendez, P. Ossona: Structural properties of sparse graphs, Bolyai society mathematical studies 19 (2008)
[63]J. Nešetřil, P. Ossona de Mendez, From sparse graphs to nowhere dense structures: decompositions, independence, dualities and limits, in: Proc. of the Fifth European Congress of Mathematics, 2009.
[64]Nešetřil, J.; De Mendez, P. Ossona: First order properties on nowhere dense structures, J. symbolic logic 75, No. 3, 868-887 (2010) · Zbl 1206.03033 · doi:10.2178/jsl/1278682204
[65]Nešetřil, J.; De Mendez, P. Ossona: How many f’s are there in G?, European J. Combin. 32, No. 7, 1126-1141 (2011)
[66]Nešetřil, J.; De Mendez, P. Ossona: On nowhere dense graphs, European J. Combin. 32, No. 4, 600-617 (2011)
[67]Nešetřil, J.; Raspaud, A.: Colored homomorphisms of colored mixed graphs, J. combin. Theory ser. B 80, No. 1, 147-155 (2000) · Zbl 1026.05047 · doi:10.1006/jctb.2000.1977
[68]Pach, J.; Tóth, G.: Graphs drawn with few crossings per edge, Combinatorica 17, No. 3, 427-439 (1997) · Zbl 0902.05017 · doi:10.1007/BF01215922
[69]Pach, J.; Tóth, G.: Which crossing number is it anyway?, J. combin. Theory ser. B 80, No. 2, 225-246 (2000) · Zbl 1023.05042 · doi:10.1006/jctb.2000.1978
[70]S.V. Pemmaraju, Exploring the powers of stacks and queues via graph layouts, Ph.D. Thesis, Virginia Polytechnic Institute and State University, USA, 1992.
[71]Pezarski, A.; Zmarz, M.: Non-repetitive 3-coloring of subdivided graphs, Electron. J. Combin. 16, #N15 (2009)
[72]Plotkin, S.; Rao, S.; Smith, W. D.: Shallow excluded minors and improved graph decompositions, , 462-470 (1994) · Zbl 0867.05069
[73]Robertson, N.; Seymour, P. D.: Graph minors I–XXI, J. combin. Theory ser. B (1983–2009)
[74]Székely, L. A.: A successful concept for measuring non-planarity of graphs: the crossing number, Discrete math. 276, No. 1–3, 331-352 (2004) · Zbl 1035.05034 · doi:10.1016/S0012-365X(03)00317-0
[75]A. Thue, Über unendliche Zeichenreichen. Norske Videnskabers Selskabs Skrifter Mat.-Nat. Kl. (Kristiana) 7 (1906) 1–22. · Zbl 37.0066.17
[76]Wood, D. R.: Acyclic, star and oriented colourings of graph subdivisions, Discrete math. Theor. comput. Sci. 7, No. 1, 37-50 (2005) · Zbl 1066.68100 · doi:emis:journals/DMTCS/volumes/abstracts/dm070104.abs.html
[77]Wood, D. R.: Clique minors in Cartesian products of graphs, New York J. Math. 17, 627-682 (2011)
[78]Yannakakis, M.: Embedding planar graphs in four pages, J. comput. System sci. 38, No. 1, 36-67 (1989) · Zbl 0673.05022 · doi:10.1016/0022-0000(89)90032-9
[79]Zhu, X.: Colouring graphs with bounded generalized colouring number, Discrete math. 309, No. 18, 5562-5568 (2009) · Zbl 1216.05043 · doi:10.1016/j.disc.2008.03.024