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 9 Next

Displaying 161 – 180 of 227

Showing per page

Note on improper coloring of 1 -planar graphs

Yanan Chu, Lei Sun, Jun Yue (2019)

Czechoslovak Mathematical Journal

A graph G = ( V , E ) is called improperly ( d 1 , ⋯ , d k ) -colorable if the vertex set V can be partitioned into subsets V 1 , ⋯ , V k such that the graph G [ V i ] induced by the vertices of V i has maximum degree at most d i for all 1 ≤ i ≤ k . In this paper, we mainly study the improper coloring of 1 -planar graphs and show that 1 -planar graphs with girth at least 7 are ( 2 , 0 , 0 , 0 ) -colorable.

Note on independent sets of a graph

Jaroslav Ivančo (1994)

Mathematica Bohemica

Let the number of k -element sets of independent vertices and edges of a graph G be denoted by n ( G , k ) and m ( G , k ) , respectively. It is shown that the graphs whose every component is a circuit are the only graphs for which the equality n ( G , k ) = m ( G , k ) is satisfied for all values of k .

Note on k -chromatic graphs

Dănuţ Marcu (1994)

Mathematica Bohemica

In this paper we characterize k -chromatic graphs without isolated vertices and connected k -chromatic graphs having a minimal number of edges.

Note on partitions of planar graphs

Izak Broere, Bonita S. Wilson, Jozef Bucko (2005)

Discussiones Mathematicae Graph Theory

Chartrand and Kronk in 1969 showed that there are planar graphs whose vertices cannot be partitioned into two parts inducing acyclic subgraphs. In this note we show that the same is true even in the case when one of the partition classes is required to be triangle-free only.

Note on Petrie and Hamiltonian cycles in cubic polyhedral graphs

Jaroslav Ivančo, Stanislav Jendroľ, Michal Tkáč (1994)

Commentationes Mathematicae Universitatis Carolinae

In this note we show that deciding the existence of a Hamiltonian cycle in a cubic plane graph is equivalent to the problem of the existence of an associated cubic plane multi-3-gonal graph with a Hamiltonian cycle which takes alternately left and right edges at each successive vertex, i.ei̇t is also a Petrie cycle. The Petrie Hamiltonian cycle in an n -vertex plane cubic graph can be recognized by an O ( n ) -algorithm.

Currently displaying 161 – 180 of 227