1. On Forbidden Induced Subgraphs for Unit Disk Graphs
   2018/03/23 by Aistis Atminas, Viktor Zamaraev · 1 citation
   Computer Science · Engineering · Mathematics · #1-planar graph #Advanced Graph Theory Research #Bipartite graph #Chordal graph #Cograph #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Discrete mathematics #Graph #Indifference graph #Line graph #Mathematics #Pathwidth #Unit (ring theory) #Unit disk #Unit disk graph #graph theory and CDMA systems
2. 2-subcoloring is NP-complete for planar comparability graphs
   2017/08/31 by Pascal Ochem · 1 citation
   Computer Science · Engineering · Mathematics · #1-planar graph #Advanced Graph Theory Research #Chordal graph #Clique-sum #Cograph #Combinatorics #Comparability #Complexity and Algorithms in Graphs #Discrete mathematics #Graph #Indifference graph #Line graph #Mathematics #Maximal independent set #Outerplanar graph #Partition (number theory) #Pathwidth #Planar graph #Vertex (graph theory) #graph theory and CDMA systems
3. Bipartite minors
   2015/08/21 by Maria Chudnovsky, Gil Kalai, Eran Nevo +2 · 1 citation
   Computer Science · Engineering · Mathematics · #1-planar graph #Advanced Graph Theory Research #Bipartite graph #Characterization (materials science) #Chordal graph #Cograph #Combinatorics #Complete bipartite graph #Computational Geometry and Mesh Generation #Dense graph #Discrete mathematics #Graph #Law #Mathematics #Minor (academic) #Physics #Robertson–Seymour theorem #Structural Analysis and Optimization
4. Identification, location–domination and metric dimension on interval and permutation graphs. I. Bounds
   2015/07/31 by Florent Foucaud, George B. Mertzios, Reza Naserasr +2 · 1 citation
   Computer Science · Engineering · Mathematics · #1-planar graph #Advanced Graph Theory Research #Bipartite graph #Chordal graph #Cograph #Combinatorics #Discrete mathematics #Graph #Graph Labeling and Dimension Problems #Independent set #Indifference graph #Interval graph #Mathematics #Maximal independent set #Metric dimension #Permutation graph #cs.DM #graph theory and CDMA systems #math.CO
5. The (Weighted) Metric Dimension of Graphs: Hard and Easy Cases
   2012/01/01 by Leah Epstein, Asaf Levin, Gerhard J. Woeginger · 3 citations
   Computer Science · Mathematics · #Bipartite graph #Chordal graph #Cograph #Combinatorics #Complete bipartite graph #Discrete mathematics #Graph #Graph Labeling and Dimension Problems #Line graph #Mathematics #Metric dimension #Pathwidth #Time complexity #Vertex (graph theory)
6. Complexity and parameterized algorithms for Cograph Editing
   2011/12/21 by Yunlong Liu, Jianxin Wang, Jiong Guo +1 · 1 citation
   Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Algorithms and Data Compression #Cograph #Combinatorics #Computational complexity theory #Computer science #Graph #Line graph #Mathematics #Parameterized complexity #Pathwidth #Protein Degradation and Inhibitors #Set (abstract data type) #Theoretical computer science #Time complexity
7. Split decomposition and graph-labelled trees: Characterizations and fully dynamic algorithms for totally decomposable graphs
   2011/07/26 by Emeric Gioan, Christophe Paul · 2 citations
   Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Bijection #Block graph #Chordal graph #Cograph #Combinatorics #Discrete mathematics #Graph #Graph Labeling and Dimension Problems #Graph theory and applications #Indifference graph #Intersection graph #Line graph #Mathematics #Modular decomposition #Pathwidth #Split graph
8. Graphs and Cubes
   2011/01/01 by С. Г. Овчинников, Sergei Ovchinnikov · 1 citation
   Computer Science · Mathematics · #Advanced Graph Theory Research #Bipartite graph #Cograph #Combinatorics #Dimension (graph theory) #Discrete mathematics #Graph #Hypercube #Line graph #Mathematics #Pathwidth
9. Countable connected-homogeneous graphs
   2009/05/14 by Robert D. Gray, R. Gray, D. Macpherson +1 · 1 citation
   Mathematics · #1-planar graph #Advanced Operator Algebra Research #Advanced Topology and Set Theory #Bipartite graph #Cograph #Combinatorics #Countable set #Discrete mathematics #Disjoint sets #Edge-transitive graph #Graph #Graph automorphism #Limits and Structures in Graph Theory #Line graph #Mathematics #Vertex-transitive graph #Voltage graph
10. Density theorems for bipartite graphs and related Ramsey-type results
    2009/03/01 by Jacob Fox, Benny Sudakov · 4 citations
    Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Bipartite graph #Cograph #Combinatorics #Dense graph #Discrete mathematics #Extremal graph theory #Graph #Intersection graph #Limits and Structures in Graph Theory #Line graph #Mathematical proof #Mathematics #Pathwidth #Ramsey theory #Ramsey's theorem #Triangle-free graph #Voltage graph
