Header menu link for other important links
X
Minimally 2-connected graphs and colouring problems
Published in
2011
Pages: 215 - 218
Abstract
A 2-connected graph G is minimally 2-connected (m2c ) , if G - e contains a cut vertex for any edge e. Thus every edge is critical for the 2-connectivity. This class has been studied independently by Plummer [10] and Dirac [6] and they obtain some interesting structural properties of these classes. In the context of edge colouring problems, we revisit these results and this reveals some interesting structural properties which are useful in several graph colouring problems. We present the structural properties and application to 4 different problems viz. induced matching, acyclic and k-intersection edge colourings and balanced decomposition. The structure has similarity with structure of degenerate graphs and this enables one to also generalise some of these results to graphs of given degeneracy. All these results are co-authored by the author in [9,3,4,5]. In the following, d(x) is the degree of a vertex, Δ maximum degree. Vertices of degree at least, at most and equal to k are denoted k +, k-, k. For each connected graph we can find a block-cut-vertex tree which contains all cut-vertices and blocks of G and a cut-vertex v of G is adjacent to a block B of G whenever v ε V (B). An end block is a block containing at most one cut-vertex in G. Undefined terms can be found in standard textbooks in graph theory.
About the journal
Journal10th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, CTW 2011 - Proceedings of the Conference
Open AccessFalse