All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 13 Next

Displaying 241 – 260 of 1336

Showing per page

On choosability of complete multipartite graphs K 4 , 3 * t , 2 * ( k - 2 t - 2 ) , 1 * ( t + 1 )

Guo-Ping Zheng, Yu-Fa Shen, Zuo-Li Chen, Jin-Feng Lv (2010)

Discussiones Mathematicae Graph Theory

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 K 4 , 3 * t , 2 * ( k - 2 t - 2 ) , 1 * ( t + 1 ) for all integers t ≥ 1 and k ≥ 2t+2, that is, c h ( K 4 , 3 * t , 2 * ( k - 2 t - 2 ) , 1 * ( t + 1 ) ) = k , which extends the results c h ( K 4 , 3 , 2 * ( k - 4 ) , 1 * 2 ) = k given by Shen et al. (Discrete Math. 308 (2008) 136-143), and c h ( K 4 , 3 * 2 , 2 * ( k - 6 ) , 1 * 3 ) = k given by He...

On chromaticity of graphs

Ewa Łazuka (1995)

Discussiones Mathematicae Graph Theory

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

Bryan Phinezy, Ping Zhang (2013)

Discussiones Mathematicae Graph Theory

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

Denis Cornaz (2007)

RAIRO - Operations Research

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 colored set partitions of type B n

David Wang (2014)

Open Mathematics

Generalizing Reiner’s notion of set partitions of type B n, we define colored B n-partitions by coloring the elements in and not in the zero-block respectively. Considering the generating function of colored B n-partitions, we get the exact formulas for the expectation and variance of the number of non-zero-blocks in a random colored B n-partition. We find an asymptotic expression of the total number of colored B n-partitions up to an error of O(n −1/2log7/2 n], and prove that the centralized and...

On colouring products of graphs

Dănuţ Marcu (1996)

Mathematica Bohemica

In this paper, we give some results concerning the colouring of the product (cartesian product) of two graphs.

Currently displaying 241 – 260 of 1336