11. Distance unimodular equivalence of graphs
    2008/05/12 by Yaoping Hou, Chingwah Woo, Ching-Wah Woo · 5 citations
    Computer Science · Engineering · Mathematics · #1-planar graph #Advanced Graph Theory Research #Chordal graph #Cograph #Combinatorics #Computer science #Discrete mathematics #Distance matrix #Equivalence (formal languages) #Graph #Graph theory and applications #Integer (computer science) #Mathematics #Multipartite #Unimodular matrix #graph theory and CDMA systems
12. A Simple Linear Time LexBFS Cograph Recognition Algorithm
    2008/01/01 by Anna Bretscher, Derek G. Corneil, Michel Habib +1 · 1 citation
    Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Algorithms and Data Compression #Lexicographical order #Algorithm #Simple (philosophy) #Mathematics #Cograph #Time complexity #Combinatorics #Graph #Modular design #Computer science #Theoretical computer science #Pathwidth #Line graph
13. A simple linear time algorithm for cograph recognition
    2004/10/30 by Michel Habib, Christophe Paul · 4 citations
    Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Algorithm #Chordal graph #Cograph #Combinatorics #Computer science #Discrete mathematics #Graph #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Mathematics #Partition (number theory) #Path (computing) #Permutation (music) #Permutation graph #Simple (philosophy) #Time complexity
14. A (sub)graph isomorphism algorithm for matching large graphs
    2004/08/16 by L.P. Cordella, Pasquale Foggia, Carlo Sansone +1 · 7 citations
    Computer Science · Mathematics · #Graph Theory and Algorithms #Data Management and Algorithms #Advanced Database Systems and Queries #Subgraph isomorphism problem #Graph isomorphism #Induced subgraph isomorphism problem #Computer science #Maximal independent set #Cograph #Algorithm #Isomorphism (crystallography) #Chordal graph #Matching (statistics) #Pathwidth #Indifference graph #Time complexity #Graph #Theoretical computer science #Mathematics #Line graph
15. Spectral Generalizations of Line Graphs: On Graphs with Least Eigenvalue -2
    2004/01/01 by Dragoš Cvetković, Peter Rowlinson, Slobodan Simić · 1 citation
    Computer Science · Materials Science · Mathematics · #1-planar graph #Algebraic number #Chordal graph #Cograph #Combinatorics #Computer science #Context (archaeology) #Discrete mathematics #Eigenvalues and eigenvectors #Epistemology #Geography #Graph #Graph product #Graph theory and applications #Indifference graph #Line graph #Mathematics #Matrix Theory and Algorithms #Maximal independent set #Modular decomposition #Pathwidth #Physics #Property (philosophy) #Synthesis and properties of polymers
16. Cholesky Factorization of Matrices in Parallel and Ranking of Graphs
    2004/01/01 by Dariusz Dereniowski, Marek Kubale · 2 citations
    Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Algorithm #Bipartite graph #Cholesky decomposition #Chordal graph #Cograph #Combinatorics #Computer science #Discrete mathematics #Eigenvalues and eigenvectors #Factorization #Graph #Graph Labeling and Dimension Problems #Incomplete Cholesky factorization #Interconnection Networks and Systems #Mathematics #Vertex (graph theory)
17. Progress on perfect graphs
    2003/07/01 by Maria Chudnovsky, Neil Robertson, Paul Seymour +2 · 3 citations
    Computer Science · Mathematics · #Advanced Graph Theory Research #Cograph #Combinatorics #Conjecture #Discrete mathematics #Distance-hereditary graph #Graph #Graph Labeling and Dimension Problems #Graph power #Limits and Structures in Graph Theory #Line graph #Mathematics #Pathwidth #Perfect graph #Perfect graph theorem #Perfect power #Split graph #Strong perfect graph theorem #Trivially perfect graph
18. Splitting a graph into disjoint induced paths or cycles
    2003/02/04 by Hoàng-Oanh Le, Van Bang Le, Van Bang Lê +1 · 1 citation
    Computer Science · Mathematics · #Advanced Graph Theory Research #Block graph #Chordal graph #Cograph #Combinatorics #Computational Geometry and Mesh Generation #Data Visualization and Analytics #Discrete mathematics #Graph #Line graph #Mathematics #Partial k-tree #Pathwidth #Split graph #Treewidth
19. Graph Subcolorings: Complexity and Algorithms
    2003/01/01 by Jiřı́ Fiala, Klaus Jansen, Van Bang Lê +1 · 1 citation
    Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Combinatorics #Mathematics #Cograph #Discrete mathematics #Treewidth #Pathwidth #1-planar graph #Chordal graph #Split graph #Indifference graph #Planar graph #Clique-sum #Degree (music) #Partial k-tree #Bounded function #Graph #Line graph
20. Graph-Theoretic Concepts in Computer Science
    2003/01/01 by Hans L. Bodlaender · 1 citation
    Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Algorithms and Data Compression #Chordal graph #Clique-sum #Cograph #Combinatorics #DNA and Biological Computing #Discrete mathematics #Graph #Indifference graph #Line graph #Mathematics #Maximal independent set #Pathwidth #Planar graph #Split graph #Treewidth
