The use of Euler's formula in (3,1)*-list coloring

Yongqiang Zhao; Wenjie He

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 \in 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}) \to 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}) \cup V (G_{2})$ and $E = E (G_{1}) \cup E (G_{2}) \cup {u v : u \in V (G_{1}), v \in 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 =...

The Grötzsch theorem for the hypergraph of maximal cliques.

Mohar, Bojan, Škrekovski, Riste (1999)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

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)} \geq \frac{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 \in V (G)$ assigned $c (x)$ , such that $d (u, v) + | c (u) - c (v) | \geq 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...