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

coloringcycle with a unique chorddecompositiondetectionHeawood graphPetersen graphrecognitionstructure

Mathematics Subject Classification ID

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

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

• 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
• scientific article; zbMATH DE number 3445275 (Why is no real title available?)
• Map-Colour Theorem
• On a Class of Totally Unimodular Matrices
• On the complexity of testing for odd holes and induced odd paths
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• 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

(48)

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