On a problem of Davison. (Summary).
On a problem of P. Erdös
On a problem of R. Häggkvist concerning edge-colourings of graphs
On a special case of Hadwiger's conjecture
Hadwiger's Conjecture seems difficult to attack, even in the very special case of graphs G of independence number α(G) = 2. We present some results in this special case.
On a theorem of Erdős, Rubin, and Taylor on choosability of complete bipartite graphs.
On acyclic colorings of direct products
A coloring of a graph G is an acyclic coloring if the union of any two color classes induces a forest. It is proved that the acyclic chromatic number of direct product of two trees T₁ and T₂ equals min{Δ(T₁) + 1, Δ(T₂) + 1}. We also prove that the acyclic chromatic number of direct product of two complete graphs Kₘ and Kₙ is mn-m-2, where m ≥ n ≥ 4. Several bounds for the acyclic chromatic number of direct products are given and in connection to this some questions are raised.
On arc-coloring of subcubic graphs.
On bicritical snarks
On Brooks' theorem and some related results.
On characterization of uniquely 3-list colorable complete multipartite graphs
For each vertex v of a graph G, if there exists a list of k colors, L(v), such that there is a unique proper coloring for G from this collection of lists, then G is called a uniquely k-list colorable graph. Ghebleh and Mahmoodian characterized uniquely 3-list colorable complete multipartite graphs except for nine graphs: r ∈ 4,5,6,7,8, , , , . Also, they conjectured that the nine graphs are not U3LC graphs. After that, except for r ∈ 4,5,6,7,8, the others have been proved not to be U3LC...
On choosability of complete multipartite graphs
A graph G is said to be chromatic-choosable if ch(G) = χ(G). Ohba has conjectured that every graph G with 2χ(G)+1 or fewer vertices is chromatic-choosable. It is clear that Ohba’s conjecture is true if and only if it is true for complete multipartite graphs. In this paper we show that Ohba’s conjecture is true for complete multipartite graphs for all integers t ≥ 1 and k ≥ 2t+2, that is, , which extends the results given by Shen et al. (Discrete Math. 308 (2008) 136-143), and given by He...
On chromatic and achromatic numbers of uniform hypergraphs
On chromatic number of product of graphs
On chromatic number of products of two graphs
On chromatic uniqueness of a family of -homeomorphs.
On chromaticity of graphs
In this paper we obtain the explicit formulas for chromatic polynomials of cacti. From the results relating to cacti we deduce the analogous formulas for the chromatic polynomials of n-gon-trees. Besides, we characterize unicyclic graphs by their chromatic polynomials. We also show that the so-called clique-forest-like graphs are chromatically equivalent.
On Closed Modular Colorings of Trees
Two vertices u and v in a nontrivial connected graph G are twins if u and v have the same neighbors in V (G) − {u, v}. If u and v are adjacent, they are referred to as true twins; while if u and v are nonadjacent, they are false twins. For a positive integer k, let c : V (G) → Zk be a vertex coloring where adjacent vertices may be assigned the same color. The coloring c induces another vertex coloring c′ : V (G) → Zk defined by c′(v) = P u∈N[v] c(u) for each v ∈ V (G), where N[v] is the closed neighborhood...
On co-bicliques
A co-biclique of a simple undirected graph G = (V,E) is the edge-set of two disjoint complete subgraphs of G. (A co-biclique is the complement of a biclique.) A subset F ⊆ E is an independent of G if there is a co-biclique B such that F ⊆ B, otherwise F is a dependent of G. This paper describes the minimal dependents of G. (A minimal dependent is a dependent C such that any proper subset of C is an independent.) It is showed that a minimum-cost dependent set of G can be determined in polynomial...
On coloring the odd-distance graph.
On colorings avoiding a rainbow cycle and a fixed monochromatic subgraph.