Page 1 Next

Displaying 1 – 20 of 134

Showing per page

On ( 4 , 1 ) * -choosability of toroidal graphs without chordal 7-cycles and adjacent 4-cycles

Haihui Zhang (2013)

Commentationes Mathematicae Universitatis Carolinae

A graph G is called ( k , d ) * -choosable if for every list assignment L satisfying | L ( v ) | = k for all v V ( G ) , there is an L -coloring of G such that each vertex of G has at most d neighbors colored with the same color as itself. In this paper, it is proved that every toroidal graph without chordal 7-cycles and adjacent 4-cycles is ( 4 , 1 ) * -choosable.

On a problem of colouring the real plane

Filip Guldan (1991)

Mathematica Bohemica

What is the least number of colours which can be used to colour all points of the real Euclidean plane so that no two points which are unit distance apart have the same colour? This well known problem, open more than 25 years is studied in the paper. Some partial results and open subproblems are presented.

On a special case of Hadwiger's conjecture

Michael D. Plummer, Michael Stiebitz, Bjarne Toft (2003)

Discussiones Mathematicae Graph Theory

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 acyclic colorings of direct products

Simon Špacapan, Aleksandra Tepeh Horvat (2008)

Discussiones Mathematicae Graph Theory

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 characterization of uniquely 3-list colorable complete multipartite graphs

Yancai Zhao, Erfang Shan (2010)

Discussiones Mathematicae Graph Theory

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: K 2 , 2 , r r ∈ 4,5,6,7,8, K 2 , 3 , 4 , K 1 * 4 , 4 , K 1 * 4 , 5 , K 1 * 5 , 4 . Also, they conjectured that the nine graphs are not U3LC graphs. After that, except for K 2 , 2 , r r ∈ 4,5,6,7,8, the others have been proved not to be U3LC...

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...

Currently displaying 1 – 20 of 134

Page 1 Next