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

From MaRDI portal
Revision as of 23:57, 19 February 2024 by RedirectionBot (talk | contribs) (‎Changed an Item)
scientific article
Language Label Description Also known as
English
How to find overfull subgraphs in graphs with large maximum degree. II
scientific article

    Statements

    How to find overfull subgraphs in graphs with large maximum degree. II (English)
    0 references
    0 references
    8 February 2001
    0 references
    [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.
    0 references
    chromatic index
    0 references
    maximum degree
    0 references
    overfull graph
    0 references
    algorithm
    0 references
    regular graphs
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references