The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

Displaying similar documents to “The use of Euler's formula in (3,1)*-list coloring”

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

Haihui Zhang (2013)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

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.

Recognizable colorings of cycles and trees

Michael J. Dorfling, Samantha Dorfling (2012)

Discussiones Mathematicae Graph Theory

Similarity:

For a graph G and a vertex-coloring c:V(G) → 1,2, ...,k, the color code of a vertex v is the (k+1)-tuple (a₀,a₁, ...,aₖ), where a₀ = c(v), and for 1 ≤ i ≤ k, a i is the number of neighbors of v colored i. A recognizable coloring is a coloring such that distinct vertices have distinct color codes. The recognition number of a graph is the minimum k for which G has a recognizable k-coloring. In this paper we prove three conjectures of Chartrand et al. in [8] regarding the recognition number...

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

Ping Wang, Jian-Liang Wu (2004)

Discussiones Mathematicae Graph Theory

Similarity:

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

Multicolor Ramsey numbers for paths and cycles

Tomasz Dzido (2005)

Discussiones Mathematicae Graph Theory

Similarity:

For given graphs G₁,G₂,...,Gₖ, k ≥ 2, the multicolor Ramsey number R(G₁,G₂,...,Gₖ) is the smallest integer n such that if we arbitrarily color the edges of the complete graph on n vertices with k colors, then it is always a monochromatic copy of some G i , for 1 ≤ i ≤ k. We give a lower bound for k-color Ramsey number R(Cₘ,Cₘ,...,Cₘ), where m ≥ 8 is even and Cₘ is the cycle on m vertices. In addition, we provide exact values for Ramsey numbers R(P₃,Cₘ,Cₚ), where P₃ is the path on 3 vertices,...

Functigraphs: An extension of permutation graphs

Andrew Chen, Daniela Ferrero, Ralucca Gera, Eunjeong Yi (2011)

Mathematica Bohemica

Similarity:

Let G 1 and G 2 be copies of a graph G , and let f : V ( G 1 ) V ( G 2 ) be a function. Then a functigraph C ( G , f ) = ( V , E ) is a generalization of a permutation graph, where V = V ( G 1 ) V ( G 2 ) and E = E ( G 1 ) E ( G 2 ) { u v : u V ( G 1 ) , v V ( G 2 ) , v = f ( u ) } . In this paper, we study colorability and planarity of functigraphs.

Defining sets in (proper) vertex colorings of the Cartesian product of a cycle with a complete graph

D. Ali Mojdeh (2006)

Discussiones Mathematicae Graph Theory

Similarity:

In a given graph G = (V,E), a set of vertices S with an assignment of colors to them is said to be a defining set of the vertex coloring of G, if there exists a unique extension of the colors of S to a c ≥ χ(G) coloring of the vertices of G. A defining set with minimum cardinality is called a minimum defining set and its cardinality is the defining number, denoted by d(G,c). The d(G = Cₘ × Kₙ, χ(G)) has been studied. In this note we show that the exact value of defining number d(G =...

A Fan-Type Heavy Pair Of Subgraphs For Pancyclicity Of 2-Connected Graphs

Wojciech Wideł (2016)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a graph on n vertices and let H be a given graph. We say that G is pancyclic, if it contains cycles of all lengths from 3 up to n, and that it is H-f1-heavy, if for every induced subgraph K of G isomorphic to H and every two vertices u, v ∈ V (K), dK(u, v) = 2 implies [...] min⁡dG(u),dG(v)≥n+12 min { d G ( u ) , d G ( v ) } n + 1 2 . In this paper we prove that every 2-connected K1,3, P5-f1-heavy graph is pancyclic. This result completes the answer to the problem of finding f1-heavy pairs of subgraphs implying...

Radio antipodal colorings of graphs

Gary Chartrand, David Erwin, Ping Zhang (2002)

Mathematica Bohemica

Similarity:

A radio antipodal coloring of a connected graph G with diameter d is an assignment of positive integers to the vertices of G , with x V ( G ) assigned c ( x ) , such that d ( u , v ) + | c ( u ) - c ( v ) | d for every two distinct vertices u , v of G , where d ( u , v ) is the distance between u and v in G . The radio antipodal coloring number a c ( c ) of a radio antipodal coloring c of G is the maximum color assigned to a vertex of G . The radio antipodal chromatic number a c ( G ) of G is min { a c ( c ) } over all radio antipodal colorings c of G . Radio antipodal chromatic numbers...