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

DOI10.1002/JGT.20405zbMATH Open1186.05104DBLPjournals/jgt/TrotignonV10arXiv1309.0979OpenAlexW2952096650WikidataQ59903346 ScholiaQ59903346MaRDI QIDQ5189239FDOQ5189239

Authors: Kristina Vušković, Nicolas Trotignon 

Publication date: 15 March 2010

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

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.

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

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

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)

Cites Work

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

Cited In (45)

• \(\chi\)-bounds, operations, and chords
• On graphs with no induced subdivision of \(K_4\)
• 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
• Characterizing k-chordal unichord-free graphs
• Total chromatic number of 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
• Vizing bound for the chromatic number on some graph classes
• Some completion problems for graphs without chordless cycles of prescribed lengths
• Practical and efficient split decomposition via graph-labelled trees
• A new characterization of unichord-free graphs
• 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
• Induced subgraphs and tree decompositions. VI: Graphs with 2-cutsets
• Excluding cycles with a fixed number of chords
• Strongly unichord-free graphs
• The (theta, wheel)-free graphs. II: Structure theorem
• Detecting induced subgraphs
• List neighbor sum distinguishing edge coloring of subcubic graphs
• Efficient algorithms for clique-colouring and biclique-colouring unichord-free graphs
• Requiring that minimal separators induce complete multipartite subgraphs
• Graphs that have separator tree representations
• Hereditary efficiently dominatable graphs
• Complexity-separating graph classes for vertex, edge and total colouring
• Triangle‐free graphs with large chromatic number and no induced wheel
• A decomposition for total-coloring partial-grids and list-total-coloring outerplanar graphs
• New graph classes characterized by weak vertex separators and two-pairs
• Combinatorial optimization with 2-joins
• Graphs that do not contain a cycle with a node that has at least two neighbors on it
• On efficient coloring of chordless graphs
• When all minimal vertex separators induce complete or edgeless subgraphs
• Edge-colouring and total-colouring chordless graphs
• Compositions, decompositions, and conformability for total coloring on power of cycle graphs
• Even-power of cycles with many vertices are type 1 total colorable
• Complexity of colouring problems restricted to unichord-free and square, unichord-free graphs

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)