21. Algorithms for maximum weight induced paths
    2002/02/01 by Fǎnicǎ Gavril, Fanica Gavril · 1 citation
    Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Bipartite graph #Bounded function #Chordal graph #Clique-sum #Cograph #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Graph #Independent set #Indifference graph #Interconnection Networks and Systems #Interval graph #Line graph #Mathematics #Pathwidth #Split graph #Time complexity
22. Algebraic Graph Theory
    2001/01/01 by Chris Godsil, Gordon Royle · 14 citations
    Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Block graph #Chordal graph #Cograph #Combinatorics #Comparability graph #Discrete mathematics #Finite Group Theory Research #Graph #Indifference graph #Limits and Structures in Graph Theory #Line graph #Mathematics #Modular decomposition #Pathwidth #Split graph #Symmetric graph #Voltage graph
23. Maximum Clique Transversals
    2001/01/01 by Maw‐Shang Chang, Maw-Shang Chang, Ton Kloks +1 · 4 citations
    Computer Science · Engineering · Mathematics · #1-planar graph #Advanced Graph Theory Research #Block graph #Chordal graph #Clique graph #Clique problem #Clique-sum #Cograph #Combinatorics #Discrete mathematics #Graph #Graph Labeling and Dimension Problems #Graph power #Independent set #Indifference graph #Interval graph #Line graph #Mathematics #Maximal independent set #Pathwidth #Split graph #Treewidth #Vertex (graph theory) #graph theory and CDMA systems
24. Linear Time Solvable Optimization Problems on Graphs of Bounded Clique-Width
    2000/03/04 by B. Courcelle, Johann A. Makowsky, J. A. Makowsky +2 · 9 citations
    Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Bounded function #Chordal graph #Clique #Cograph #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Enhanced Data Rates for GSM Evolution #Graph #Graph Labeling and Dimension Problems #Indifference graph #Line graph #Mathematics #Measure (data warehouse) #Pathwidth #Time complexity #Tree (set theory) #Treewidth
25. Graph classes between parity and distance-hereditary graphs
    1999/07/01 by Serafino Cicerone, Gabriele Di Stefano · 2 citations
    Computer Science · Mathematics · #Advanced Graph Theory Research #Chordal graph #Cograph #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Distance-hereditary graph #Graph #Graph Labeling and Dimension Problems #Graph isomorphism #Graph property #Induced subgraph isomorphism problem #Line graph #Mathematics #Modular decomposition #Pathwidth #Subgraph isomorphism problem #Voltage graph
26. Characterizations and algorithmic applications of chordal graph embeddings
    1997/11/01 by Andreas Parra, Petra Scheffler · 3 citations
    Computer Science · Mathematics · #Advanced Graph Theory Research #Chordal graph #Cograph #Combinatorics #Comparability graph #Complexity and Algorithms in Graphs #Discrete mathematics #Graph #Graph Labeling and Dimension Problems #Indifference graph #Interval graph #Line graph #Mathematics #Outerplanar graph #Pathwidth #Split graph #Treewidth
27. Clique Graphs of Chordal and Path Graphs
    1994/05/01 by Jayme L. Szwarcfiter, Claudson F. Bornstein · 1 citation
    Computer Science · Mathematics · #Advanced Graph Theory Research #Graph theory and applications #Complexity and Algorithms in Graphs #Chordal graph #Combinatorics #Split graph #Mathematics #Block graph #Treewidth #Indifference graph #Pathwidth #Clique-sum #Discrete mathematics #Interval graph #Cograph #Longest path problem #Graph #1-planar graph #Line graph
28. Extremal interval graphs
    1993/03/01 by Jürgen Eckhoff · 1 citation
    Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Graph theory and applications #Combinatorics #Mathematics #Indifference graph #Interval (graph theory) #Chordal graph #Split graph #Interval graph #Discrete mathematics #Clique number #Clique-sum #Clique #Cograph #Block graph #Pathwidth #Graph #1-planar graph #Line graph
29. Computing treewidth and minimum fill-in: All you need are the minimal separators
    1993/01/01 by Ton Kloks, T. Kloks, H. Bodlaender +5 · 1 citation
    Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Bipartite graph #Chordal graph #Clique-sum #Cograph #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Graph #Indifference graph #Interconnection Networks and Systems #Interval graph #Line graph #Mathematics #Partial k-tree #Pathwidth #Permutation graph #Split graph #Time complexity #Treewidth
30. A fast algorithm for coloring Meyniel graphs
    1990/12/01 by Alain Hertz, A Hertz · 1 citation
    Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Block graph #Chordal graph #Clique #Clique graph #Cograph #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Graph #Graph coloring #Graph power #Induced subgraph #Line graph #Mathematics #Optimization and Search Problems #Pathwidth #Perfect graph #Split graph #Vertex (graph theory)

more