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 719

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

Currently displaying 41 – 60 of 719