How to find overfull subgraphs in graphs with large maximum degree. II (Q1594580): Difference between revisions

[For Part I see Discrete Appl. Math. 51, No. 1-2, 117-125 (1994; Zbl 0805.05032).] Let \(G= G(V,E)\) be a simple graph with \(3\Delta(G)>|V|\). \(\chi'(G)\) and \(\Delta(G)\) be its chromatic index and the maximum degree of its vertices, respectively. \(G\) is said to be overfull, if \(|E|>\lfloor|V|/2\rfloor\cdot\Delta(G)\), and \(G\) is called Class 1, if \(\chi'=\Delta\), otherwise, \(G\) is called Class 2. It is known that \(\chi'= \Delta+1\) holds for every Class 2 graph. Every overfull graph is Class 2, as well as every graph \(G\) having an overfull subgraph with \(\Delta(H)= \Delta(G)\) (such a subgraph is called \(\Delta\)-overfull). It can be shown that a graph \(H\subset G\) is \(\Delta\)-overfull iff \(|E(H)|> \lfloor{1\over 2}|V(H)|\rfloor\cdot\Delta(G)\). An overfull graph conjecture, formulated in the literature, is stated, namely that a graph with \(3\Delta>|V|\) is Class 2 iff it has a \(\Delta\)-overfull subgraph. Whereas in Part I (in the course of the investigation of simple graphs with \(2\Delta\geq|V|\)) an algorithm for finding overfull subgraphs was presented, the main result of Part II is an algorithm which finds all induced \(\Delta\)-overfull subgraphs of a graph \(G\) with \(3\Delta(G)>|V|\). Therefore at first the algorithm given in Part I, is modified such that it determines every induced \(\Delta\)-overfull subgraph \(H\) of an arbitrary graph \(G\) with \(|V(H)|>|V(G)|- \Delta(G)\) in \(O(n\log n+m)\) time, where \(n\) and \(m\) denote the order and the size of \(G\), respectively, and this algorithm is called Algorithm 1 (Theorem 3.2). Moreover, the author receives a generalization of Theorem 3.4 in Part I, namely that every graph \(G\) has at most one induced \(\Delta\)-overfull subgraph \(H\) with \(|V(H)|>|V(G)|- \Delta(G)\) (Theorem 3.3). In the special case of simple graphs with \(2\Delta\geq|V|\) it follows that these graphs have at most one induced \(\Delta\)-overfull subgraph, which can be found in \(O(n+ m)\) time (Theorem 3.4), and by this the former algorithm is improved to run in linear time. To get the above-mentioned main result, Algorithm 2 is developed in three phases and Algorithm 1 is applied here occasionally. Moreover, two procedures for this problem are used, namely one for the general case and another for the regular graphs. The author proves the following results: Algorithm 2 finds all induced \(\Delta\)-overfull subgraphs of a graph \(G\) with \(3\Delta(G)>|V(G)|\), they can be found on \(O(n^{{5\over 3}}m)\) time and in the case of a regular graph in \(O(n^3)\) time, where \(n\) and \(m\) denote the order and size of \(G\), respectively (Theorems 4.3, 4.4, and 4.5). Finally, with the help of Algorithm 2, Corollary 4.6 can be deduced: A graph with \(3\Delta>|V|\) has at most three induced \(\Delta\)-overfull subgraphs.