On Group Choosability of Total Graphs

In this paper, we study the group and list group colorings of total graphs and present group coloring versions of the total and list total colorings conjectures. We establish the group coloring version of the total coloring conjecture for the following classes of graphs: graphs with small maximum degree, two-degenerate graphs, planner graphs with maximum degree at least 11, planner graphs without certain small cycles, outerplanar graphs and near outerplanar graphs with maximum degree at least 4. In addition, the group version of the list total coloring conjecture is established for forests, outerplanar graphs and graphs with maximum degree at most two.     

A polynomial algorithm to find an independent set of maximum weight in a fork-free graph

The class of fork-free graphs is an extension of claw-free graphs and their subclass of line graphs. The first polynomial-time solution to the maximum weight independent set problem in the class of line graphs, which is equivalent to the maximum matching problem in general graphs, has been proposed by Edmonds in 1965 and then extended to the entire class of claw-free graphs by Minty in 1980. Recently, Alekseev proposed a solution for the larger class of fork-free graphs, but only for the unweighted version of the problem, i.e., finding an independent set of maximum cardinality. In the present paper, we describe the first polynomial-time algorithm to solve the problem for weighted fork-free graphs.     

Combinatorial optimization with 2-joins

A 2-join is an edge cutset that naturally appears in decomposition of several classes of graphs closed under taking induced subgraphs, such as perfect graphs and claw-free graphs. In this paper we construct combinatorial polynomial time algorithms for finding a maximum weighted clique, a maximum weighted stable set and an optimal coloring for a class of perfect graphs decomposable by 2-joins: the class of perfect graphs that do not have a balanced skew partition, a 2-join in the complement, nor a homogeneous pair. The techniques we develop are general enough to be easily applied to finding a maximum weighted stable set for another class of graphs known to be decomposable by 2-joins, namely the class of even-hole-free graphs that do not have a star cutset.We also give a simple class of graphs decomposable by 2-joins into bipartite graphs and line graphs, and for which finding a maximum stable set is NP-hard. This shows that having holes all of the same parity gives essential properties for the use of 2-joins in computing stable sets.     

On maximum bipartite subgraphs

In this paper are investigated maximum bipartite subgraphs of graphs, i.e., bipartite subgraphs with a maximum number of edges. Such subgraphs are characterized and a criterion is given for a subgraph to be a unique maximum bipartite subgraph of a given graph. In particular maximum bipartite subgraphs of cubic graphs are investigated. It is shown that cubic graphs can be built up from five building stones (called elementary paths). Finally the investigation of a special class of cubic graphs yields a theorem which characterizes the Petersen graph and the dodecahedron graph by means of their maximum bipartite subgraphs.     

Independent packings in structured graphs

Packing a maximum number of disjoint triangles into a given graph G is NP-hard, even for most classes of structured graphs. In contrast, we show that packing a maximum number of independent (that is, disjoint and nonadjacent) triangles is polynomial-time solvable for many classes of structured graphs, including weakly chordal graphs, asteroidal triple-free graphs, polygon-circle graphs, and interval-filament graphs. These classes contain other well-known classes such as chordal graphs, cocomparability graphs, circle graphs, circular-arc graphs, and outerplanar graphs. Our results apply more generally to independent packings by members of any family of connected graphs. Research of both authors is supported by the Natural Sciences and Engineering Research Council of Canada.     

Approximating the minimum clique cover and other hard problems in subtree filament graphs

Subtree filament graphs are the intersection graphs of subtree filaments in a tree. This class of graphs contains subtree overlap graphs, interval filament graphs, chordal graphs, circle graphs, circular-arc graphs, cocomparability graphs, and polygon-circle graphs. In this paper we show that, for circle graphs, the clique cover problem is NP-complete and the h-clique cover problem for fixed h is solvable in polynomial time. We then present a general scheme for developing approximation algorithms for subtree filament graphs, and give approximation algorithms developed from the scheme for the following problems which are NP-complete on circle graphs and therefore on subtree filament graphs: clique cover, vertex colouring, maximum k-colourable subgraph, and maximum h-coverable subgraph.     

On finding augmenting graphs

Method of augmenting graphs is a general approach to solve the maximum independent set problem. As the problem is generally NP-hard, no polynomial time algorithms are available to implement the method. However, when restricted to particular classes of graphs, the approach may lead to efficient solutions. A famous example of this type is the maximum matching algorithm: it finds a maximum matching in a graph G, which is equivalent to finding a maximum independent set in the line graph of G. In the particular case of line graphs, the method reduces to finding augmenting (alternating) chains. Recent investigations of more general classes of graphs revealed many more types of augmenting graphs. In the present paper we study the problem of finding augmenting graphs different from chains. To simplify this problem, we introduce the notion of a redundant set. This allows us to reduce the problem to finding some basic augmenting graphs. As a result, we obtain a polynomial time solution to the maximum independent set problem in a class of graphs which extends several previously studied classes including the line graphs.     

Large graphs with given degree and diameter. II

The following problem arises in the study of interconnection networks: find graphs of given maximum degree and diameter having the maximum number of vertices. Constructions based on a new product of graphs, which enable us to construct graphs of given maximum degree and diameter, having a great number of vertices from smaller ones are given; therefore the best values known before are improved considerably.     

Ramsey numbers for bipartite graphs with small bandwidth

We estimate Ramsey numbers for bipartite graphs with small bandwidth and bounded maximum degree. In particular we determine asymptotically the two and three color Ramsey numbers for grid graphs. More generally, we determine asymptotically the two color Ramsey number for bipartite graphs with small bandwidth and bounded maximum degree and the three color Ramsey number for such graphs with the additional assumption that the bipartite graph is balanced.     

