for Journals by Title or ISSN
for Articles by Keywords
  Subjects -> COMPUTER SCIENCE (Total: 1991 journals)
    - ANIMATION AND SIMULATION (29 journals)
    - AUTOMATION AND ROBOTICS (98 journals)
    - COMPUTER ARCHITECTURE (9 journals)
    - COMPUTER ENGINEERING (9 journals)
    - COMPUTER GAMES (16 journals)
    - COMPUTER PROGRAMMING (24 journals)
    - COMPUTER SCIENCE (1157 journals)
    - COMPUTER SECURITY (45 journals)
    - DATA BASE MANAGEMENT (13 journals)
    - DATA MINING (32 journals)
    - E-BUSINESS (22 journals)
    - E-LEARNING (29 journals)
    - IMAGE AND VIDEO PROCESSING (39 journals)
    - INFORMATION SYSTEMS (105 journals)
    - INTERNET (92 journals)
    - SOCIAL WEB (50 journals)
    - SOFTWARE (34 journals)
    - THEORY OF COMPUTING (8 journals)

COMPUTER SCIENCE (1157 journals)                  1 2 3 4 5 6 | Last

Showing 1 - 200 of 872 Journals sorted alphabetically
3D Printing and Additive Manufacturing     Full-text available via subscription   (Followers: 13)
Abakós     Open Access   (Followers: 4)
ACM Computing Surveys     Hybrid Journal   (Followers: 22)
ACM Journal on Computing and Cultural Heritage     Hybrid Journal   (Followers: 9)
ACM Journal on Emerging Technologies in Computing Systems     Hybrid Journal   (Followers: 13)
ACM Transactions on Accessible Computing (TACCESS)     Hybrid Journal   (Followers: 3)
ACM Transactions on Algorithms (TALG)     Hybrid Journal   (Followers: 16)
ACM Transactions on Applied Perception (TAP)     Hybrid Journal   (Followers: 6)
ACM Transactions on Architecture and Code Optimization (TACO)     Hybrid Journal   (Followers: 9)
ACM Transactions on Autonomous and Adaptive Systems (TAAS)     Hybrid Journal   (Followers: 7)
ACM Transactions on Computation Theory (TOCT)     Hybrid Journal   (Followers: 12)
ACM Transactions on Computational Logic (TOCL)     Hybrid Journal   (Followers: 4)
ACM Transactions on Computer Systems (TOCS)     Hybrid Journal   (Followers: 18)
ACM Transactions on Computer-Human Interaction     Hybrid Journal   (Followers: 13)
ACM Transactions on Computing Education (TOCE)     Hybrid Journal   (Followers: 4)
ACM Transactions on Design Automation of Electronic Systems (TODAES)     Hybrid Journal   (Followers: 1)
ACM Transactions on Economics and Computation     Hybrid Journal  
ACM Transactions on Embedded Computing Systems (TECS)     Hybrid Journal   (Followers: 4)
ACM Transactions on Information Systems (TOIS)     Hybrid Journal   (Followers: 20)
ACM Transactions on Intelligent Systems and Technology (TIST)     Hybrid Journal   (Followers: 8)
ACM Transactions on Interactive Intelligent Systems (TiiS)     Hybrid Journal   (Followers: 3)
ACM Transactions on Multimedia Computing, Communications, and Applications (TOMCCAP)     Hybrid Journal   (Followers: 10)
ACM Transactions on Reconfigurable Technology and Systems (TRETS)     Hybrid Journal   (Followers: 7)
ACM Transactions on Sensor Networks (TOSN)     Hybrid Journal   (Followers: 8)
ACM Transactions on Speech and Language Processing (TSLP)     Hybrid Journal   (Followers: 11)
ACM Transactions on Storage     Hybrid Journal  
ACS Applied Materials & Interfaces     Full-text available via subscription   (Followers: 25)
Acta Automatica Sinica     Full-text available via subscription   (Followers: 3)
Acta Universitatis Cibiniensis. Technical Series     Open Access  
Ad Hoc Networks     Hybrid Journal   (Followers: 11)
Adaptive Behavior     Hybrid Journal   (Followers: 11)
Advanced Engineering Materials     Hybrid Journal   (Followers: 26)
Advanced Science Letters     Full-text available via subscription   (Followers: 8)
Advances in Adaptive Data Analysis     Hybrid Journal   (Followers: 8)
Advances in Artificial Intelligence     Open Access   (Followers: 16)
Advances in Calculus of Variations     Hybrid Journal   (Followers: 2)
Advances in Catalysis     Full-text available via subscription   (Followers: 5)
Advances in Computational Mathematics     Hybrid Journal   (Followers: 15)
Advances in Computer Science : an International Journal     Open Access   (Followers: 14)
Advances in Computing     Open Access   (Followers: 2)
Advances in Data Analysis and Classification     Hybrid Journal   (Followers: 51)
Advances in Engineering Software     Hybrid Journal   (Followers: 25)
Advances in Geosciences (ADGEO)     Open Access   (Followers: 10)
Advances in Human Factors/Ergonomics     Full-text available via subscription   (Followers: 26)
Advances in Human-Computer Interaction     Open Access   (Followers: 20)
Advances in Materials Sciences     Open Access   (Followers: 16)
Advances in Operations Research     Open Access   (Followers: 11)
Advances in Parallel Computing     Full-text available via subscription   (Followers: 7)
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)
Advances in Technology Innovation     Open Access   (Followers: 2)
AEU - International Journal of Electronics and Communications     Hybrid Journal   (Followers: 8)
African Journal of Information and Communication     Open Access   (Followers: 8)
African Journal of Mathematics and Computer Science Research     Open Access   (Followers: 4)
Air, Soil & Water Research     Open Access   (Followers: 9)
AIS Transactions on Human-Computer Interaction     Open Access   (Followers: 6)
Algebras and Representation Theory     Hybrid Journal   (Followers: 1)
Algorithms     Open Access   (Followers: 11)
American Journal of Computational and Applied Mathematics     Open Access   (Followers: 4)
American Journal of Computational Mathematics     Open Access   (Followers: 4)
American Journal of Information Systems     Open Access   (Followers: 7)
American Journal of Sensor Technology     Open Access   (Followers: 4)
Anais da Academia Brasileira de Ciências     Open Access   (Followers: 2)
Analog Integrated Circuits and Signal Processing     Hybrid Journal   (Followers: 7)
Analysis in Theory and Applications     Hybrid Journal   (Followers: 1)
Animation Practice, Process & Production     Hybrid Journal   (Followers: 5)
Annals of Combinatorics     Hybrid Journal   (Followers: 3)
Annals of Data Science     Hybrid Journal   (Followers: 11)
Annals of Mathematics and Artificial Intelligence     Hybrid Journal   (Followers: 7)
Annals of Pure and Applied Logic     Open Access   (Followers: 2)
Annals of Software Engineering     Hybrid Journal   (Followers: 12)
Annual Reviews in Control     Hybrid Journal   (Followers: 6)
Anuario Americanista Europeo     Open Access  
Applicable Algebra in Engineering, Communication and Computing     Hybrid Journal   (Followers: 2)
Applied and Computational Harmonic Analysis     Full-text available via subscription   (Followers: 2)
Applied Artificial Intelligence: An International Journal     Hybrid Journal   (Followers: 14)
Applied Categorical Structures     Hybrid Journal   (Followers: 2)
Applied Clinical Informatics     Hybrid Journal   (Followers: 2)
Applied Computational Intelligence and Soft Computing     Open Access   (Followers: 12)
Applied Computer Systems     Open Access   (Followers: 1)
Applied Informatics     Open Access  
Applied Mathematics and Computation     Hybrid Journal   (Followers: 33)
Applied Medical Informatics     Open Access   (Followers: 11)
Applied Numerical Mathematics     Hybrid Journal   (Followers: 5)
Applied Soft Computing     Hybrid Journal   (Followers: 16)
Applied Spatial Analysis and Policy     Hybrid Journal   (Followers: 4)
Architectural Theory Review     Hybrid Journal   (Followers: 3)
Archive of Applied Mechanics     Hybrid Journal   (Followers: 5)
Archive of Numerical Software     Open Access  
Archives and Museum Informatics     Hybrid Journal   (Followers: 132)
Archives of Computational Methods in Engineering     Hybrid Journal   (Followers: 4)
Artifact     Hybrid Journal   (Followers: 2)
Artificial Life     Hybrid Journal   (Followers: 6)
Asia Pacific Journal on Computational Engineering     Open Access  
Asia-Pacific Journal of Information Technology and Multimedia     Open Access   (Followers: 1)
Asian Journal of Computer Science and Information Technology     Open Access  
Asian Journal of Control     Hybrid Journal  
Assembly Automation     Hybrid Journal   (Followers: 2)
at - Automatisierungstechnik     Hybrid Journal   (Followers: 1)
Australian Educational Computing     Open Access   (Followers: 1)
Automatic Control and Computer Sciences     Hybrid Journal   (Followers: 4)
Automatic Documentation and Mathematical Linguistics     Hybrid Journal   (Followers: 5)
Automatica     Hybrid Journal   (Followers: 11)
Automation in Construction     Hybrid Journal   (Followers: 6)
Autonomous Mental Development, IEEE Transactions on     Hybrid Journal   (Followers: 8)
Basin Research     Hybrid Journal   (Followers: 5)
Behaviour & Information Technology     Hybrid Journal   (Followers: 52)
Bioinformatics     Hybrid Journal   (Followers: 306)
Biomedical Engineering     Hybrid Journal   (Followers: 16)
Biomedical Engineering and Computational Biology     Open Access   (Followers: 13)
Biomedical Engineering, IEEE Reviews in     Full-text available via subscription   (Followers: 17)
Biomedical Engineering, IEEE Transactions on     Hybrid Journal   (Followers: 32)
Briefings in Bioinformatics     Hybrid Journal   (Followers: 44)
British Journal of Educational Technology     Hybrid Journal   (Followers: 129)
Broadcasting, IEEE Transactions on     Hybrid Journal   (Followers: 10)
c't Magazin fuer Computertechnik     Full-text available via subscription   (Followers: 2)
CALCOLO     Hybrid Journal  
Calphad     Hybrid Journal  
Canadian Journal of Electrical and Computer Engineering     Full-text available via subscription   (Followers: 14)
Catalysis in Industry     Hybrid Journal   (Followers: 1)
CEAS Space Journal     Hybrid Journal  
Cell Communication and Signaling     Open Access   (Followers: 1)
Central European Journal of Computer Science     Hybrid Journal   (Followers: 5)
CERN IdeaSquare Journal of Experimental Innovation     Open Access  
Chaos, Solitons & Fractals     Hybrid Journal   (Followers: 3)
Chemometrics and Intelligent Laboratory Systems     Hybrid Journal   (Followers: 15)
ChemSusChem     Hybrid Journal   (Followers: 7)
China Communications     Full-text available via subscription   (Followers: 7)
Chinese Journal of Catalysis     Full-text available via subscription   (Followers: 2)
CIN Computers Informatics Nursing     Full-text available via subscription   (Followers: 12)
Circuits and Systems     Open Access   (Followers: 16)
Clean Air Journal     Full-text available via subscription   (Followers: 2)
CLEI Electronic Journal     Open Access  
Clin-Alert     Hybrid Journal   (Followers: 1)
Cluster Computing     Hybrid Journal   (Followers: 1)
Cognitive Computation     Hybrid Journal   (Followers: 4)
COMBINATORICA     Hybrid Journal  
Combustion Theory and Modelling     Hybrid Journal   (Followers: 13)
Communication Methods and Measures     Hybrid Journal   (Followers: 12)
Communication Theory     Hybrid Journal   (Followers: 20)
Communications Engineer     Hybrid Journal   (Followers: 1)
Communications in Algebra     Hybrid Journal   (Followers: 3)
Communications in Partial Differential Equations     Hybrid Journal   (Followers: 3)
Communications of the ACM     Full-text available via subscription   (Followers: 53)
Communications of the Association for Information Systems     Open Access   (Followers: 18)
COMPEL: The International Journal for Computation and Mathematics in Electrical and Electronic Engineering     Hybrid Journal   (Followers: 3)
Complex & Intelligent Systems     Open Access  
Complex Adaptive Systems Modeling     Open Access  
Complex Analysis and Operator Theory     Hybrid Journal   (Followers: 2)
Complexity     Hybrid Journal   (Followers: 6)
Complexus     Full-text available via subscription  
Composite Materials Series     Full-text available via subscription   (Followers: 9)
Computación y Sistemas     Open Access  
Computation     Open Access  
Computational and Applied Mathematics     Hybrid Journal   (Followers: 2)
Computational and Mathematical Methods in Medicine     Open Access   (Followers: 2)
Computational and Mathematical Organization Theory     Hybrid Journal   (Followers: 2)
Computational and Structural Biotechnology Journal     Open Access   (Followers: 2)
Computational and Theoretical Chemistry     Hybrid Journal   (Followers: 9)
Computational Astrophysics and Cosmology     Open Access   (Followers: 1)
Computational Biology and Chemistry     Hybrid Journal   (Followers: 12)
Computational Chemistry     Open Access   (Followers: 2)
Computational Cognitive Science     Open Access   (Followers: 2)
Computational Complexity     Hybrid Journal   (Followers: 4)
Computational Condensed Matter     Open Access  
Computational Ecology and Software     Open Access   (Followers: 9)
Computational Economics     Hybrid Journal   (Followers: 9)
Computational Geosciences     Hybrid Journal   (Followers: 14)
Computational Linguistics     Open Access   (Followers: 23)
Computational Management Science     Hybrid Journal  
Computational Mathematics and Modeling     Hybrid Journal   (Followers: 8)
Computational Mechanics     Hybrid Journal   (Followers: 4)
Computational Methods and Function Theory     Hybrid Journal  
Computational Molecular Bioscience     Open Access   (Followers: 2)
Computational Optimization and Applications     Hybrid Journal   (Followers: 7)
Computational Particle Mechanics     Hybrid Journal   (Followers: 1)
Computational Research     Open Access   (Followers: 1)
Computational Science and Discovery     Full-text available via subscription   (Followers: 2)
Computational Science and Techniques     Open Access  
Computational Statistics     Hybrid Journal   (Followers: 13)
Computational Statistics & Data Analysis     Hybrid Journal   (Followers: 31)
Computer     Full-text available via subscription   (Followers: 87)
Computer Aided Surgery     Hybrid Journal   (Followers: 3)
Computer Applications in Engineering Education     Hybrid Journal   (Followers: 7)
Computer Communications     Hybrid Journal   (Followers: 10)
Computer Engineering and Applications Journal     Open Access   (Followers: 5)
Computer Journal     Hybrid Journal   (Followers: 7)
Computer Methods in Applied Mechanics and Engineering     Hybrid Journal   (Followers: 22)
Computer Methods in Biomechanics and Biomedical Engineering     Hybrid Journal   (Followers: 10)
Computer Methods in the Geosciences     Full-text available via subscription   (Followers: 1)
Computer Music Journal     Hybrid Journal   (Followers: 16)
Computer Physics Communications     Hybrid Journal   (Followers: 6)
Computer Science - Research and Development     Hybrid Journal   (Followers: 7)
Computer Science and Engineering     Open Access   (Followers: 17)
Computer Science and Information Technology     Open Access   (Followers: 11)
Computer Science Education     Hybrid Journal   (Followers: 12)
Computer Science Journal     Open Access   (Followers: 20)
Computer Science Master Research     Open Access   (Followers: 10)
Computer Science Review     Hybrid Journal   (Followers: 10)

        1 2 3 4 5 6 | Last

  [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
    • 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
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Tel: +00 44 (0)131 4513762
Fax: +00 44 (0)131 4513327
Home (Search)
Subjects A-Z
Publishers A-Z
Your IP address:
About JournalTOCs
News (blog, publications)
JournalTOCs on Twitter   JournalTOCs on Facebook

JournalTOCs © 2009-2016