Uniquely cocolourable graphs

A graphG is uniquelyn-cocolourable if (its cochromatic number)z(G) = n and alln-cocolourings ofG induce the same partition of its vertex set. We prove that there are infinitely many uniquelyn-cocolourable graphs and that the numbers of complete and empty colour classes can be prescribed. It is also shown that everyn-cocolourable graph is an induced subgraph of a uniquelyn-cocolourable graph.     

Note on the cochromatic number of several surfaces

The cochromatic number of a graph G, denoted by z(G), is the minimum number of subsets into which the vertex set of G can be partitioned so that each subset induces an empty or a complete subgraph of G. In an earlier work, the author considered the problem of determining z(S), the maximum cochromatic number among all graphs that embed in a surface S. The value of z(S) was found for the sphere, the Klein bottle, and for the nonorientable surface of genus 4. In this note, some recent results of Albertson and Hutchinson are used to determine the cochromatic numbers of the projective plane and the nonorientable surface of genus 3. These results lend further evidence to support the conjecture that z(S) is equal to the maximum n for which the graph G_n = K₁ U K₂ U … U K_n embeds in S.     

Cochromatic Number and the Genus of a Graph

The cochromatic number of a graph G, denoted by z(G), is the minimum number of subsets into which the vertex set of G can be partitioned so that each sbuset induces an empty or a complete subgraph of G. In this paper we introduce the problem of determining for a surface S, z(S), which is the maximum cochromatic number among all graphs G that embed in S. Some general bounds are obtained; for example, it is shown that if S is orientable of genus at least one, or if S is nonorientable of genus at least four, then z(S) is nonorientable of genus at least four, then z(S)≤χ(S). Here χ(S) denotes the chromatic number S. Exact results are obtained for the sphere, the Klein bottle, and for S. It is conjectured that z(S) is equal to the maximum n for which the graph G_n = K₁ ∪ K₂ ∪ … ∪ K_n embeds in S.     

Some extremal results in cochromatic and dichromatic theory

For a graph G, the cochromatic number of G, denoted z(G), is the least m for which there is a partition of the vertex set of G having order m. where each part induces a complete or empty graph. We show that if {G_n} is a family of graphs where G_n has o(n² log²(n)) edges, then z(G_n) = o(n). We turn our attention to dichromatic numbers. Given a digraph D, the dichromatic number of D is the minimum number of parts the vertex set of D must be partitioned into so that each part induces an acyclic digraph. Given an (undirected) graph G, the dichromatic number of G, denoted d(G), is the maximum dichromatic number of all orientations of G. Let m be an integer; by d(m) we mean the minimum size of all graphs G where d(G) = m. We show that d(m) = θ(m² ln²(m)).     

On chromatic‐choosable graphs

A graph is chromatic‐choosable if its choice number coincides with its chromatic number. It is shown in this article that, for any graph G, if we join a sufficiently large complete graph to G, then we obtain a chromatic‐choosable graph. As a consequence, if the chromatic number of a graph G is close enough to the number of vertices in G, then G is chromatic‐choosable. We also propose a conjecture related to this fact. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 130–135, 2002     

Bounds for the vertex linear arboricity

The vertex linear arboricity vla(G) of a nonempty graph G is the minimum number of subsets into which the vertex set V(G) can be partitioned so that each subset induces a subgraph whose connected components are paths. This paper provides an upper bound for vla(G) of a connected nonempty graph G, namely vla(G) ≦ 1 + ?δ(G)/2? where δ(G) denotes the maximum degree of G. Moreover, if δ(G) is even, then vla(G) = 1 + ?δ(G)/2? if and only if G is either a cycle or a complete graph.     

Partitioning graphs into complete and empty graphs

Given integers j and k and a graph G, we consider partitions of the vertex set of G into j+k parts where j of these parts induce empty graphs and the remaining k induce cliques. If such a partition exists, we say G is a (j,k)-graph. For a fixed j and k we consider the maximum order n where every graph of order n is a (j,k)-graph. The split-chromatic number of G is the minimum j where G is a (j,j)-graph. Further, the cochromatic number is the minimum j+k where G is a (j,k)-graph. We examine some relations between cochromatic, split-chromatic and chromatic numbers. We also consider some computational questions related to chordal graphs and cographs.     

