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)

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

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)