English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We give a structural description of the class  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  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 2 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 , i.e. every graph in  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 . This has several consequences: an ( nm ) ‐time algorithm to decide whether a graph is in , an ( n +  m ) ‐time algorithm that finds a maximum clique of any graph in , and an ( nm ) ‐time coloring algorithm for graphs in . We prove that every graph in  is either 3‐colorable or has a coloring with ω colors where ω is the size of a largest clique. The problem of finding a maximum stable set for a graph in  is known to be NP‐hard. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 31–67, 2010

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