Total domination critical and stable graphs upon edge removal

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number of G. A graph is total domination edge critical if the removal of any arbitrary edge increases the total domination number. On the other hand, a graph is total domination edge stable if the removal of any arbitrary edge has no effect on the total domination number. In this paper, we characterize total domination edge critical graphs. We also investigate various properties of total domination edge stable graphs.     

Game-perfect graphs

A graph coloring game introduced by Bodlaender (Int J Found Comput Sci 2:133–147, 1991) as coloring construction game is the following. Two players, Alice and Bob, alternately color vertices of a given graph G with a color from a given color set C, so that adjacent vertices receive distinct colors. Alice has the first move. The game ends if no move is possible any more. Alice wins if every vertex of G is colored at the end, otherwise Bob wins. We consider two variants of Bodlaender’s graph coloring game: one (A) in which Alice has the right to have the first move and to miss a turn, the other (B) in which Bob has these rights. These games define the A-game chromatic number resp. the B-game chromatic number of a graph. For such a variant g, a graph G is g-perfect if, for every induced subgraph H of G, the clique number of H equals the g-game chromatic number of H. We determine those graphs for which the game chromatic numbers are 2 and prove that the triangle-free B-perfect graphs are exactly the forests of stars, and the triangle-free A-perfect graphs are exactly the graphs each component of which is a complete bipartite graph or a complete bipartite graph minus one edge or a singleton. From these results we may easily derive the set of triangle-free game-perfect graphs with respect to Bodlaender’s original game. We also determine the B-perfect graphs with clique number 3. As a general result we prove that complements of bipartite graphs are A-perfect.      

Polar permutation graphs are polynomial-time recognisable

Polar graphs generalise bipartite graphs, cobipartite graphs, and split graphs, and they constitute a special type of matrix partitions. A graph is polar if its vertex set can be partitioned into two, such that one part induces a complete multipartite graph and the other part induces a disjoint union of complete graphs. Deciding whether a given arbitrary graph is polar, is an NP$\text{NP}$-complete problem. Here, we show that for permutation graphs this problem can be solved in polynomial time. The result is surprising, as related problems like achromatic number and cochromatic number are NP$\text{NP}$-complete on permutation graphs. We give a polynomial-time algorithm for recognising graphs that are both permutation and polar. Prior to our result, polarity has been resolved only for chordal graphs and cographs.     

On Trees with Double Domination Number Equal to the 2-Outer-Independent Domination Number Plus One

A vertex of a graph is said to dominate itself and all of its neighbors.A double dominating set of a graph G is a set D of vertices of G,such that every vertex of G is dominated by at least two vertices of D.The double domination number of a graph G is the minimum cardinality of a double dominating set of G.For a graph G =(V,E),a subset D V(G) is a 2-dominating set if every vertex of V(G) \ D has at least two neighbors in D,while it is a 2-outer-independent dominating set of G if additionally the set V(G)\D is independent.The 2-outer-independent domination number of G is the minimum cardinality of a 2-outer-independent dominating set of G.This paper characterizes all trees with the double domination number equal to the 2-outer-independent domination number plus one.     

Connected Domatic Number in Planar Graphs

A dominating set in a graph G is a connected dominating set of G if it induces a connected subgraph of G. The connected domatic number of G is the maximum number of pairwise disjoint, connected dominating sets in V(G). We establish a sharp lower bound on the number of edges in a connected graph with a given order and given connected domatic number. We also show that a planar graph has connected domatic number at most 4 and give a characterization of planar graphs having connected domatic number 3.     

Minor and minimum cycle bases of a 3-connected planar graph

In this paper, we prove that if any set of ｜E（G）｜- ｜V（G）｜ ＋ 1 facial cycles of a 3-connected planar graph G embedded in the plane doesn＇t form a minimum cycle base of G, then any minimum cycle base of G contains a separating cycle, and G has a minor isomorphic to T6, where T6 is the graph obtained from the complete graph K6 by deleting a path with four edges.     

