On the structure of (pan, even hole)‐free graphs
From MaRDI portal
Publication:4604020
DOI10.1002/jgt.22146zbMath1387.05215arXiv1508.03062OpenAlexW2964127636MaRDI QIDQ4604020
Steven Chaplick, Kathie Cameron, Chính T. Hoàng
Publication date: 23 February 2018
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1508.03062
Analysis of algorithms (68W40) Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (11)
Structure and algorithms for (cap, even hole)-free graphs ⋮ A class of graphs with large rankwidth ⋮ (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels ⋮ (Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth ⋮ Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey ⋮ On the tree-width of even-hole-free graphs ⋮ Free fermions behind the disguise ⋮ On the structure of (even hole, kite)-free graphs ⋮ On \(H\)-topological intersection graphs ⋮ Square-Free Graphs with No Six-Vertex Induced Path ⋮ Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure
Cites Work
- Unnamed Item
- Unnamed Item
- Finding and counting small induced subgraphs efficiently
- On rigid circuit graphs
- Triangulated neighborhoods in even-hole-free graphs
- Bisimplicial vertices in even-hole-free graphs
- Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
- Decomposition by clique separators
- The strong perfect graph conjecture for pan-free graphs
- An \(0(n^{1.5})\) algorithm to color proper circular arcs
- A characterisation of rigid circuit graphs
- Edge dominating set and colorings on graphs with fixed clique-width
- \(\beta\)-perfect graphs
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- A faster algorithm to recognize even-hole-free graphs
- On the vertex packing problem
- Vertex elimination orderings for hereditary graph classes
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Even-hole-free graphs part II: Recognition algorithm
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Unit Circular-Arc Graph Representations and Feasible Circulations
- Representations of chordal graphs as subtrees of a tree
- The NP-Completeness of Edge-Coloring
- An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
- Detecting even holes
- Even-hole-free graphs: A survey
- ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P4'S
- On the Relationship Between Clique-Width and Treewidth
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- Independent Sets of Maximum Weight in Apple-Free Graphs
- Graph-Theoretic Concepts in Computer Science
This page was built for publication: On the structure of (pan, even hole)‐free graphs
