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

Displaying 41 – 60 of 715

Showing per page

A note on on-line ranking number of graphs

Gabriel Semanišin, Roman Soták (2006)

Czechoslovak Mathematical Journal

A k -ranking of a graph G = ( V , E ) is a mapping ϕ V → { 1 , 2 , ⋯ , k } such that each path with endvertices of the same colour c contains an internal vertex with colour greater than c . The ranking number of a graph G is the smallest positive integer k admitting a k -ranking of G . In the on-line version of the problem, the vertices v 1 , v 2 , ⋯ , v n of G arrive one by one in an arbitrary order, and only the edges of the induced graph G [ { v 1 , v 2 , ⋯ , v i } ] are known when the colour for the vertex v i has to be chosen. The on-line ranking number of a graph G is the smallest...

A note on radio antipodal colourings of paths

Riadh Khennoufa, Olivier Togni (2005)

Mathematica Bohemica

The radio antipodal number of a graph G is the smallest integer c such that there exists an assignment f V ( G ) → { 1 , 2 , ... , c } satisfying | f ( u ) - f ( v ) | ≥ D - d ( u , v ) for every two distinct vertices u and v of G , where D is the diameter of G . In this note we determine the exact value of the antipodal number of the path, thus answering the conjecture given in [G. Chartrand, D. Erwin and P. Zhang, Math. Bohem. 127 (2002), 57–69]. We also show the connections between this colouring and radio labelings.

A Note on the Total Detection Numbers of Cycles

Henry E. Escuadro, Futaba Fujie, Chad E. Musick (2015)

Discussiones Mathematicae Graph Theory

Let G be a connected graph of size at least 2 and c :E(G)→{0, 1, . . . , k− 1} an edge coloring (or labeling) of G using k labels, where adjacent edges may be assigned the same label. For each vertex v of G, the color code of v with respect to c is the k-vector code(v) = (a0, a1, . . . , ak−1), where ai is the number of edges incident with v that are labeled i for 0 ≤ i ≤ k − 1. The labeling c is called a detectable labeling if distinct vertices in G have distinct color codes. The value val(c) of...

A note on total colorings of planar graphs without 4-cycles

Ping Wang, Jian-Liang Wu (2004)

Discussiones Mathematicae Graph Theory

Let G be a 2-connected planar graph with maximum degree Δ such that G has no cycle of length from 4 to k, where k ≥ 4. Then the total chromatic number of G is Δ +1 if (Δ,k) ∈ {(7,4),(6,5),(5,7),(4,14)}.

A note on uniquely H-colourable graphs

Anthony Bonato (2007)

Discussiones Mathematicae Graph Theory

For a graph H, we compare two notions of uniquely H-colourable graphs, where one is defined via automorphisms, the second by vertex partitions. We prove that the two notions of uniquely H-colourable are not identical for all H, and we give a condition for when they are identical. The condition is related to the first homomorphism theorem from algebra.

A Note On Vertex Colorings Of Plane Graphs

Igor Fabricia, Stanislav Jendrol’, Roman Soták (2014)

Discussiones Mathematicae Graph Theory

Given an integer valued weighting of all elements of a 2-connected plane graph G with vertex set V , let c(v) denote the sum of the weight of v ∈ V and of the weights of all edges and all faces incident with v. This vertex coloring of G is proper provided that c(u) ≠ c(v) for any two adjacent vertices u and v of G. We show that for every 2-connected plane graph there is such a proper vertex coloring with weights in {1, 2, 3}. In a special case, the value 3 is improved to 2.

A strongly non-Ramsey uncountable graph

Péter Komjáth (1997)

Fundamenta Mathematicae

It is consistent that there exists a graph X of cardinality ℵ 1 such that every graph has an edge coloring with ℵ 1 colors in which the induced copies of X (if there are any) are totally multicolored (get all possible colors).

A survey of hereditary properties of graphs

Mieczysław Borowiecki, Izak Broere, Marietjie Frick, Peter Mihók, Gabriel Semanišin (1997)

Discussiones Mathematicae Graph Theory

In this paper we survey results and open problems on the structure of additive and hereditary properties of graphs. The important role of vertex partition problems, in particular the existence of uniquely partitionable graphs and reducible properties of graphs in this structure is emphasized. Many related topics, including questions on the complexity of related problems, are investigated.

Currently displaying 41 – 60 of 715