A generalization of menger's theorem for certain block—cactus graphs

A graphG is called a block—cactus graph if each block ofG is complete or a cycle. In this paper, we shall show that a block—cactus graphG has the property that the cardinality of a smallest set separating any vertex setJ ofG is the maximum number of internally disjoint paths between the vertices ofJ if and only if every block ofG contains at most two cut-vertices. This result extends two theorems of Sampathkumar [4] and [5].     

Some Defective Parameters in Graphs

Given a graph G and an integer k, a set S of vertices in G is k-sparse if S induces a graph with a maximum degree of at most k. Many parameters in graph theory are defined in terms of independent sets. Accordingly, their definitions can be expanded taking into account the notion of k-sparse sets. In this discussion, we examine several of those extensions. Similarly, S is k-dense if S induces a k-sparse graph in the complement of G. A partition of V(G) is a k-defective cocoloring if each part is k-sparse or k-dense. The minimum order of all k-defective cocolorings is the k-defective cochromatic number of G and denoted z _k (G). Analogous notions are defined similarly for k-defective coloring where V(G) is partitioned into k-sparse parts. We show the NP-hardness of computing maximum k-defective sets in planar graphs with maximum degree at most k + 1 and arbitrarily large girth. We explore the extension of Ramsey numbers to k-sparse and k-dense sets of vertices. Lastly, we discuss some bounds related to k-defective colorings and k-defective cocolorings.     

A characterization of the interval distance monotone graphs

A simple connected graph G is said to be interval distance monotone if the interval I(u,v) between any pair of vertices u and v in G induces a distance monotone graph. A?¨der and Aouchiche [Distance monotonicity and a new characterization of hypercubes, Discrete Math. 245 (2002) 55-62] proposed the following conjecture: a graph G is interval distance monotone if and only if each of its intervals is either isomorphic to a path or to a cycle or to a hypercube. In this paper we verify the conjecture.     

Bounds on Laplacian eigenvalues related to total and signed domination of graphs

A total dominating set in a graph G is a subset X of V (G) such that each vertex of V (G) is adjacent to at least one vertex of X. The total domination number of G is the minimum cardinality of a total dominating set. A function f: V (G) → {−1, 1} is a signed dominating function (SDF) if the sum of its function values over any closed neighborhood is at least one. The weight of an SDF is the sum of its function values over all vertices. The signed domination number of G is the minimum weight of an SDF on G. In this paper we present several upper bounds on the algebraic connectivity of a connected graph in terms of the total domination and signed domination numbers of the graph. Also, we give lower bounds on the Laplacian spectral radius of a connected graph in terms of the signed domination number of the graph.     

Orthogonal latin square graphs

An orthogonal latin square graph (OLSG) is one in which the vertices are latin squares of the same order and on the same symbols, and two vertices are adjacent if and only if the latin squares are orthogonal. If G is an arbitrary finite graph, we say that G is realizable as an OLSG if there is an OLSG isomorphic to G. The spectrum of G [Spec(G)] is defined as the set of all integers n that there is a realization of G by latin squares of order n. The two basic theorems proved here are (1) every graph is realizable and (2) for any graph G, Spec G contains all but a finite set of integers. A number of examples are given that point to a number of wide open questions. An example of such a question is how to classify the graphs for which a given n lies in the spectrum.     

On supercompact graphs

A graph G is called a supercompact graph if G is the intersection graph of some family ?? of subsets of a set X such that ?? satisfies the Helly property and for any x≠y in X, there exists S ∈ ?? with x ∈ S, y ? S. Various characterizations of supercompact graphs are given. It is shown that every clique-critical graph is supercompact. Furthermore, for any finite graph, H, there is at most a finite number of different supercompact graphs G such that H is the clique-graph of G.     

Critically cochromatic graphs

A graph G is critically n-cochromatic if (its cochromatic number) z(G) = n and z(G - v) = n - 1 for every vertex v of G. Properties of critically n-cochromatic graphs are discussed and we also construct graphs that are critically n-chromatic and critically n-cochromatic.