| Summary: | The cutwidth of a graph <i>G</i> is the smallest integer <i>k</i> (<inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>k</mi><mo>≥</mo><mn>1</mn></mrow></semantics></math></inline-formula>) such that the vertices of <i>G</i> are arranged in a linear layout <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>[</mo><msub><mi>v</mi><mn>1</mn></msub><mo>,</mo><msub><mi>v</mi><mn>2</mn></msub><mo>,</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo>,</mo><msub><mi>v</mi><mi>n</mi></msub><mo>]</mo></mrow></semantics></math></inline-formula>, in such a way that for each <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>i</mi><mo>=</mo><mn>1</mn><mo>,</mo><mn>2</mn><mo>,</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo>,</mo><mi>n</mi><mo>−</mo><mn>1</mn></mrow></semantics></math></inline-formula>, there are at most <i>k</i> edges with one endpoint in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>{</mo><msub><mi>v</mi><mn>1</mn></msub><mo>,</mo><msub><mi>v</mi><mn>2</mn></msub><mo>,</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo>,</mo><msub><mi>v</mi><mi>i</mi></msub><mo>}</mo></mrow></semantics></math></inline-formula> and the other in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>{</mo><msub><mi>v</mi><mrow><mi>i</mi><mo>+</mo><mn>1</mn></mrow></msub><mo>,</mo><mo>.</mo><mo>.</mo><mo>.</mo><mo>,</mo><msub><mi>v</mi><mi>n</mi></msub><mo>}</mo></mrow></semantics></math></inline-formula>. The cutwidth problem for <i>G</i> is to determine the cutwidth <i>k</i> of <i>G</i>. A graph <i>G</i> with cutwidth <i>k</i> is <i>k</i>-cutwidth critical if every proper subgraph of <i>G</i> has a cutwidth less than <i>k</i> and <i>G</i> is homeomorphically minimal. In this paper, except five irregular graphs, other 4-cutwidth critical graphs were resonably classified into two classes, which are graph class with a central vertex <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>v</mi><mn>0</mn></msub></semantics></math></inline-formula>, and graph class with a central cycle <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>C</mi><mi>q</mi></msub></semantics></math></inline-formula> of length <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>q</mi><mo>≤</mo><mn>6</mn></mrow></semantics></math></inline-formula>, respectively, and any member of two graph classes can skillfuly achieve a subgraph decomposition <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi mathvariant="script">S</mi></semantics></math></inline-formula> with cardinality 2, 3 or 4, where each member of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi mathvariant="script">S</mi></semantics></math></inline-formula> is either a 2-cutwith graph or a 3-cutwidth graph.
|
|---|