- Circle graphs are quadratically χ‐bounded
2020/12/19 by James C. Davies, Rose McCarty · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Graph Labeling and Dimension Problems #Mathematics #Quadratic growth #Omega #Clique number #Combinatorics #Bounded function #Chromatic scale #Graph #Clique #Block graph #Discrete mathematics #Chordal graph #1-planar graph #Mathematical analysis
- Triangle-free intersection graphs of line segments with large chromatic number
2012/09/30 by Arkadiusz Pawlik, Jakub Kozik, Tomasz Krawczyk +4 · 1 citation
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Block graph #Bounded function #Chordal graph #Chromatic scale #Clique number #Computational Geometry and Mesh Generation #Conjecture #Graph #Intersection (aeronautics) #Intersection graph #cs.CG #cs.DM #math.CO #msc:05C15 #msc:05C62
- Integer realizations of disk and segment graphs
2012/09/29 by Colin McDiarmid, Tobias Müller · 2 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Block graph #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Digital Image Processing Techniques #Discrete mathematics #Graph #Line graph #Mathematics #Unit disk graph
- Split decomposition and graph-labelled trees: Characterizations and fully dynamic algorithms for totally decomposable graphs
2011/07/26 by Emeric Gioan, Christophe Paul · 1 citation
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
- Line graphs of multigraphs and Hamilton-connectedness of claw-free graphs
2010/11/12 by Zdeněk Ryjáček, Petr Vrána · 2 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Interconnection Networks and Systems #graph theory and CDMA systems #Multigraph #Combinatorics #Mathematics #Line graph #Social connectedness #Discrete mathematics #Cubic graph #Block graph #Quartic graph #Voltage graph #Graph #Pathwidth
- Clique graphs and overlapping communities
2010/09/03 by T S Evans, T. S. Evans · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Block graph #Clique #Clique graph #Clique percolation method #Clique-sum #Complexity and Algorithms in Graphs #Graph #Graph Labeling and Dimension Problems #Graph theory and applications #Simplex graph #Split graph #Vertex (graph theory) #cs.SI #physics.data-an #physics.soc-ph
- Line graphs of weighted networks for overlapping communities
2009/12/31 by T. S. Evans, Tim Evans, R. Lambiotte +1 · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Block graph #Combinatorics #Complex Network Analysis Techniques #Computer science #Graph #Graph partition #Graph theory and applications #Line graph #Mathematics #Partition (number theory) #Pathwidth #Theoretical computer science #Topological and Geometric Data Analysis #cs.DS #physics.data-an #physics.soc-ph
- The LBFS Structure and Recognition of Interval Graphs
2009/12/11 by Derek G. Corneil, Stephan Olariu, Lorna Stewart · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithms and Data Compression #Constraint Satisfaction and Optimization #Interval graph #Chordal graph #Combinatorics #Indifference graph #Pathwidth #Mathematics #Split graph #Intersection graph #Discrete mathematics #Block graph #Lexicographical order #Intersection (aeronautics) #Outerplanar graph #Trapezoid graph #Graph #Interval (graph theory) #Line graph #1-planar graph
- The Complexity of Bendless Three-Dimensional Orthogonal Graph Drawing
2007/09/30 by David Eppstein · 1 citation
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Block graph #Book embedding #Computational Geometry and Mesh Generation #Embedding #Graph #Graph embedding #Line graph #Outerplanar graph #Planar graph #Topological and Geometric Data Analysis #Topological graph theory #cs.CG #math.CO
- 1.5-Approximation for Treewidth of Graphs Excluding a Graph with One Crossing as a Minor
2002/01/01 by Erik D. Demaine, Mohammad Taghi Hajiaghayi, MohammadTaghi Hajiaghayi +1 · 3 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Block graph #Chordal graph #Clique-sum #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Discrete mathematics #Graph #Graph minor #Indifference graph #Line graph #Mathematics #Minor (academic) #Partial k-tree #Pathwidth #Planar graph #Tree-depth #Treewidth #Voltage graph
- Algebraic Graph Theory
2001/01/01 by Chris Godsil, Gordon Royle · 8 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
- 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
- TREEWIDTH OF CIRCLE GRAPHS
1996/06/01 by Ton Kloks · 2 citations
Computer Science · Mathematics · #Interconnection Networks and Systems #Advanced Graph Theory Research #Graph Theory and Algorithms #Treewidth #Combinatorics #Partial k-tree #Circle graph #Mathematics #Block graph #Chordal graph #Outerplanar graph #Discrete mathematics #Tree-depth #Split graph #Pathwidth #Clique-sum #1-planar graph #Line graph #Graph
- 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
- 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
- Kernels in perfect line-graphs
1992/05/01 by Frédéric Maffray · 2 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Block graph #Combinatorics #Conjecture #Discrete mathematics #Graph #Graph power #Graph theory and applications #Limits and Structures in Graph Theory #Line graph #Mathematics #Pathwidth #Perfect graph #Perfect graph theorem #Voltage graph
- 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)
- Decomposition by clique separators
1985/07/01 by Robert E. Tarjan · 8 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Block graph #Clique #Clique graph #Clique problem #Cograph #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Divide and conquer algorithms #Graph #Graph Labeling and Dimension Problems #Line graph #Mathematics #Pathwidth #Simplex graph #Split graph #Vertex (graph theory) #Voltage graph
- Almost all chordal graphs split
1985/04/01 by Edward A. Bender, L. Bruce Richmond, N. C. Wormald · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Graph theory and applications #Chordal graph #Mathematics #Combinatorics #Treewidth #Split graph #Interval graph #Block graph #Discrete mathematics #Chord (peer-to-peer) #Indifference graph #Clique-sum #Vertex (graph theory) #Pathwidth #Graph #1-planar graph #Line graph #Computer science
- A relationship between triangulated graphs, comparability graphs, proper interval graphs, proper circular‐arc graphs, and nested interval graphs
1982/09/01 by Dale Skrien · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #Combinatorics #Mathematics #Indifference graph #Interval graph #Pathwidth #Chordal graph #Split graph #Block graph #Cograph #Discrete mathematics #Comparability graph #Trapezoid graph #Maximal independent set #1-planar graph #Pancyclic graph #Graph #Line graph
- A clique problem equivalent to graph isomorphism
1978/07/01 by Dexter Kozen · 2 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #graph theory and CDMA systems #Combinatorics #Graph isomorphism #Induced subgraph isomorphism problem #Mathematics #Clique graph #Discrete mathematics #Subgraph isomorphism problem #Block graph #Split graph #Simplex graph #Cograph #Clique #Graph #Graph homomorphism #Isomorphism (crystallography) #Line graph #Pathwidth #Graph power #Voltage graph
- The intersection graphs of subtrees in trees are exactly the chordal graphs
1974/02/01 by Fǎnicǎ Gavril · 11 citations
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Block graph #Chordal graph #Combinatorics #Discrete mathematics #Distance-hereditary graph #Graph #Graph Labeling and Dimension Problems #Graph power #Graph theory and applications #Interval graph #Line graph #Mathematics #Outerplanar graph #Pathwidth #Split graph
- Algorithms for a maximum clique and a maximum independent set of a circle graph
1973/01/01 by Fǎnicǎ Gavril · 8 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Interconnection Networks and Systems #Graph Labeling and Dimension Problems #Combinatorics #Circle graph #Independent set #Mathematics #Split graph #Block graph #Clique graph #Vertex (graph theory) #Biconnected graph #Chord (peer-to-peer) #Chordal graph #Discrete mathematics #Graph #Computer science #Line graph #Pathwidth #Graph power #1-planar graph