Line graphs: Their maximum nullities and zero forcing numbers

The maximum nullity over a collection of matrices associated with a graph has been attracting the attention of numerous researchers for at least three decades. Along these lines various zero forcing parameters have been devised and utilized for bounding the maximum nullity. The maximum nullity and zero forcing number, and their positive counterparts, for general families of line graphs associated with graphs possessing a variety of specific properties are analysed. Building upon earlier work, where connections to the minimum rank of line graphs were established, we verify analogous equations in the positive semidefinite cases and coincidences with the corresponding zero forcing numbers. Working beyond the case of trees, we study the zero forcing number of line graphs associated with certain families of unicyclic graphs.     

Some results on the Laplacian eigenvalues of unicyclic graphs

In this paper, we provide the smallest value of the second largest Laplacian eigenvalue for any unicyclic graph, and find the unicyclic graphs attaining that value. And also give an “asymptotically good” upper bounds for the second largest Laplacian eigenvalues of unicyclic graphs. Using this results, we can determine unicyclic graphs with maximum Laplacian separator. And unicyclic graphs with maximum Laplacian spread will also be determined.     

Polynomial algorithms for (integral) maximum two-flows in vertex edge-capacitated planar graphs

In this paper we study the maximum two-flow problem in vertex- and edge-capacitated undirected ST₂-planar graphs, that is, planar graphs where the vertices of each terminal pair are on the same face. For such graphs we provide an O(n) algorithm for finding a minimum two-cut and an O(n log n) algorithm for determining a maximum two-flow and show that the value of a maximum two-flow equals the value of a minimum two-cut. We further show that the flow obtained is half-integral and provide a characterization of edge and vertex capacitated ST₂-planar graphs that guarantees a maximum two-flow that is integral. By a simple variation of our maximum two-flow algorithm we then develop, for ST₂-planar graphs with vertex and edge capacities, an O(n log n) algorithm for determining an integral maximum two-flow of value not less than the value of a maximum two-flow minus one.     

On the Reverse Wiener Indices of Unicyclic Graphs

We determine the maximum values of the reverse Wiener indices of the unicyclic graphs with given cycle length, number of pendent vertices and maximum degree, respectively, and characterize the extremal graphs. We also determine the unicyclic graphs of given cycle length and diameter with minimum Wiener index.      

On the second largest Laplacian eigenvalues of graphs

The second largest Laplacian eigenvalue of a graph is the second largest eigenvalue of the associated Laplacian matrix. In this paper, we study extremal graphs for the extremal values of the second largest Laplacian eigenvalue and the Laplacian separator of a connected graph, respectively. All simple connected graphs with second largest Laplacian eigenvalue at most 3 are characterized. It is also shown that graphs with second largest Laplacian eigenvalue at most 3 are determined by their Laplacian spectrum. Moreover, the graphs with maximum and the second maximum Laplacian separators among all connected graphs are determined.     

极大外平面图在边界条件下的4染色

本文利用极大外平面图的对象变换研究它的染色，并给出了特征向量的概念，证明了任意两上有公共界环的极大外平面图都可以通过一系列对角变换互相得到，进而证明了有公共标定界环的两个极大外平面图在某些条件下有公共４染色。     

Q-integral graphs with edge-degrees at most five

We consider the problem of determining the Q-integral graphs, i.e. the graphs with integral signless Laplacian spectrum. We find all such graphs with maximum edge-degree 4, and obtain only partial results for the next natural case, with maximum edge-degree 5.     

On the Laplacian spectral radii of bipartite graphs

The Laplacian spectral radius of a graph is the largest eigenvalue of the associated Laplacian matrix. In this paper, we provide structural and behavioral details of graphs with maximum Laplacian spectral radius among all bipartite connected graphs of given order and size. Using these results, we provide a unified approach to determine the graphs with maximum Laplacian spectral radii among all trees, and all bipartite unicyclic, bicyclic, tricyclic and quasi-tree graphs, respectively.     

Sufficient conditions for a graph to be edge-colorable with maximum degree colors

We study properties of graphs related to the existence of certain vertex and edge partitions. These properties give sufficient conditions for a graph to be Class 1 (i.e., edge-colorable with maximum degree colors). We apply these conditions for solving the classification problem for graphs with acyclic core (the subgraph induced by the maximum degree vertices), and for subclasses of join graphs and cobipartite graphs.     

Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number

The maximum independent set problem is known to be NP-hard for graphs in general, but is solvable in polynomial time for graphs in many special classes. It is also known that the problem is generally intractable from a parameterized point of view. A simple Ramsey argument implies the fixed-parameter tractability of the maximum independent set problem in classes of graphs of bounded clique number. Beyond this observation very little is known about the parameterized complexity of the problem in restricted graph families. In the present paper we develop fpt-algorithms for graphs in some classes extending graphs of bounded clique number.     

On a new reformulation of Hadwiger's conjecture

Assuming that every proper minor closed class of graphs contains a maximum with respect to the homomorphism order, we prove that such a maximum must be homomorphically equivalent to a complete graph. This proves that Hadwiger's conjecture is equivalent to saying that every minor closed class of graphs contains a maximum with respect to homomorphism order. Let F be a finite set of 2-connected graphs, and let C be the class of graphs with no minor from F. We prove that if C has a maximum, then any maximum of C must be homomorphically equivalent to a complete graph. This is a special case of a conjecture of Nešet?il and Ossona de Mendez.