Structure and algorithms for (cap, even hole)-free graphs

DOI10.1016/j.disc.2017.09.013zbMath1376.05132arXiv1611.08066OpenAlexW2558490395WikidataQ59885331 ScholiaQ59885331MaRDI QIDQ1685999

Murilo V. G. da Silva, Kristina Vušković, Shenwei Huang, Kathie Cameron

Publication date: 20 December 2017

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1611.08066

zbMATH Keywords

decompositioncombinatorial optimizationtreewidthcoloringmaximum weight stable setclique-widthstructure theoremeven-hole-free graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Structural characterization of families of graphs (05C75) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Vertex degrees (05C07)

Related Items (15)

The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable ⋮ Complete complexity dichotomy for $7$-edge forbidden subgraphs in the edge coloring problem ⋮ Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes ⋮ Clique‐width: Harnessing the power of atoms ⋮ 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 ⋮ Coloring \((4K_1,C_4,C_6)\)-free graphs ⋮ Induced subgraphs and tree decompositions. IV: (Even hole, diamond, pyramid)-free graphs ⋮ A note on chromatic number of (cap, even hole)-free graphs ⋮ Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey ⋮ On the tree-width of even-hole-free graphs ⋮ A better upper bound on the chromatic number of (cap, even-hole)-free graphs ⋮ The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs ⋮ Two classes of \(\beta \)-perfect graphs that do not necessarily have simplicial extremes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Coloring vertices of a graph or finding a Meyniel obstruction
• Stable sets and graphs with no even holes
• Triangulated neighborhoods in even-hole-free graphs
• Bisimplicial vertices in even-hole-free graphs
• A bound on the treewidth of planar even-hole-free graphs
• Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
• Decomposition by clique separators
• On a conjecture of Meyniel
• A fast algorithm for coloring Meyniel graphs
• Alpha-balanced graphs and matrices and GF(3)-representability of matroids
• On the perfect graph conjecture
• Efficient graph representations
• 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
• Compositions for perfect graphs
• A faster algorithm to recognize even-hole-free graphs
• Approximating clique-width and branch-width
• Vertex elimination orderings for hereditary graph classes
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Even-hole-free graphs part II: Recognition algorithm
• Perfect coloring and linearly χ-boundP6-free graphs
• Even and odd holes in cap-free graphs
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Deciding Clique-Width for Graphs of Bounded Tree-Width
• On the structure of (pan, even hole)‐free graphs
• Even-hole-free graphs: A survey
• Approximating rank-width and clique-width quickly
• HOLES AND DOMINOES IN MEYNIEL GRAPHS
• On the Relationship Between Clique-Width and Treewidth
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Paths and Circuits in Critical Graphs
• An \(O(n^2)\) algorithm to color Meyniel graphs

This page was built for publication: Structure and algorithms for (cap, even hole)-free graphs