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

DOI10.1016/J.DISC.2017.09.013MaRDI QIDQ1685999zbMATH OpenOpenAlexWikidataFDO

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

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, http://eprints.whiterose.ac.uk/119116/1/capcolorCW-pub.pdf

zbMATH Keywords

combinatorial optimizationdecompositiontreewidthclique-widthstructure theoremcoloringmaximum weight stable seteven-hole-free graph

Mathematics Subject Classification ID

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

Abstract: A graph is even-hole-free if it has no induced even cycles of length 4 or more. A cap is a cycle of length at least 5 with exactly one chord and that chord creates a triangle with the cycle. In this paper, we consider (cap, even hole)-free graphs, and more generally, (cap, 4-hole)-free odd-signable graphs. We give an explicit construction of these graphs. We prove that every such graph $G$ has a vertex of degree at most $frac32omega(G)-1$, and hence $chi(G)leqfrac32omega(G)$, where $omega(G)$ denotes the size of a largest clique in $G$ and $chi(G)$ denotes the chromatic number of $G$. We give an $O(nm)$ algorithm for $q$-coloring these graphs for fixed $q$ and an $O(nm)$ algorithm for maximum weight stable set. We also give a polynomial-time algorithm for minimum coloring. Our algorithms are based on our results that triangle-free odd-signable graphs have treewidth at most 5 and thus have clique-width at most 48, and that (cap, 4-hole)-free odd-signable graphs $G$ without clique cutsets have treewidth at most $6omega(G)-1$ and clique-width at most 48.

Recommendations

• Even and odd holes in cap-free graphs
• scientific article; zbMATH DE number 1496606
• A note on chromatic number of (cap, even hole)-free graphs
• A better upper bound on the chromatic number of (cap, even-hole)-free graphs
• On the structure of (pan, even hole)-free graphs

Cites work

• scientific article; zbMATH DE number 3878985 (Why is no real title available?)
• scientific article; zbMATH DE number 3556145 (Why is no real title available?)
• scientific article; zbMATH DE number 1496606 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A bound on the treewidth of planar even-hole-free graphs
• A fast algorithm for coloring Meyniel graphs
• A faster algorithm to recognize even-hole-free graphs
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Alpha-balanced graphs and matrices and GF(3)-representability of matroids
• An \(O(n^2)\) algorithm to color Meyniel graphs
• Approximating clique-width and branch-width
• Approximating rank-width and clique-width quickly
• Bisimplicial vertices in even-hole-free graphs
• Coloring vertices of a graph or finding a Meyniel obstruction
• Compositions for perfect graphs
• Deciding Clique-Width for Graphs of Bounded Tree-Width
• Decomposition by clique separators
• Edge dominating set and colorings on graphs with fixed clique-width
• Efficient graph representations
• Even and odd holes in cap-free graphs
• Even-hole-free graphs part II: Recognition algorithm
• Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
• Even-hole-free graphs: A survey
• Finding a strong stable set or a Meyniel obstruction in any graph
• Holes and dominoes in Meyniel graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• On a conjecture of Meyniel
• On the Relationship Between Clique-Width and Treewidth
• On the perfect graph conjecture
• On the structure of (pan, even hole)-free graphs
• Paths and Circuits in Critical Graphs
• Perfect coloring and linearly χ-boundP6-free graphs
• Stable sets and graphs with no even holes
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Triangulated neighborhoods in even-hole-free graphs
• Upper bounds to the clique width of graphs
• Vertex elimination orderings for hereditary graph classes
• -perfect graphs

Cited in

(25)

• Even-hole-free graphs: A survey
• The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable
• Tree independence number. I. (Even hole, diamond, pyramid)-free graphs
• The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs
• Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes
• On the structure of (banner, odd hole)-free graphs
• Induced subgraphs and tree decompositions. IV: (Even hole, diamond, pyramid)-free graphs
• Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
• Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey
• Finding a smallest odd hole in a claw-free graph using global structure
• (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels
• Complete complexity dichotomy for 7-edge forbidden subgraphs in the edge coloring problem
• (Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth
• On the tree-width of even-hole-free graphs
• Two classes of \(\beta \)-perfect graphs that do not necessarily have simplicial extremes
• Clique‐width: Harnessing the power of atoms
• Stable sets and graphs with no even holes
• A class of graphs with large rankwidth
• A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs
• On the structure of (pan, even hole)-free graphs
• On the chromatic number of a family of odd hole free graphs
• Coloring \((4K_1,C_4,C_6)\)-free graphs
• A note on chromatic number of (cap, even hole)-free graphs
• A better upper bound on the chromatic number of (cap, even-hole)-free graphs
• Even-hole-free graphs part II: Recognition algorithm

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1685999)