A structure theorem for graphs with no cycle with a unique chord and its consequences

DOI10.1002/JGT.20405MaRDI QIDQ5189239zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Kristina Vušković, Nicolas Trotignon

Publication date 15 March 2010

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

decompositionrecognitioncoloringPetersen graphstructuredetectionHeawood graphcycle with a unique chord

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75)

Abstract: We give a structural description of the class $calC$ of graphs that do not contain a cycle with a unique chord as an induced subgraph. Our main theorem states that any connected graph in $calC$ is either in some simple basic class or has a decomposition. Basic classes are chordless cycles, cliques, bipartite graphs with one side containing only nodes of degree two and induced subgraphs of the famous Heawood or Petersen graph. Decompositions are node cutsets consisting of one or two nodes and edge cutsets called 1-joins. Our decomposition theorem actually gives a complete structure theorem for $calC$, i.e. every graph in $calC$ can be built from basic graphs that can be explicitly constructed, and gluing them together by prescribed composition operations; and all graphs built this way are in $calC$. This has several consequences: an $calO(nm)$-time algorithm to decide whether a graph is in $calC$, an $calO(n+m)$-time algorithm that finds a maximum clique of any graph in $calC$ and an $calO(nm)$-time coloring algorithm for graphs in $calC$. We prove that every graph in $calC$ is either 3-colorable or has a coloring with $omega$ colors where $omega$ is the size of a largest clique. The problem of finding a maximum stable set for a graph in $calC$ is known to be NP-hard.

Recommendations

• The class of \((P_7, C_4, C_5)\)-free graphs: decomposition, algorithms, and \(\chi \)-boundedness
• On graphs with no induced subdivision of \(K_4\)
• The (theta, wheel)-free graphs. III: Cliques, stable sets and coloring
• Excluding cycles with a fixed number of chords
• Chromatic index of graphs with no cycle with a unique chord

Cites work

• scientific article; zbMATH DE number 3445275 (Why is no real title available?)
• Algorithms for Perfectly Contractile Graphs
• Alpha-balanced graphs and matrices and GF(3)-representability of matroids
• Balanced matrices
• Decomposition of Directed Graphs
• Depth-First Search and Linear Graph Algorithms
• Dividing a Graph into Triconnected Components
• Even and odd holes in cap-free graphs
• Graph Theory and Probability
• Map-Colour Theorem
• On a Class of Totally Unimodular Matrices
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• On the complexity of testing for odd holes and induced odd paths
• Parallel Algorithms for Hierarchical Clustering and Applications to Split Decomposition and Parity Graph Recognition
• Recognizing Berge graphs
• Structural properties and recognition of restricted and strongly unimodular matrices
• The strong perfect graph theorem
• The three-in-a-tree problem
• Vertex colouring and forbidden subgraphs -- a survey

Cited in

(44)

• Complexity-separating graph classes for vertex, edge and total colouring
• Some completion problems for graphs without chordless cycles of prescribed lengths
• The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs
• Practical and efficient split decomposition via graph-labelled trees
• When all minimal vertex separators induce complete or edgeless subgraphs
• The P versus NP-complete dichotomy of some challenging problems in graph theory
• A new characterization of unichord-free graphs
• Characterizing atoms that result from decomposition by clique separators
• Graphs of separability at most two: structural characterizations and their consequences
• Total chromatic number of \{square,unichord\}-free graphs
• List neighbor sum distinguishing edge coloring of subcubic graphs
• Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs
• Graphs of separability at most 2
• Excluding induced subdivisions of the bull and related graphs
• Even-power of cycles with many vertices are type 1 total colorable
• Requiring that minimal separators induce complete multipartite subgraphs
• FPT and kernelization algorithms for the induced tree problem
• Triangle‐free graphs with large chromatic number and no induced wheel
• Complexity of colouring problems restricted to unichord-free and square, unichord-free graphs
• Strongly unichord-free graphs
• Wheel-free planar graphs
• Complexity separating classes for edge-colouring and total-colouring
• Edge-colouring and total-colouring chordless graphs
• Graphs that have separator tree representations
• Unique chords of unique cycles in 3-connected planar graphs
• The (theta, wheel)-free graphs. II: Structure theorem
• Chromatic index of graphs with no cycle with a unique chord
• A decomposition for total-coloring partial-grids and list-total-coloring outerplanar graphs
• Graphs that do not contain a cycle with a node that has at least two neighbors on it
• On efficient coloring of chordless graphs
• \(\chi\)-bounds, operations, and chords
• Hereditary efficiently dominatable graphs
• Characterizing k-chordal unichord-free graphs
• Excluding clocks
• Using SPQR-trees to speed up algorithms based on 2-cutset decompositions
• Total chromatic number of unichord-free graphs
• Induced subgraphs and tree decompositions. VI: Graphs with 2-cutsets
• Vizing bound for the chromatic number on some graph classes
• Using SPQR-trees to speed up recognition algorithms based on 2-cutsets
• New graph classes characterized by weak vertex separators and two-pairs
• Excluding cycles with a fixed number of chords
• Combinatorial optimization with 2-joins
• On graphs with no induced subdivision of \(K_4\)
• Compositions, decompositions, and conformability for total coloring on power of cycle graphs

Describes a project that uses

Uses Software

• Algorithm 447

This page was built for publication: A structure theorem for graphs with no cycle with a unique chord and its consequences

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