for Journals by Title or ISSN
for Articles by Keywords
help
  Subjects -> ENGINEERING (Total: 2268 journals)
    - CHEMICAL ENGINEERING (190 journals)
    - CIVIL ENGINEERING (183 journals)
    - ELECTRICAL ENGINEERING (103 journals)
    - ENGINEERING (1201 journals)
    - ENGINEERING MECHANICS AND MATERIALS (380 journals)
    - HYDRAULIC ENGINEERING (55 journals)
    - INDUSTRIAL ENGINEERING (67 journals)
    - MECHANICAL ENGINEERING (89 journals)

ENGINEERING (1201 journals)                  1 2 3 4 5 6 7 | Last

Showing 1 - 200 of 1205 Journals sorted alphabetically
3 Biotech     Open Access   (Followers: 7)
3D Research     Hybrid Journal   (Followers: 17)
AAPG Bulletin     Hybrid Journal   (Followers: 7)
AASRI Procedia     Open Access   (Followers: 15)
Abstract and Applied Analysis     Open Access   (Followers: 3)
Aceh International Journal of Science and Technology     Open Access   (Followers: 2)
ACS Nano     Full-text available via subscription   (Followers: 246)
Acta Geotechnica     Hybrid Journal   (Followers: 7)
Acta Metallurgica Sinica (English Letters)     Hybrid Journal   (Followers: 5)
Acta Polytechnica : Journal of Advanced Engineering     Open Access   (Followers: 2)
Acta Scientiarum. Technology     Open Access   (Followers: 3)
Acta Universitatis Cibiniensis. Technical Series     Open Access  
Active and Passive Electronic Components     Open Access   (Followers: 7)
Adaptive Behavior     Hybrid Journal   (Followers: 11)
Adıyaman Üniversitesi Mühendislik Bilimleri Dergisi     Open Access  
Adsorption     Hybrid Journal   (Followers: 4)
Advanced Engineering Forum     Full-text available via subscription   (Followers: 6)
Advanced Science     Open Access   (Followers: 5)
Advanced Science Focus     Free   (Followers: 3)
Advanced Science Letters     Full-text available via subscription   (Followers: 9)
Advanced Science, Engineering and Medicine     Partially Free   (Followers: 7)
Advanced Synthesis & Catalysis     Hybrid Journal   (Followers: 17)
Advances in Calculus of Variations     Hybrid Journal   (Followers: 2)
Advances in Catalysis     Full-text available via subscription   (Followers: 5)
Advances in Complex Systems     Hybrid Journal   (Followers: 7)
Advances in Engineering Software     Hybrid Journal   (Followers: 26)
Advances in Fuel Cells     Full-text available via subscription   (Followers: 16)
Advances in Fuzzy Systems     Open Access   (Followers: 5)
Advances in Geosciences (ADGEO)     Open Access   (Followers: 10)
Advances in Heat Transfer     Full-text available via subscription   (Followers: 22)
Advances in Human Factors/Ergonomics     Full-text available via subscription   (Followers: 26)
Advances in Magnetic and Optical Resonance     Full-text available via subscription   (Followers: 9)
Advances in Natural Sciences: Nanoscience and Nanotechnology     Open Access   (Followers: 29)
Advances in Operations Research     Open Access   (Followers: 11)
Advances in OptoElectronics     Open Access   (Followers: 5)
Advances in Physics Theories and Applications     Open Access   (Followers: 12)
Advances in Polymer Science     Hybrid Journal   (Followers: 41)
Advances in Porous Media     Full-text available via subscription   (Followers: 4)
Advances in Remote Sensing     Open Access   (Followers: 38)
Advances in Science and Research (ASR)     Open Access   (Followers: 6)
Aerobiologia     Hybrid Journal   (Followers: 1)
African Journal of Science, Technology, Innovation and Development     Hybrid Journal   (Followers: 4)
AIChE Journal     Hybrid Journal   (Followers: 31)
Ain Shams Engineering Journal     Open Access   (Followers: 5)
Akademik Platform Mühendislik ve Fen Bilimleri Dergisi     Open Access  
Alexandria Engineering Journal     Open Access   (Followers: 1)
AMB Express     Open Access   (Followers: 1)
American Journal of Applied Sciences     Open Access   (Followers: 28)
American Journal of Engineering and Applied Sciences     Open Access   (Followers: 11)
American Journal of Engineering Education     Open Access   (Followers: 9)
American Journal of Environmental Engineering     Open Access   (Followers: 17)
American Journal of Industrial and Business Management     Open Access   (Followers: 23)
Analele Universitatii Ovidius Constanta - Seria Chimie     Open Access  
Annals of Combinatorics     Hybrid Journal   (Followers: 3)
Annals of Pure and Applied Logic     Open Access   (Followers: 2)
Annals of Regional Science     Hybrid Journal   (Followers: 7)
Annals of Science     Hybrid Journal   (Followers: 7)
Applicable Algebra in Engineering, Communication and Computing     Hybrid Journal   (Followers: 2)
Applicable Analysis: An International Journal     Hybrid Journal   (Followers: 1)
Applied Catalysis A: General     Hybrid Journal   (Followers: 6)
Applied Catalysis B: Environmental     Hybrid Journal   (Followers: 16)
Applied Clay Science     Hybrid Journal   (Followers: 5)
Applied Computational Intelligence and Soft Computing     Open Access   (Followers: 12)
Applied Magnetic Resonance     Hybrid Journal   (Followers: 4)
Applied Nanoscience     Open Access   (Followers: 8)
Applied Network Science     Open Access   (Followers: 1)
Applied Numerical Mathematics     Hybrid Journal   (Followers: 5)
Applied Physics Research     Open Access   (Followers: 3)
Applied Sciences     Open Access   (Followers: 2)
Applied Spatial Analysis and Policy     Hybrid Journal   (Followers: 4)
Arabian Journal for Science and Engineering     Hybrid Journal   (Followers: 5)
Archives of Computational Methods in Engineering     Hybrid Journal   (Followers: 4)
Archives of Foundry Engineering     Open Access  
Archives of Thermodynamics     Open Access   (Followers: 7)
Arkiv för Matematik     Hybrid Journal   (Followers: 1)
ASEE Prism     Full-text available via subscription   (Followers: 3)
Asia-Pacific Journal of Science and Technology     Open Access  
Asian Engineering Review     Open Access  
Asian Journal of Applied Science and Engineering     Open Access   (Followers: 1)
Asian Journal of Applied Sciences     Open Access   (Followers: 2)
Asian Journal of Biotechnology     Open Access   (Followers: 8)
Asian Journal of Control     Hybrid Journal  
Asian Journal of Current Engineering & Maths     Open Access  
Asian Journal of Technology Innovation     Hybrid Journal   (Followers: 8)
Assembly Automation     Hybrid Journal   (Followers: 2)
at - Automatisierungstechnik     Hybrid Journal   (Followers: 1)
ATZagenda     Hybrid Journal  
ATZextra worldwide     Hybrid Journal  
Australasian Physical & Engineering Sciences in Medicine     Hybrid Journal   (Followers: 1)
Australian Journal of Multi-Disciplinary Engineering     Full-text available via subscription   (Followers: 2)
Autonomous Mental Development, IEEE Transactions on     Hybrid Journal   (Followers: 8)
Avances en Ciencias e Ingeniería     Open Access  
Balkan Region Conference on Engineering and Business Education     Open Access   (Followers: 1)
Bangladesh Journal of Scientific and Industrial Research     Open Access  
Basin Research     Hybrid Journal   (Followers: 5)
Batteries     Open Access   (Followers: 5)
Bautechnik     Hybrid Journal   (Followers: 1)
Bell Labs Technical Journal     Hybrid Journal   (Followers: 23)
Beni-Suef University Journal of Basic and Applied Sciences     Open Access   (Followers: 4)
BER : Manufacturing Survey : Full Survey     Full-text available via subscription   (Followers: 2)
BER : Motor Trade Survey     Full-text available via subscription   (Followers: 1)
BER : Retail Sector Survey     Full-text available via subscription   (Followers: 2)
BER : Retail Survey : Full Survey     Full-text available via subscription   (Followers: 2)
BER : Survey of Business Conditions in Manufacturing : An Executive Summary     Full-text available via subscription   (Followers: 3)
BER : Survey of Business Conditions in Retail : An Executive Summary     Full-text available via subscription   (Followers: 3)
Bharatiya Vaigyanik evam Audyogik Anusandhan Patrika (BVAAP)     Open Access   (Followers: 1)
Biofuels Engineering     Open Access  
Biointerphases     Open Access   (Followers: 1)
Biomaterials Science     Full-text available via subscription   (Followers: 10)
Biomedical Engineering     Hybrid Journal   (Followers: 16)
Biomedical Engineering and Computational Biology     Open Access   (Followers: 14)
Biomedical Engineering Letters     Hybrid Journal   (Followers: 5)
Biomedical Engineering, IEEE Reviews in     Full-text available via subscription   (Followers: 17)
Biomedical Engineering, IEEE Transactions on     Hybrid Journal   (Followers: 32)
Biomedical Engineering: Applications, Basis and Communications     Hybrid Journal   (Followers: 5)
Biomedical Microdevices     Hybrid Journal   (Followers: 9)
Biomedical Science and Engineering     Open Access   (Followers: 4)
Biomedizinische Technik - Biomedical Engineering     Hybrid Journal  
Biomicrofluidics     Open Access   (Followers: 4)
BioNanoMaterials     Hybrid Journal   (Followers: 2)
Biotechnology Progress     Hybrid Journal   (Followers: 39)
Boletin Cientifico Tecnico INIMET     Open Access  
Botswana Journal of Technology     Full-text available via subscription   (Followers: 1)
Boundary Value Problems     Open Access   (Followers: 1)
Brazilian Journal of Science and Technology     Open Access   (Followers: 2)
Broadcasting, IEEE Transactions on     Hybrid Journal   (Followers: 10)
Bulletin of Canadian Petroleum Geology     Full-text available via subscription   (Followers: 14)
Bulletin of Engineering Geology and the Environment     Hybrid Journal   (Followers: 10)
Bulletin of the Crimean Astrophysical Observatory     Hybrid Journal  
Cahiers, Droit, Sciences et Technologies     Open Access  
Calphad     Hybrid Journal  
Canadian Geotechnical Journal     Hybrid Journal   (Followers: 25)
Canadian Journal of Remote Sensing     Full-text available via subscription   (Followers: 43)
Case Studies in Engineering Failure Analysis     Open Access   (Followers: 8)
Case Studies in Thermal Engineering     Open Access   (Followers: 4)
Catalysis Communications     Hybrid Journal   (Followers: 6)
Catalysis Letters     Hybrid Journal   (Followers: 2)
Catalysis Reviews: Science and Engineering     Hybrid Journal   (Followers: 8)
Catalysis Science and Technology     Free   (Followers: 7)
Catalysis Surveys from Asia     Hybrid Journal   (Followers: 3)
Catalysis Today     Hybrid Journal   (Followers: 8)
CEAS Space Journal     Hybrid Journal  
Cellular and Molecular Neurobiology     Hybrid Journal   (Followers: 3)
Central European Journal of Engineering     Hybrid Journal   (Followers: 1)
CFD Letters     Open Access   (Followers: 6)
Chaos : An Interdisciplinary Journal of Nonlinear Science     Hybrid Journal   (Followers: 2)
Chaos, Solitons & Fractals     Hybrid Journal   (Followers: 3)
Chinese Journal of Catalysis     Full-text available via subscription   (Followers: 2)
Chinese Journal of Engineering     Open Access   (Followers: 2)
Chinese Science Bulletin     Open Access   (Followers: 1)
Ciencia e Ingenieria Neogranadina     Open Access  
Ciencia en su PC     Open Access   (Followers: 1)
Ciencias Holguin     Open Access   (Followers: 1)
CienciaUAT     Open Access  
Cientifica     Open Access  
CIRP Annals - Manufacturing Technology     Full-text available via subscription   (Followers: 11)
CIRP Journal of Manufacturing Science and Technology     Full-text available via subscription   (Followers: 14)
City, Culture and Society     Hybrid Journal   (Followers: 22)
Clay Minerals     Full-text available via subscription   (Followers: 10)
Clean Air Journal     Full-text available via subscription   (Followers: 2)
Coal Science and Technology     Full-text available via subscription   (Followers: 3)
Coastal Engineering     Hybrid Journal   (Followers: 11)
Coastal Engineering Journal     Hybrid Journal   (Followers: 5)
Coatings     Open Access   (Followers: 4)
Cogent Engineering     Open Access   (Followers: 2)
Cognitive Computation     Hybrid Journal   (Followers: 4)
Color Research & Application     Hybrid Journal   (Followers: 1)
COMBINATORICA     Hybrid Journal  
Combustion Theory and Modelling     Hybrid Journal   (Followers: 13)
Combustion, Explosion, and Shock Waves     Hybrid Journal   (Followers: 13)
Communications Engineer     Hybrid Journal   (Followers: 1)
Communications in Numerical Methods in Engineering     Hybrid Journal   (Followers: 2)
Components, Packaging and Manufacturing Technology, IEEE Transactions on     Hybrid Journal   (Followers: 26)
Composite Interfaces     Hybrid Journal   (Followers: 6)
Composite Structures     Hybrid Journal   (Followers: 265)
Composites Part A : Applied Science and Manufacturing     Hybrid Journal   (Followers: 188)
Composites Part B : Engineering     Hybrid Journal   (Followers: 278)
Composites Science and Technology     Hybrid Journal   (Followers: 182)
Comptes Rendus Mécanique     Full-text available via subscription   (Followers: 2)
Computation     Open Access  
Computational Geosciences     Hybrid Journal   (Followers: 14)
Computational Optimization and Applications     Hybrid Journal   (Followers: 7)
Computational Science and Discovery     Full-text available via subscription   (Followers: 2)
Computer Applications in Engineering Education     Hybrid Journal   (Followers: 7)
Computer Science and Engineering     Open Access   (Followers: 17)
Computers & Geosciences     Hybrid Journal   (Followers: 28)
Computers & Mathematics with Applications     Full-text available via subscription   (Followers: 5)
Computers and Electronics in Agriculture     Hybrid Journal   (Followers: 4)
Computers and Geotechnics     Hybrid Journal   (Followers: 10)
Computing and Visualization in Science     Hybrid Journal   (Followers: 5)
Computing in Science & Engineering     Full-text available via subscription   (Followers: 30)
Conciencia Tecnologica     Open Access  
Concurrent Engineering     Hybrid Journal   (Followers: 3)
Continuum Mechanics and Thermodynamics     Hybrid Journal   (Followers: 7)
Control and Dynamic Systems     Full-text available via subscription   (Followers: 9)
Control Engineering Practice     Hybrid Journal   (Followers: 42)
Control Theory and Informatics     Open Access   (Followers: 8)
Corrosion Science     Hybrid Journal   (Followers: 25)
CT&F Ciencia, Tecnologia y Futuro     Open Access   (Followers: 1)
CTheory     Open Access  

        1 2 3 4 5 6 7 | Last

