Mathematics – Combinatorics
Scientific paper
2010-12-28
Mathematics
Combinatorics
17 pages, submitted on Nov. 10 2010
Scientific paper
The series-parallel (SP) graphs are those containing no topological $K_{_4}$ and are considered trivial. We relax the prohibition distinguishing the SP graphs by forbidding only embeddings of $K_{_4}$ whose edges with both ends 3-valent (skeleton hereafter) induce a graph isomorphic to certain prescribed subgraphs of $K_{_4}$. In particular, we describe the structure of the graphs containing no embedding of $K_{_4}$ whose skeleton is isomorphic to $P_{_3}$ or $P_{_4}$. Such "almost series-parallel graphs" (ASP) still admit a concise description. Amongst other things, their description reveals that: 1. Essentially, the 3-connected ASP graphs are those obtained from the 3-connected cubic graphs by replacing each vertex with a triangle (e.g., the 3-connected claw-free graphs). 2. Except for $K_{_6}$, the ASP graphs are 5-colorable in polynomial time. Distinguishing between the 5-chromatic and the 4-colorable ASP graphs is $NP$-hard. 3. The ASP class is significantly richer than the SP class: 4-vertex-colorability, 3-edge-colorability, and Hamiltonicity are $NP$-hard for ASP graphs. Our interest in such ASP graphs arises from a previous paper of ours: "{\sl On the colorability of graphs with forbidden minors along paths and circuits}, Discrete Math. (to appear)".
Aigner-Horev Elad
No associations
LandOfFree
Almost Series-Parallel graphs: structure and colorability does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Almost Series-Parallel graphs: structure and colorability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Almost Series-Parallel graphs: structure and colorability will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-428392