Three-Rainbow Coloring of Split Graphs

After a necessary condition is given, 3-rainbow coloring of split graphs with time complexity O(m) is obtained by constructive method. The number of corresponding colors is at most 2 or 3 more than the minimum number of colors needed in a 3-rainbow coloring.

The Interval Graph Completion Problem on Split Graphs

The interval graph completion problem on a graph G is to find an added edge set F such that G + F is an interval supergraph with the smallest possible number of edges. The problem has important applications to numerical algebra, V LSI-layout and algorithm graph theory etc; And it has been known to be N P-complete on general graphs. Some classes of special graphs have been investigated in the literatures. In this paper the interval graph completion problem on split graphs is investigated.

Split Graphs with Completely Regular Endomorphism Monoids

In this paper, split graphs with complete endomorphism-regularity are characterized explicitly. Hopefully, the main idea of the proofs can also be used for other classes of graphs.

Split graphs whose half-strong endomorphisms form a monoid

In this paper, the half-strong, the locally strong and the quasi-strong endomorphisms of a split graph are investigated. Let X be a split graph and let End（X）, hEnd（X）, 1End（X） and qEnd（X） be the endomorphism monoid, the set of all half-strong endomorphisms, the set of all locally strong endomorphisms and the set of all quasi-strong endomorphisms of X, respectively. The conditions under which hEnd（X） forms a submonoid of End（X） are given. It is shown that 1End（X） = qEnd（X） for any split graph X. The conditions under which 1End（X） （resp. qEnd（X）） forms a submonoid of End（X） are also given. In particular, if hEnd（X） forms a monoid, then 1End（X） （resp. qEnd（X）） forms a monoid too.

The Join of Split Graphs Whose Half-strong Endomorphisms Form a Monoid

In this paper, the half-strong endomorphisms of the join of split graphs are investigated. We give the conditions under which the half-strong endomorphisms of the join of split graphs form a monoid.

On the parameterized complexity of minimum/maximum degree vertex deletion on several special graphs

In the minimum degree vertex deletion problem,we are given a graph,a distinguished vertex in the graph,and an integer κ,and the question is whether we can delete at most κ vertices from the graph so that the distinguished vertex has the unique minimum degree.The maximum degree vertex deletion problem is defined analogously but here we want the distinguished vertex to have the unique maximum degree.It is known that both problems areΨ-hard and fixed-parameter intractable with respect to some natural parameters.In this paper,we study the(parameterized)complexity of these two problems restricted to split graphs,p-degenerate graphs,and planar graphs.Our study provides a comprehensive complexity landscape of the two problems restricted to these special graphs.

The Comaximal Graphs of Noncommutative Rings

For a ring R(not necessarily commutative)with identity,the comaximal graph of R,denoted byΩ(R),is a graph whose vertices are all the nonunit elements of R,and two distinct vertices a and b are adjacent if and only if Ra+Rb=R.In this paper we consider a subgraphΩ_(1)(R)ofΩ(R)induced by R\Uℓ(R),where Uℓ(R)is the set of all left-invertible elements of R.We characterize those rings R for whichΩ_(1)(R)\J(R)is a complete graph or a star graph,where J(R)is the Jacobson radical of R.We investigate the clique number and the chromatic number of the graphΩ_(1)(R)\J(R),and we prove that if every left ideal of R is symmetric,then this graph is connected and its diameter is at most 3.Moreover,we completely characterize the diameter ofΩ_(1)(R)\J(R).We also investigate the properties of R whenΩ_(1)(R)is a split graph.