Journal Cover COMBINATORICA
  [SJR: 1.296]   [H-I: 38]   [0 followers]  Follow
    
   Hybrid Journal Hybrid journal (It can contain Open Access articles)
   ISSN (Print) 1439-6912 - ISSN (Online) 0209-9683
   Published by Springer-Verlag Homepage  [2352 journals]
  • Fractional covers and matchings in families of weighted d -intervals
    • Authors: Ron Aharoni; Tomáš Kaiser; Shira Zerbib
      Pages: 555 - 572
      Abstract: A d-interval is a union of at most d disjoint closed intervals on a fixed line. Tardos [14] and the second author [11] used topological tools to bound the transversal number τ of a family H of d-intervals in terms of d and the matching number ν of H. We investigate the weighted and fractional versions of this problem and prove upper bounds that are tight up to constant factors. We apply both a topological method and an approach of Alon [1]. For the use of the latter, we prove a weighted version of Turán’s theorem. We also provide proofs of the upper bounds of [11] that are more direct than the original proofs.
      PubDate: 2017-08-01
      DOI: 10.1007/s00493-016-3174-7
      Issue No: Vol. 37, No. 4 (2017)
       
  • Powers of Hamilton cycles in pseudorandom graphs
    • Authors: Peter Allen; Julia Böttcher; Hiệp Hàn; Yoshiharu Kohayakawa; Yury Person
      Pages: 573 - 616
      Abstract: We study the appearance of powers of Hamilton cycles in pseudorandom graphs, using the following comparatively weak pseudorandomness notion. A graph G is (ε,p,k,ℓ)-pseudorandom if for all disjoint X and Y ⊂ V(G) with X ≥εp k n and Y ≥εp ℓ n we have e(X,Y)=(1±ε)p X Y . We prove that for all β>0 there is an ε>0 such that an (ε,p,1,2)-pseudorandom graph on n vertices with minimum degree at least βpn contains the square of a Hamilton cycle. In particular, this implies that (n,d,λ)-graphs with λ≪d 5/2 n -3/2 contain the square of a Hamilton cycle, and thus a triangle factor if n is a multiple of 3. This improves on a result of Krivelevich, Sudakov and Szabó [27]. We also extend our result to higher powers of Hamilton cycles and establish corresponding counting versions.
      PubDate: 2017-08-01
      DOI: 10.1007/s00493-015-3228-2
      Issue No: Vol. 37, No. 4 (2017)
       
  • The typical structure of graphs with no large cliques
    • Authors: József Balogh; Neal Bushaw; Maurício Collares; Hong Liu; Robert Morris; Maryam Sharifzadeh
      Pages: 617 - 632
      Abstract: In 1987, Kolaitis, Prömel and Rothschild proved that, for every fixed r∈ℕ, almost every n-vertex K r+1-free graph is r-partite. In this paper we extend this result to all functions r = r(n) with r ⩽ (logn)1/4. The proof combines a new (close to sharp) supersaturation version of the Erdős-Simonovits stability theorem, the hypergraph container method, and a counting technique developed by Balogh, Bollobás and Simonovits.
      PubDate: 2017-08-01
      DOI: 10.1007/s00493-015-3290-9
      Issue No: Vol. 37, No. 4 (2017)
       
  • Computing the partition function for graph homomorphisms
    • Authors: Alexander Barvinok; Pablo Soberón
      Pages: 633 - 650
      Abstract: We introduce the partition function of edge-colored graph homomorphisms, of which the usual partition function of graph homomorphisms is a specialization, and present an efficient algorithm to approximate it in a certain domain. Corollaries include effcient algorithms for computing weighted sums approximating the number of k-colorings and the number of independent sets in a graph, as well as an effcient procedure to distinguish pairs of edge-colored graphs with many color-preserving homomorphisms G → H from pairs of graphs that need to be substantially modified to acquire a color-preserving homomorphism G → H.
      PubDate: 2017-08-01
      DOI: 10.1007/s00493-016-3357-2
      Issue No: Vol. 37, No. 4 (2017)
       
  • Regular families of forests, antichains and duality pairs of relational
           structures
    • Authors: Péter L. Erdős; Dömötör Pálvölgyi; Claude Tardif; Gábor Tardos
      Pages: 651 - 672
      Abstract: Homomorphism duality pairs play a crucial role in the theory of relational structures and in the Constraint Satisfaction Problem. The case where both classes are finite is fully characterized. The case when both sides are infinite seems to be very complex. It is also known that no finite-infinite duality pair is possible if we make the additional restriction that both classes are antichains. In this paper we characterize the infinite-finite antichain dualities and infinite-finite dualities with trees or forests on the left hand side. This work builds on our earlier papers [6] that gave several examples of infinite-finite antichain duality pairs of directed graphs and [7] giving a complete characterization for caterpillar dualities.
      PubDate: 2017-08-01
      DOI: 10.1007/s00493-015-3003-4
      Issue No: Vol. 37, No. 4 (2017)
       
  • Generalising Fisher’s inequality to coverings and packings
    • Authors: Daniel Horsley
      Pages: 673 - 696
      Abstract: In 1940 Fisher famously showed that if there exists a non-trivial (v,k,λ)-design, then λ(v-1)⩾k(k-1). Subsequently Bose gave an elegant alternative proof of Fisher’s result. Here, we show that the idea behind Bose’s proof can be generalised to obtain new bounds on the number of blocks in (v,k,λ)-coverings and -packings with λ(v-1)<k(k-1).
      PubDate: 2017-08-01
      DOI: 10.1007/s00493-016-3326-9
      Issue No: Vol. 37, No. 4 (2017)
       
  • Compatible Hamilton cycles in Dirac graphs
    • Authors: Michael Krivelevich; Choongbum Lee; Benny Sudakov
      Pages: 697 - 732
      Abstract: A graph is Hamiltonian if it contains a cycle passing through every vertex exactly once. A celebrated theorem of Dirac from 1952 asserts that every graph on n≥3 vertices with minimum degree at least n/2 is Hamiltonian. We refer to such graphs as Dirac graphs. In this paper we obtain the following strengthening of this result. Given a graph G=(V,E), an incompatibility system F over G is a family F = {F v } v∈V such that for every v∈V, the set F v is a family of unordered pairs F v ⊆ {{e,e′}}: e ≠ e′ ∈ E,e ∩ e′ = {v}}. An incompatibility system is Δ-bounded if for every vertex v and an edge e incident to v, there are at most Δ pairs in F v containing e. We say that a cycle C in G is compatible with F if every pair of incident edges e,e′ of C satisfies {e,e′}∉F v , where v=e ∩ e′. This notion is partly motivated by a concept of transition systems defined by Kotzig in 1968, and can be viewed as a quantitative measure of robustness of graph properties. We prove that there is a constant μ>0 such that for every μn-bounded incompatibility system F over a Dirac graph G, there exists a Hamilton cycle compatible with F. This settles in a very strong form a conjecture of Häggkvist from 1988.
      PubDate: 2017-08-01
      DOI: 10.1007/s00493-016-3328-7
      Issue No: Vol. 37, No. 4 (2017)
       
  • Lifts, derandomization, and diameters of Schreier graphs of Mealy automata
    • Authors: Anton Malyshev; Igor Pak
      Pages: 733 - 765
      Abstract: It is known that random 2-lifts of graphs give rise to expander graphs. We present a new conjectured derandomization of this construction based on certain Mealy automata. We verify that these graphs have polylogarithmic diameter, and present a class of automata for which the same is true. However, we also show that some automata in this class do not give rise to expander graphs.
      PubDate: 2017-08-01
      DOI: 10.1007/s00493-016-3306-0
      Issue No: Vol. 37, No. 4 (2017)
       
  • An exponential-type upper bound for Folkman numbers
    • Authors: Vojtěch Rödl; Andrzej Ruciński; Mathias Schacht
      Pages: 767 - 784
      Abstract: For given integers k and r, the Folkman number f(k;r) is the smallest number of vertices in a graph G which contains no clique on k+1 vertices, yet for every partition of its edges into r parts, some part contains a clique of order k. The existence (finiteness) of Folkman numbers was established by Folkman (1970) for r=2 and by Nešetřil and Rödl (1976) for arbitrary r, but these proofs led to very weak upper bounds on f(k;r). Recently, Conlon and Gowers and independently the authors obtained a doubly exponential bound on f(k;2). Here, we establish a further improvement by showing an upper bound on f(k;r) which is exponential in a polynomial of k and r. This is comparable to the known lower bound 2 Ω(rk). Our proof relies on a recent result of Saxton and Thomason (or, alternatively, on a recent result of Balogh, Morris, and Samotij) from which we deduce a quantitative version of Ramsey’s theorem in random graphs.
      PubDate: 2017-08-01
      DOI: 10.1007/s00493-015-3298-1
      Issue No: Vol. 37, No. 4 (2017)
       
  • Infinitely connected subgraphs in graphs of uncountable chromatic number
    • Authors: Carsten Thomassen
      Pages: 785 - 793
      Abstract: Erdős and Hajnal conjectured in 1966 that every graph of uncountable chromatic number contains a subgraph of infinite connectivity. We prove that every graph of uncountable chromatic number has a subgraph which has uncountable chromatic number and infinite edge-connectivity. We also prove that, if each orientation of a graph G has a vertex of infinite outdegree, then G contains an uncountable subgraph of infinite edge-connectivity.
      PubDate: 2017-08-01
      DOI: 10.1007/s00493-016-3436-4
      Issue No: Vol. 37, No. 4 (2017)
       
  • Minimal normal graph covers
    • Authors: David Gajser; Bojan Mohar
      Abstract: A graph is normal if it admits a clique cover C and a stable set cover S such that each clique in C and each stable set in S have a vertex in common. The pair (C,S) is a normal cover of the graph. We present the following extremal property of normal covers. For positive integers c, s, if a graph with n vertices admits a normal cover with cliques of sizes at most c and stable sets of sizes at most s, then c+s≥log2(n). For infinitely many n, we also give a construction of a graph with n vertices that admits a normal cover with cliques and stable sets of sizes less than 0.87log2(n). Furthermore, we show that for all n, there exists a normal graph with n vertices, clique number Θ(log2(n)) and independence number Θ(log2(n)). When c or s are very small, we can describe all normal graphs with the largest possible number of vertices that allow a normal cover with cliques of sizes at most c and stable sets of sizes at most s. However, such extremal graphs remain elusive even for moderately small values of c and s.
      PubDate: 2017-08-14
      DOI: 10.1007/s00493-017-3559-2
       
  • Edge lower bounds for list critical graphs, via discharging
    • Authors: Daniel W. Cranston; Landon Rabern
      Abstract: A graph G is k-critical if G is not (k − 1)-colorable, but every proper subgraph of G is (k − 1)-colorable. A graph G is k-choosable if G has an L-coloring from every list assignment L with L(v) =k for all v, and a graph G is k-list-critical if G is not (k−1)-choosable, but every proper subgraph of G is (k−1)-choosable. The problem of determining the minimum number of edges in a k-critical graph with n vertices has been widely studied, starting with work of Gallai and culminating with the seminal results of Kostochka and Yancey, who essentially solved the problem. In this paper, we improve the best known lower bound on the number of edges in a k-list-critical graph. In fact, our result on k-list-critical graphs is derived from a lower bound on the number of edges in a graph with Alon–Tarsi number at least k. Our proof uses the discharging method, which makes it simpler and more modular than previous work in this area.
      PubDate: 2017-08-14
      DOI: 10.1007/s00493-016-3584-6
       
  • Count matroids of group-labeled graphs
    • Authors: Rintaro Ikeshita; Shin-ichi Tanigawa
      Abstract: A graph G = (V, E) is called (k, ℓ)-sparse if F ≤ k V (F) − ℓ for any nonempty F ⊆ E, where V (F) denotes the set of vertices incident to F. It is known that the family of the edge sets of (k, ℓ)-sparse subgraphs forms the family of independent sets of a matroid, called the (k, ℓ)-count matroid of G. In this paper we shall investigate lifts of the (k, ℓ)- count matroids by using group labelings on the edge set. By introducing a new notion called near-balancedness, we shall identify a new class of matroids whose independence condition is described as a count condition of the form F ≤ k V (F) −ℓ+α ψ (F) for some function α ψ determined by a given group labeling ψ on E.
      PubDate: 2017-08-14
      DOI: 10.1007/s00493-016-3469-8
       
  • Essential dimension and the flats spanned by a point set
    • Authors: Ben Lund
      Abstract: Let P be a finite set of points in ℝ d or ℂ d .We answer a question of Purdy on the conditions under which the number of hyperplanes spanned by P is at least the number of (d−2)-flats spanned by P. In answering this question, we define a new measure of the degeneracy of a point set with respect to affine subspaces, termed the essential dimension. We use the essential dimension to give an asymptotic expression for the number of k-flats spanned by P, for 1≤k≤d−1.
      PubDate: 2017-08-14
      DOI: 10.1007/s00493-016-3602-8
       
  • List supermodular coloring
    • Authors: Satoru Iwata; Yu Yokoi
      Abstract: In 1995, Galvin provided an elegant proof for the list edge coloring conjecture for bipartite graphs, utilizing the stable matching theorem of Gale and Shapley. In this paper, we generalize Galvin’s result to the setting of supermodular coloring, introduced by Schrijver, with the aid of the monochromatic path theorem of Sands, Sauer andWoodrow. Our result derives a list coloring version of Gupta’s theorem, which can also be proven directly from Galvin’s theorem.
      PubDate: 2017-08-14
      DOI: 10.1007/s00493-017-3670-4
       
  • Treewidth of grid subsets
    • Authors: Eli Berger; Zdenĕk Dvořák; Sergey Norin
      Abstract: Let Q n be the 3-dimensional n×n×n grid with all non-decreasing diagonals (including the facial ones) in its constituent unit cubes. Suppose that a set S ⊆ V (Q n ) separates the left side of the grid from the right side. We show that S induces a subgraph of tree-width at least \(\frac{n}{{\sqrt {18} }} = - 1\) . We use a generalization of this claim to prove that the vertex set of Q n cannot be partitioned to two parts, each of them inducing a subgraph of bounded tree-width.
      PubDate: 2017-08-14
      DOI: 10.1007/s00493-017-3548-5
       
  • Chromatic number of ordered graphs with forbidden ordered subgraphs
    • Authors: Maria Axenovich; Jonathan Rollin; Torsten Ueckerdt
      Abstract: It is well-known that the graphs not containing a given graph H as a subgraph have bounded chromatic number if and only if H is acyclic. Here we consider ordered graphs, i.e., graphs with a linear ordering ≺ on their vertex set, and the function $${f_ \prec }\left( H \right) = \sup \left\{ {\chi \left( G \right) G \in For{b_ \prec }\left( H \right)} \right\},$$ where Forb≺(H) denotes the set of all ordered graphs that do not contain a copy of H. If H contains a cycle, then as in the case of unordered graphs, f ≺(H)=∞. However, in contrast to the unordered graphs, we describe an infinite family of ordered forests H with f ≺(H) =∞. An ordered graph is crossing if there are two edges uv and u′v′ with u ≺ u′ ≺ v ≺ v′. For connected crossing ordered graphs H we reduce the problem of determining whether f ≺(H) ≠∞ to a family of so-called monotonically alternating trees. For non-crossing H we prove that f ≺(H) ≠∞ if and only if H is acyclic and does not contain a copy of any of the five special ordered forests on four or five vertices, which we call bonnets. For such forests H, we show that f ≺(H)⩽2 V(H) and that f ≺(H)⩽2 V (H) −3 if H is connected.
      PubDate: 2017-08-14
      DOI: 10.1007/s00493-017-3593-0
       
  • Topology of complexes of edge covering partite graphs and hypergraphs
    • Authors: Victor A. Vassiliev
      Abstract: We describe the homotopy types of complexes of partite graphs and hypergraphs with a fixed set of vertices covered by their edges.
      PubDate: 2017-08-14
      DOI: 10.1007/s00493-017-3508-0
       
  • Sparsity and dimension
    • Authors: Gwenaël Joret; Piotr Micek; Veit Wiechert
      Abstract: We prove that posets of bounded height whose cover graphs belong to a fixed class with bounded expansion have bounded dimension. Bounded expansion, introduced by Nešetřil and Ossona de Mendez as a model for sparsity in graphs, is a property that is naturally satisfied by a wide range of graph classes, from graph structure theory (graphs excluding a minor or a topological minor) to graph drawing (e.g. graphs with bounded book thickness). Therefore, our theorem generalizes a number of results including the most recent one for posets of bounded height with cover graphs excluding a fixed graph as a topological minor. We also show that the result is in a sense best possible, as it does not extend to nowhere dense classes; in fact, it already fails for cover graphs with locally bounded treewidth.
      PubDate: 2017-08-14
      DOI: 10.1007/s00493-017-3638-4
       
  • A proof of the block model threshold conjecture
    • Authors: Elchanan Mossel; Joe Neeman; Allan Sly
      Abstract: We study a random graph model called the “stochastic block model” in statistics and the “planted partition model” in theoretical computer science. In its simplest form, this is a random graph with two equal-sized classes of vertices, with a within-class edge probability of q and a between-class edge probability of q′. A striking conjecture of Decelle, Krzkala, Moore and Zdeborová [9], based on deep, non-rigorous ideas from statistical physics, gave a precise prediction for the algorithmic threshold of clustering in the sparse planted partition model. In particular, if q=a/n and q′=b/n, s=(a−b)/2 and d=(a+b)/2, then Decelle et al. conjectured that it is possible to efficiently cluster in a way correlated with the true partition if s 2>d and impossible if s 2<d. By comparison, until recently the best-known rigorous result showed that clustering is possible if s 2>Cdlnd for sufficiently large C. In a previous work, we proved that indeed it is information theoretically impossible to cluster if s 2 ≤ d and moreover that it is information theoretically impossible to even estimate the model parameters from the graph when s 2 < d. Here we prove the rest of the conjecture by providing an efficient algorithm for clustering in a way that is correlated with the true partition when s 2>d. A different independent proof of the same result was recently obtained by Massoulié [20].
      PubDate: 2017-08-14
      DOI: 10.1007/s00493-016-3238-8
       
 
 
JournalTOCs
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Email: journaltocs@hw.ac.uk
Tel: +00 44 (0)131 4513762
Fax: +00 44 (0)131 4513327
 
About JournalTOCs
API
Help
News (blog, publications)
JournalTOCs on Twitter   JournalTOCs on Facebook

JournalTOCs © 2009-2016